圖論模型的建立與簡(jiǎn)單應(yīng)用

徐乙富 張俸川 石少儉

摘 要：在近些年的ACM ICPC競(jìng)賽中，圖論的題目屢見不鮮。圖論中的圖是由若干給定的點(diǎn)鏈接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形常來(lái)用于描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有的關(guān)系。

關(guān)鍵詞：圖論模型；拓?fù)洌粴W拉路徑

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

0 前言

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

1 Cover（HDU）

1.1 題目大意

給一個(gè)有n個(gè)節(jié)點(diǎn)m條邊的圖，每個(gè)節(jié)點(diǎn)從1到n標(biāo)號(hào)，題目給出m條邊的連接情況（1<=n，m<=100000），問(wèn)至少需要幾筆可以走完所有的m條邊，輸出最少的筆畫數(shù)目與每一筆所經(jīng)過(guò)的邊的編號(hào)。

1.2 分析

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

1.3 步驟

（1）首先，我們應(yīng)該根據(jù)題目的輸入將無(wú)向圖建立出來(lái)，由于頂點(diǎn)個(gè)數(shù)比較多，所以無(wú)法建立鄰接矩陣，可以建立鄰接表儲(chǔ)存邊的信息。（2）對(duì)于每一個(gè)連通塊進(jìn)行深度優(yōu)先搜索，對(duì)于每一個(gè)連通塊內(nèi)度數(shù)為奇數(shù)的點(diǎn)，可以兩兩之間加一條邊，這樣，對(duì)于每一個(gè)連通塊，最多要加入max（k/2，1）條邊，（k為度數(shù)為奇數(shù)的點(diǎn)的個(gè)數(shù)）。（3）再次進(jìn)行深度優(yōu)先搜索，每次搜索到加入的邊時(shí)，說(shuō)明搜到一條路徑，進(jìn)行輸出路徑（可以用一個(gè)以為數(shù)組暫時(shí)保存路徑并進(jìn)行輸出），這樣，就正好輸出了max（k/2，1）條的路徑。

1.4 小結(jié)

通過(guò)分析相關(guān)的問(wèn)題，將一個(gè)復(fù)雜的問(wèn)題轉(zhuǎn)化為構(gòu)造歐拉路徑的簡(jiǎn)單問(wèn)題，建立了正確的模型。由此可見，對(duì)于問(wèn)題正確的分析與認(rèn)識(shí)，是建立模型，解決問(wèn)題中至關(guān)重要的一步。本題所用到的歐拉路徑模型，在競(jìng)賽中比較常見，是一個(gè)重要的解決問(wèn)題的模型與方法。

2 Guess（UVA1423）

2.1 題目大意

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

2.2 分析

首先想到應(yīng)該求出sum[0]到sum[n]的值，輸出即可，而sum[i]的值可以設(shè)置在0到10之間，這樣的話，任意的sum[i]與sum[i-1]只差的絕對(duì)值不會(huì)超過(guò)10，滿足了題目要求的任意a[i]的絕對(duì)值小于等于10。 重點(diǎn)在于，這樣的前綴和可以轉(zhuǎn)化為拓?fù)渑判?，把i看做節(jié)點(diǎn)，當(dāng)a[i]加到a[j]的值大于0時(shí)，即sum[j]-sum[i-1]大于0，這樣連一條從j到i-1的邊，反之，連一條，從i-1到j(luò)的邊，這樣，最大的邊入度為0，進(jìn)行拓?fù)渑判蚣纯伞?/p>

2.3 步驟

（1）首先，對(duì)于輸入進(jìn)行建圖，當(dāng)輸入字符為‘+時(shí)，在j與i-1間加一條邊，當(dāng)輸入字符為‘-時(shí)，在i-1到j(luò)間建一條邊。（2）進(jìn)行拓?fù)渑判颍瑢?duì)于n個(gè)點(diǎn)，每次找到入度為0的點(diǎn) t ，將它的度數(shù)變?yōu)?1，并標(biāo)記已經(jīng)訪問(wèn)過(guò)這個(gè)點(diǎn)，將所有t指向的點(diǎn)的度數(shù)減一，每次記錄sum[t]=now--，初始now為10。（3）根據(jù)拓?fù)渑判蚯蟪龅膕um數(shù)組，求出最終的答案，即ans[i]=sum[i]-sum[i-1]。

2.4 小結(jié)

本道題目是一個(gè)比較抽象的題目，但是經(jīng)過(guò)對(duì)于前綴和性質(zhì)的認(rèn)真分析，可以建立了拓?fù)渑判蜻@一模型，將一個(gè)復(fù)雜的問(wèn)題轉(zhuǎn)化為一個(gè)簡(jiǎn)單的拓?fù)溥^(guò)程，在ACM ICPC中，拓?fù)渑判蜃鳛橐粋€(gè)常見的模型，經(jīng)常用于簡(jiǎn)化與解決復(fù)雜的問(wèn)題。

3 結(jié)論

問(wèn)題是千變?nèi)f化的，如何建立問(wèn)題的圖論模型并沒有通用的準(zhǔn)則。前面的兩個(gè)例子都比較簡(jiǎn)單，在更復(fù)雜的問(wèn)題中，有時(shí)會(huì)感到難以建立適當(dāng)?shù)哪Ｐ?，這時(shí)，需要在不改變問(wèn)題原型本身的性質(zhì)的前提下，對(duì)原型進(jìn)行抽象，簡(jiǎn)化，在此基礎(chǔ)上建立合適，有效的模型。有時(shí)，建立了問(wèn)題的一個(gè)模型之后，可能會(huì)感到難以求解，這時(shí)，可能需要對(duì)模型進(jìn)行修改，轉(zhuǎn)化，或者對(duì)原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個(gè)易于求解的模型。這些都需要有豐富的經(jīng)驗(yàn)，靈活的思維以及良好的創(chuàng)造力。在ICPC比賽中，更是要求在規(guī)定的時(shí)間內(nèi)可以正確的分析問(wèn)題，建立相應(yīng)的模型，并解決問(wèn)題的能力。

參考文獻(xiàn)：

[1]劉汝佳.算法競(jìng)賽入門經(jīng)典.第2版[M].清華大學(xué)出版社，2014.

[2]巫澤俊.挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽[M].人民郵電出版社，2013.

[3]黃蘭，魯珍珍，尹倩華等.圖論及其算法在數(shù)學(xué)建模中的應(yīng)用[J].數(shù)學(xué)學(xué)習(xí)與研究，2016（05）：106-107.

[4]楊玉軍，王大勇.圖論在數(shù)學(xué)建模中的應(yīng)用[J].教育現(xiàn)代化，2018

（04）.

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