圖論模型的建立與簡單應用

徐乙富 張俸川 石少儉

摘 要：在近些年的ACM ICPC競賽中，圖論的題目屢見不鮮。圖論中的圖是由若干給定的點鏈接兩點的線所構成的圖形，這種圖形常來用于描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有的關系。

關鍵詞：圖論模型；拓撲；歐拉路徑

DOI：10.16640/j.cnki.37-1222/t.2018.23.090

0 前言

圖論是數學的一個分支，它以圖作為研究對象。圖論中的圖是由若干給定的點鏈接兩點的線所構成的圖形，這種圖形常來用于描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有的關系。利用圖論解題，通常具有高效、簡潔的便利。有了這門工具，并不意味就能很好地解決問題，還在于我們能否熟練地識別與建立一系列的圖論模型。本文通過一些實例，簡單地介紹一下圖論建模的方法與應用。并通過建立相關的模型來解決相對較為復雜的問題。

1 Cover（HDU）

1.1 題目大意

給一個有n個節點m條邊的圖，每個節點從1到n標號，題目給出m條邊的連接情況（1<=n，m<=100000），問至少需要幾筆可以走完所有的m條邊，輸出最少的筆畫數目與每一筆所經過的邊的編號。

1.2 分析

容易想到，這個題目需要將最少筆畫數目轉化為無向圖的最小路徑覆蓋問題，然而，不同于常見的有向圖二分圖做法，需要建立一個歐拉路徑或歐拉回路的模型。當一個連通塊是歐拉路徑（度數為奇數的頂點的數目為0或者2）時，可以一筆走完所有的邊，所以將每個連通塊轉化為歐拉路徑進行搜索，轉化的方法是通過對度數為奇數的兩點之間加邊將連通塊轉化為歐拉路徑。

1.3 步驟

（1）首先，我們應該根據題目的輸入將無向圖建立出來，由于頂點個數比較多，所以無法建立鄰接矩陣，可以建立鄰接表儲存邊的信息。（2）對于每一個連通塊進行深度優先搜索，對于每一個連通塊內度數為奇數的點，可以兩兩之間加一條邊，這樣，對于每一個連通塊，最多要加入max（k/2，1）條邊，（k為度數為奇數的點的個數）。（3）再次進行深度優先搜索，每次搜索到加入的邊時，說明搜到一條路徑，進行輸出路徑（可以用一個以為數組暫時保存路徑并進行輸出），這樣，就正好輸出了max（k/2，1）條的路徑。

1.4 小結

通過分析相關的問題，將一個復雜的問題轉化為構造歐拉路徑的簡單問題，建立了正確的模型。由此可見，對于問題正確的分析與認識，是建立模型，解決問題中至關重要的一步。本題所用到的歐拉路徑模型，在競賽中比較常見，是一個重要的解決問題的模型與方法。

2 Guess（UVA1423）

2.1 題目大意

給出一個n*n（N>1&&N;<=10）的上三角矩陣S，S[i][j]表示數列a從a[i]+...a[j]和的大小，要求我們求出a[1]到a[n]的所有值，即通過和的值求元素的值。

2.2 分析

首先想到應該求出sum[0]到sum[n]的值，輸出即可，而sum[i]的值可以設置在0到10之間，這樣的話，任意的sum[i]與sum[i-1]只差的絕對值不會超過10，滿足了題目要求的任意a[i]的絕對值小于等于10。 重點在于，這樣的前綴和可以轉化為拓撲排序，把i看做節點，當a[i]加到a[j]的值大于0時，即sum[j]-sum[i-1]大于0，這樣連一條從j到i-1的邊，反之，連一條，從i-1到j的邊，這樣，最大的邊入度為0，進行拓撲排序即可。

2.3 步驟

（1）首先，對于輸入進行建圖，當輸入字符為‘+時，在j與i-1間加一條邊，當輸入字符為‘-時，在i-1到j間建一條邊。（2）進行拓撲排序，對于n個點，每次找到入度為0的點 t ，將它的度數變為-1，并標記已經訪問過這個點，將所有t指向的點的度數減一，每次記錄sum[t]=now--，初始now為10。（3）根據拓撲排序求出的sum數組，求出最終的答案，即ans[i]=sum[i]-sum[i-1]。

2.4 小結

本道題目是一個比較抽象的題目，但是經過對于前綴和性質的認真分析，可以建立了拓撲排序這一模型，將一個復雜的問題轉化為一個簡單的拓撲過程，在ACM ICPC中，拓撲排序作為一個常見的模型，經常用于簡化與解決復雜的問題。

3 結論

問題是千變萬化的，如何建立問題的圖論模型并沒有通用的準則。前面的兩個例子都比較簡單，在更復雜的問題中，有時會感到難以建立適當的模型，這時，需要在不改變問題原型本身的性質的前提下，對原型進行抽象，簡化，在此基礎上建立合適，有效的模型。有時，建立了問題的一個模型之后，可能會感到難以求解，這時，可能需要對模型進行修改，轉化，或者對原型進行更深入的分析，抽取其中較關鍵的要素，建立一個易于求解的模型。這些都需要有豐富的經驗，靈活的思維以及良好的創造力。在ICPC比賽中，更是要求在規定的時間內可以正確的分析問題，建立相應的模型，并解決問題的能力。

參考文獻：

[1]劉汝佳.算法競賽入門經典.第2版[M].清華大學出版社，2014.

[2]巫澤俊.挑戰程序設計競賽[M].人民郵電出版社，2013.

[3]黃蘭，魯珍珍，尹倩華等.圖論及其算法在數學建模中的應用[J].數學學習與研究，2016（05）：106-107.

[4]楊玉軍，王大勇.圖論在數學建模中的應用[J].教育現代化，2018

（04）.

作者簡介：徐乙富（1997-），男，山東臨沂人，本科，研究方向：ACM圖論建模與應用。