第一篇：圖論基礎知識
圖論基本知識
對于網絡的研究，最早是從數學家開始的，其基本的理論就是圖論，它也是目前組合數學領域最活躍的分支。我們在復雜網絡的研究中將要遇到的各種類型的網絡，無向的、有向的、加權的??這些都可以用圖論的語言和符號精確簡潔地描述。圖論不僅為物理學家提供了描述網絡的語言和研究的平臺，而且其結論和技巧已經被廣泛地移植到復雜網絡的研究中。圖論，尤其是隨機圖論已經與統計物理并駕齊驅地成為研究復雜網絡的兩大解析方法之一。考慮到物理學家對于圖論這一領域比較陌生，我在此專辟一章介紹圖論的基本知識，同時將在后面的章節中不加說明地使用本章定義過的符號。進一步研究所需要的更深入的圖論知識，請參考相關文獻[1-5]。
本章只給出非平凡的定理的證明，過于簡單直觀的定理的證明將留給讀者。個別定理涉及到非常深入的數學知識和繁復的證明，我們將列出相關參考文獻并略去證明過程。對于圖論知識比較熟悉的讀者可以直接跳過此章，不影響整體閱讀。
圖的基本概念
圖G是指兩個集合(V，E)，其中集合E是集合V×V的一個子集。集合V稱為圖的頂點集，往往被用來代表實際系統中的個體，集合E被稱為圖的邊集，多用于表示實際系統中個體之間的關系或相互作用。若{x,y}?E，就稱圖G中有一條從x到y的弧（有向邊），記為x→
y，其中頂點x叫做弧的起點，頂點y叫做弧的終點。根據定義，從任意頂點x到y至多只有一條弧，這是因為如果兩個頂點有多種需要區分的關系或相互作用，我們總是樂意在多個圖中分別表示，從而不至于因為這種復雜的關系而給解析分析帶來困難。如果再假設圖G中不含自己到自己的弧，我們就稱圖G為簡單圖，或者更精確地叫做有向簡單圖。以后如果沒有特殊的說明，所有出現的圖都是簡單圖。記G中頂點數為?(G)?|V|，邊數為?(G)?|E|，分別叫做圖G的階和規模，顯然有?(G)??(G)(?(G)?1)。圖2.1a給出了一個計算機分級網絡的示意圖，及其表示為頂點集和邊集的形式。
圖2.1：網絡拓撲結構示意圖。圖a是10階有向圖，頂點集為{1,2,3,4,5,6,7,8,9,10}，邊
集
為{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；圖b是6階無向圖，頂點集為{1,2,3,4,5,6}，邊集為{13,14,15,23,24,26,36,56}。
從定義中可以看到，從任意頂點x到y不能連接兩條或以上邊，本文所討論的圖，均符合上述要求，既均為不含多重邊的圖。如
果弧x→ y與弧y→ x要么同時存在，要么同時不存在，我們就把這兩條弧合為一條邊，記為xy或yx，這樣的圖叫做無向圖（對稱圖），可以被看作上述一般圖（有向圖）的一種特例。顯然，對無向圖而言，有?(G)??(G)(?(G)?1)/2，其中?(G)表示無向圖G中邊的數目。圖2b給出了一個無向圖的示意。以后提到的圖，若沒有特別的說明，均指無向圖。下面介紹的大部分結論都可以自然地從無向圖推廣到有向圖，勿需重復敘述，對于那些本質上有差異的特性，我們會在文中明確指出。
對于兩個圖G(V,E)和G'(V',E')，如果V'?V,E'?E，就稱G'是G的子圖。若V'?V，則稱G'是G的生成子圖；若在G中所有連接集合V'中兩頂點的邊都出現在集合E'，則稱G'是G的導出子圖，記為G'?G[V']。如果圖H與圖G有相同的頂點集，并且圖H中兩點之間有邊相連（相鄰）當且僅當在G中這兩點是不相鄰的，就稱圖H是圖G的余圖，記做H?G。擁有Cn條邊的n階無向圖或擁有Pn條邊的n階有向圖叫做完全圖，用符號Kn表示，其余圖Kn叫做空圖。
在無向圖G中，與某頂點x關聯的所有邊的數目叫做x的度，用符號dG(x)表示，在不致混淆的時候，可以簡單地記為d(x)。對于有向圖，由于需要區分從頂點出去的弧和進入頂點的弧，所以不能簡單地用度表示。我們把以頂點x為起點的弧的數目叫做x的出度，把以
??d(x)dxx頂點為終點的弧的數目叫做的入度，分別記為和(x)。頂點
22度與邊之間有一個顯然的關系：
定理2.1：對于無向圖G(V,E)有：
(2.1)對于有向圖G'(V',E')有：
(2.2)
x?V'?d(x)?2?(G)x?V
?d?(x)??d?(x)??(G')x?V'
在圖G中，以x為起點，y為終點的x?y路P是指一系列首尾相連的邊組成的集合：E(P)?{x0x1,x1x2,?,xl?1xl}
其中x0?x,xl?y，xi?xj,?0?i?j?l。邊的數目l被稱作路P的長度。如果x0xl?E，則稱邊集{x0x1,x1x2,?,xl?1xl,xlx0}為圈，其長度為l?1。G中最短的x?y路的長度稱為點x,y的距離，記為dG(x,y)，如果G中不存在x?y路，則記d(x,y)??。稱無向圖（有向圖）G為連通圖（強連通圖），如果對G中任意兩個不同頂點x,y，都能夠找到至少一條x?y路。有向圖G被稱為連通圖，如果對G中任意兩個不同頂點x,y，至少能找到一條x?y路或y?x路。
若圖G(V,E)的頂點集V可以拆成兩個不相交的子集V?V1?V2，且E中不含兩端點同時位于V1中或同時位于V2中的邊，就稱圖G為二部分圖。容易證明：
定理2.2：G是二部分圖當且僅當G中不含奇圈。
如果圖G不含圈，我們就稱其為森林，若它同時還是連通圖，則被叫做樹。定理2.3至定理2.5給出了樹的基本性質。
定理2.3：下面幾個命題是等價的：(1)G是樹；
(2)G是最小連通圖，也就是說，任意去掉一條邊，G都會變成非連通圖；
(3)G是最大無圈圖，也就是說，任意加上一條邊，G都會變成含圈圖；
(4)G是連通圖，且G中任意兩頂點之間有且只有一條路。定理2.4：n階樹有n?1條邊。
定理2.5：階數大于1的樹至少有兩個度為1的頂點。
直徑、平均距離、簇系數與度分布
對復雜網絡的研究最早始于對真實網絡諸如直徑、平均距離、簇系數等參數的取值以及頂點度分布的性質的實證研究，后續的大量研究也是圍繞這些概念進行的，因此有必要詳細地介紹這些概念的定義以及相關的基本結論，這些介紹將有助于我們更好地理解當前復雜網絡研究的物理意義。
在分析傳輸網絡的性能與效率時，有兩個因素總是受到特別的關注，即最大傳輸時延與平均傳輸時延。在圖理論中，它們被近似地抽象為兩個參數：直徑與平均距離。圖G(V,E)的直徑與平均距離可分別表為：
d(G)?max{dG(x,y)}x,y?V
?(G)?1dG(x,y)?v(v?1)x,y?V
為了敘述方便，后文中使用?(G)來代替有關?(G)的討論，其中
?(G)?v(v?1)?(G)。
關于圖直徑和平均距離的研究可以追溯到半個世紀前，Ore給出了無向圖直徑一個漂亮的緊界[6]，Entringer,Jackson,Slater和Ng,Teh分別就無向圖和有向圖的情形給出了圖平均距離粗糙但具有開創意義的下界[7,8]，再往后Plesnik給出了平均距離只依賴于階數和直徑的下界[9]。Zhou等人通過一種新的構造分析方法，給出了Ore定理的簡單證明，此方法可以無困難地將Ore定理推廣到有向圖形式。利用類似的分析方法，可以得到k直徑圖平均距離的下界定理，Entringer，Ng等人的結果可以作為該定理的一個自然的推論給出。結合此定理與Ore定理，可以只依賴于階數和直徑的平均距離下界，該下界是目前已知的最好的下界[10-11]。
Ore通過類似于構造廣度優先樹的方法將無向圖分割成一圈圈的等距子圖，其證明手法是優美而繁復的。由于其構造中隱含了dG(x,y)?dG(y,x)的條件，因此無法直接推廣到有向圖的形式。
顯然，任何v階圖都可以看作從完全無向圖或完全有向圖中移走若干條邊后得到的，下面將從這一簡單而直觀的角度出發，給出 Ore定理的簡單證明。
定理2.6[6,10-11]：對任意無向(v,k)圖G，有：
(2.3)
?(G)?k?(v?k?4)(v?k?1)12
其中(v,k)圖是指階數為v，直徑為k的簡單有限圖。
證明：用?(v,k)表示要得到無向(v,k)圖至少需要從完全圖Kv中移
走的邊的數目，則對任意無向(v,k)圖G，有：
?(G)??(Kv)??(v,k)
(2.4)令P?{x0,x1,x2,?,xk}為G中長為k的最短路，由P的最短性易知P1k(k?1)xi,xj|i?j|?12中兩點不相鄰，若。這就意味著至少有條邊必須從Kv中移走以得到圖G。同樣由P的最短性知，對于不在P中的頂點x，若P中兩點xi,xj滿足|i?j|?2，則x不能同時與xi,xj相鄰，即x最多與P中形如xi,xi?1,xi?2的三個頂點相鄰。換句話說，P中至少有(k?2)個點不與x相鄰。由于G中不在P上的頂點數為(v?k?1)，即有至少(v?k?1)(k?2)條邊必須從Kv中移去以得到G。綜上可知：
(2.5)結■ 合?(v,k)?k(k?1)?(v?k?1)(k?2)12
(2.4)(2.5)即得(2.3)式。
利用同樣的分析方法，可以得到Ore定理的有向圖形式，證明略。定理2.7[10-11]：對任意強連通有向(v,k)圖G，有：
(2.6)
?(G)?v(v?k?1)?(k2?k?4)12
下面兩個定理將給出平均距離的下界，由于證明比較復雜，此處省略。
定理2.8[10-11]：設G為無向(v,k)圖(k?2)，若G的規模為?，則有：
(2.7)
11?2v(v?1)?2??k(k?1)(k?2)?(v?k?1)(k?2)(k?4)k為偶??32?(G)???2v(v?1)?2?＋1k(k?1)(k?2)?1(v?k?1)(k?3)2 k為奇?32?
定理2.9[10-11]: 對任意無向(v,k)圖G，有：
11?2v(v?1)?2k?k(k?1)(k?2)?(v?k?1)(k2?4k?2v)k為偶??32?(G)???2v(v?1)?2k?1k(k?1)(k?2)?1(v?k?1)(k2?4k?2v?1)k為奇?32?
(2.8)有向圖的下界可以類似的得到，此處不再贅述。
圖的簇系數是衡量圖的成團特性的參數。對于無向圖G(V,E)，記某頂點x的鄰點集合為A(x)，顯然d(x)?|A(x)|，頂點x的簇系數被定義為它所有相鄰節點之間連邊的數目占可能的最大連邊數目的比例，即：
CG(x)?2?(G[A(x)])d(x)(d(x)?1)
圖G的簇系數則被定義為所有頂點簇系數的平均值：
C(G)?1?C(x)?(G)x?VG
在下一節我們可以通過隨機圖論的方法，得到關于簇系數的一些基本性質。
對于無向圖G(V,E)，記度為k的頂點數目為P(k)，則p(k)?P(k)?(G)給出了圖G的頂點度分布。類似地，關于頂點度分布的基本性質，需要到第三節才能給出。
隨機圖的基本模型與主要結論
隨機圖論起源于20世紀40年代一些零星的文章，其中Sezle的文章給出了目前已知的最早利用概率方法證明的非平凡的圖論定理[12-14]。1959年到1961年，Erd?s和Rényi三篇著名的文獻，使得隨機圖論開始成為圖論一個正式的分支，他們所構建的隨機圖的模型在后來被稱作ER模型[15-17]。下面的三篇重要文獻向我們展現了隨機圖論的全貌，也包含了我們將要討論到的大部分問題[1,18-19]。
考慮一個n階無向圖G(V,E)，Erd?s和Rényi給出了兩種相似但又不完全相同的隨機圖的模型。如果任意兩點之間獨立地以概率p連邊，以概率q?(1?p)不連邊，就得到第一種ER隨機圖，習慣上記做Gn,p；如果完全隨機地選擇m條邊作為邊集E，則得到第二種ER隨機圖，習慣上記做Gn,m。本節主要討論Gn,p的性質，其中大多數的結論對于圖Gn,m也是適用的（這里顯然有
m?pn(n?1)2）。
設n??且p?0（實際物理應用時只需要n足夠大，p足夠小既可以近似地求解），使得節點平均度z?p(n?1)為有限常數。只需注意到任意節點度為k的概率為
?n?1?kzke?zn?1?kpk????p(1?p)k!
?k?
(2.9)即可得到下面顯然但卻常用的定理：
定理2.10：若Gn,p滿足n??，p?0且z?p(n?1)為有限常數，則
其度分布為均值為z的泊松分布，因此Gn,p常被叫做泊松網絡。
我們將圖的頂點標號，以便彼此區別，對于某個k階圖F，NF被定義為Kk中與F同構的圖的數目。定理2.11給出了在Gn,p中特定結構出現的頻次。
定理2.11：記XF為圖Gn,p中與F同構的子圖的數目，則XF的期望值為：
?n?k!?(F)Ep(XF)???p?k?a
(2.10)其中a是F自同構群的階數。
?n?k!N?F??Ep(XF)?NFp?(F)?k?a，證明：顯然有，且根據同構計數原理有故■ 可得（2.10）式。
定理2.11雖然簡單，但是是隨機圖論最基本的定理之一，有著廣泛的應用。作為例子，下面我們給出定理2.11兩個直接的推論。
推論2.12：記Xs為Gn,p中子圖Ks的數目，則有：
s?n??2?Ep(Xs)???p?s?
(2.11)推論2.13：記Xk為Gn,p中導出子圖為k圈圖的點集數目，則有：
?n?k!kk(k?3)2Ep(Xk)???pqk2k??
(2.12)
需要提醒注意的是，由于推論2.13中要求的是導出子圖，所以k(k?3)2q多了一個因子。
仍然假設n??，用?n,p表示第一種ER隨機圖構成的概率空間，定理2.14給出了一個似乎不那么直觀但易于證明的結果。
(?hk?)為給定的自然數，定理2.14：設h1則在?n,p中幾乎所有（概率趨于1）圖都滿足：對于任意一個長度為k的點序列，圖中至少存在一個點，它與前h個點相鄰，而與后(k?h)個點不相鄰。
證明：我們考察“存在一個長度為k的點序列，使圖G??n,p中不存在任何點，它與前h個點相鄰，而與后(k?h)個點不相鄰”的概率?。長度為k的點序列的不同選取方法共有(n)k?n(n?1)?(n?k?1)種，對于某個選定的點序列，沒有任何頂點與前h個點相鄰，而與后(k?h)個
hk?hn?k(1?pq)。故有： 點不相鄰的概率為
(2.13)此■ 結lim??lim(n)k(1?phqk?h)n?k?limnk(1?phqk?h)n?k?0n??n??n??
論與定理2.14等價。
由定理2.14可以得到一些有趣的推論：
推論2.15：對給定的正整數k，幾乎所有圖G??n,p都滿足?(G)?k，其中?(G)表示G的最小度。
推論2.16：幾乎所有圖G??n,p的直徑都為2。
對某種性質Q，如果在任意具有該性質的圖上添加一條邊后得到的圖依然具有性質Q，則稱性質Q是單調遞增的性質。Erd?s和Rényi 的研究表明，隨著p的增加，很多單調遞增的性質會以某種很突然的方式涌現。對于給定的單調遞增的性質Q，稱pl(n)為?n,p的下極限函數，如果當p?pl(n)時，幾乎所有圖G??n,p都不含性質Q；類似地，稱pu(n)為?n,p的下極限函數，如果當p?pu(n)時，幾乎所有圖G??n,p都含有性質Q。
事實上，在很多情況下，下極限函數和上極限函數靠得非常近，因此我們才說相應的性質出現得非常突然。物理學家往往把這種現象看作一種相變，定理2.17給出的例子就可以被看作從不連通相向連通相的一個突變。
定理2.17：記?(n)??,且?(n)?logloglogn，令pu?pl?1(logn??(n))n，1(logn??(n))n，則幾乎所有的圖G??n,pl都不連通，而幾乎所有的u圖G??n,p都連通。
這里我們不打算給出定理的證明，但需要特別強調的一點是，很多物理學家在研究網絡時依然保留著在推導定理后再設計實驗進行驗證的習慣，這種習慣在網絡研究中是危險的，因此必須特別地謹慎。比如對于定理2.17，Bollobás認為n必須足夠大以保證?(n)?10，這種量級的n顯然不是當前計算機能力所能處理的。因此，如果只是隨便選取n?10或10進行實驗，那么不管結果怎樣，都只是一種假象。
下面的定理給出了一個經典的相變圖景，物理學家關于逾滲模型[20-21]很多重要的結論可以作為該定理的一個自然推論或利用類似的分析方法容易地得到。
定理2.18：考慮一個每次在圖G上隨機添加一條邊的隨機過程，Gn(n?1)2其生成的圖序列記為Gt，顯然G0為空圖，為完全圖。令c?0,h?1?cn2??，為確定的常數，?(n)與定理2.17一致。取??c?1?logc,t?t(n)??有：
如果c?1，則對任意的1?i?h和幾乎所有的圖Gt，有：
L(i)(Gt)?1?5?logn?loglogn????(n)??2?
(2.14)(1)(2)L(G)?L(G)??是圖G各連通片按階的大小排成的非增序其中列。
存在常數0?c1?c2，對任意的1?i?h和幾乎所有的圖
(2.15)如果c?1，則對幾乎所有的圖Gt，有：
(2.16)其中，0????(c)?1，?唯一地由式(2.17)決定：
L(1)(Gt)??n??(n)n1223c2n23?L(i)(G?)?cn2?n2??G??n2??，有：
?c?e?1??
(2.17)進一步的，對所有2?i?h，式(2.14)成立。
定理2.18的證明請參考文獻[16]，更細致的研究結果請參考
第二篇：《離散數學》圖論部分習題
《離散數學》圖論部分習題
1.已知無向圖G有12條邊，6個3度頂點，其余頂點的度數均小于3，問G至少有幾個頂點？并畫出滿足條件的一個圖形.（24-3*6）/2 +6=9 2.是否存在7階無向簡單圖G，其度序列為1、3、3、4、6、6、7.給出相應證明.不存在；7階無向簡單圖G中最大度≤6 3.設d1、d2、…、dn為n個互不相同的正整數.證明：不存在以d1、d2、…、dn為度序列的無向簡單圖.Max{d1，d2，…，dn}≥n，n階無向簡單圖G中最大度≤n-1 4.求下圖的補圖.5.1)試畫一個具有5個頂點的自補圖
2)是否存在具有6個頂點的自補圖，試說明理由。
對于n階圖，原圖與其補圖同構，邊數應相等，均為(n*(n-1)/2)/2，即n*(n-1)/4且為整 數，n=4k或n=4k+1，不存在6階自補圖。
6.設圖G為n(n>2且為奇數)階無向簡單圖，證明：G與G的補圖中奇度頂點個數相等.n(n>2且為奇數)，奇度點成對出現
7.無向圖G中只有2個奇度頂點u和v，u與v是否一定連通.給出說明或證明。
只有2個奇度頂點u和v，如果不連通，在u和v在2個連通分支上，每個分支上僅有一個奇度頂點，與握手引理相矛盾。
8.圖G如下圖所示：
1)寫出上圖的一個生成子圖.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.說明：δ(G)=min{ d(v)| v?V } ；κ(G)=min{ |V’| |V’是圖G的點割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} 9.在什么條件下無向完全圖Kn為歐拉圖？
n為奇數時
10.證明：有橋的圖不是歐拉圖.假設是歐拉圖：橋的端點是u和v，并且圖各頂點度均為偶數； 橋為割邊，刪除橋，圖不再連通，u和v應該在2各不同的連通分支上；且u和v度數變為奇數；由于其他頂點度數均為偶數，則u和v所在的連通分支上只有一個奇度頂點，與握手引理矛盾。
11.證明：有橋的圖不是哈密爾頓圖.若G是K2，顯然不是哈密爾頓圖；
否則n≥3，則橋的兩個端點u和v至少有一個不是懸掛頂點（容易證明懸掛頂點不是割點）；設u不是懸掛點，則u是割點，存在割點顯然不是哈密爾頓圖。
12.樹T有2個4度頂點，3個3度頂點，其余頂點全為樹葉，問T有幾片樹葉？
X+2*4+3*3=2*（2+3+x-1）
x=9 13.證明：最大度Δ（T）≥k的樹T至少有k片樹葉。
設有n個頂點，其中x片樹葉
2*（n-1）≥1*K+（n-x-1）*2+x*1
x≥k 14.已知具有3個連通分支的平面圖G有4個面，9條邊，求G的階數.n-9+4=3+1
n=9
15.給出全部互不同構的4階簡單無向圖的平面圖形。
16.如果G是平面圖, 有n個頂點、m條邊、f個面，G有k個連通分支。試利用歐拉公式證明:：n-m+f=k+1.
第三篇：《礦井通風網絡圖論》教學大綱
《礦井通風網絡圖論》教學大綱
課程中文名稱：礦井通風網絡圖論 課程英文名稱：Mine Ventilation network
theory 課程類別：專業課
課程編號: 課程歸屬單位：礦業學院 制定時間： 2006年9月2日
一、課程的性質和任務
1.課程的性質：本課程為采礦工程、安全工程專業本科生的專業選修課。
2.課程的任務：通過本課程的學習，要求學生掌握有關圖論的基本概念，網絡的基本數學模型，扇風機的運轉數學模型。理解網絡自然分風的算法框圖，并利用所學的計算機程序設計語言編制、解算。另外，通過本課程的學習，學生必須熟練將礦井通風系統圖繪制為通風網絡圖。
3、教學的基本要求
通過本課程的學習，學生應該掌握集合及其基本運算、矩陣代數基礎、圖論的基本知識、礦井通風網絡的基本數學模型、扇風機的運轉數學模型。學習通風網絡理論的目的，主要是掌握通風網絡繪制的基本規律和計算方法，為解決實際通風問題奠定基礎。
1）課程的重點及難點：本課程的重點是講解利用圖論的知識繪制礦井通風網絡圖。難點是根據實際問題建立礦井通風網絡數學模型。
2）課程的教學方法：課堂教學主要講解圖論的基礎知識，介紹基本的通風網絡數學模型。課外布置一定量習題供學生練習外。
3）課程的學習方法：要通過理論與方法學習、習題練習這兩個基本環節，來熟練掌握把礦井通風系統圖繪制為通風網絡圖。
4、適用專業及學分（學時）： 采礦工程、安全技術及工程, 2學分/36學時
5、本課程與其他課程的關系：礦井通風網絡圖論是一門與自然科學和應用技術兩者相聯系的邊緣科學,是平行于工程數學、計算機科學、礦井通風等獨立的學科, 必須先修完《工程數學》、《礦井通風》、《高級計算機語言程序設計》等課程。
6、教材、教學參考書： 教材： 貴州大學礦業學院采礦工程教研室自編教材。參考書：
1）《礦井通風系統優化原理與設計計算方法》 徐竹分編著 冶金工業出版社； 2）《通風網絡理論》徐瑞龍編著 煤炭工業出版社；
3）《礦井通風網絡分析及電算方法》譚國遼 煤炭工業出版社。
7、主要教學方法與媒體要求：課堂教學主要講解礦井通風網絡基本模型。課外布置一定量習題供學生練習。
二、課程內容
第一章 集合與矩陣代數基礎（4學時）
（一）、基本內容：
集合及其基本運算、矩陣代數基礎。
（二）、要求學生掌握的基本概念、理論、原理：
1、掌握集合概念及其表示方法。
2、了解集合基數、有限集、無限集、空集的概念。
3、掌握集合間的關系。
4、掌握集合的運算。
5、了解集合的圖解表示法。
6、掌握集合的運算律。
7、向量及線性空間。
8、矩陣及矩陣的秩。
9、矩陣的運算。
10、分塊矩陣。
（三）、本章教學重點和難點：
向量及線性空間、矩陣及矩陣的秩、矩陣的運算、分塊矩陣。第二章 圖論基礎（6學時）
（一）、基本內容：
圖的基本概念、圖的矩陣表示、生成樹的選擇。
（二）、要求學生掌握的基本概念、理論、原理：
1、了解圖的定義和術語、同構和子圖的概念。
2、掌握道路和回路的概念。
3、掌握樹的概念。
4、掌握割集的概念。
5、掌握圖的節點鄰接矩陣。
6、掌握關聯矩陣、回路矩陣和割集矩陣，了解圖的關聯、回路、割集矩陣間的關系。
7、掌握生成樹選擇。
8、掌握獨立回路選擇。
9、掌握生成數目的計算。
（三）、本章教學重點和難點：
圖的節點鄰接矩陣、關聯矩陣、回路矩陣、割集矩陣、生成樹選擇、獨立回路選擇。第三章 礦井通風網絡
（6學時）
（一）、基本內容：
礦井通風網絡圖、礦井通風網絡基本數學模型。
（二）、要求學生掌握的基本概念、理論、原理：
1、掌握礦井通風系統。
2、熟練掌握礦井通風網絡圖。
3、了解礦井通風網絡的有關子網絡。
4、了解礦井通風網絡在電子計算機中的存貯。
5、掌握礦井通風網絡內空氣流動的基本規律。
6、掌握礦井通風網絡的基本數學模型。
（三）、本章教學重點和難點：
礦井通風網絡圖、礦井通風網絡內空氣流動的基本規律、礦井通風網絡的基本數學模型。第四章 礦井通風機運轉特性及分析
（6學時）
（一）、基本內容：
通風機工作特性數學描述、通風機工況點求解與分析。
（二）、要求學生掌握的基本概念、理論、原理：
1、掌握通風機的特性方程。
2、掌握通風機特性方程的確定。
3、了解通風機特性方程的變換。
4、掌握通風機工況點參數的求解方法。
5、掌握通風機工況分析。
（三）、本章教學重點、難點：
通風機特性方程及其確定、通風機工況點參數的求解方法。第五章 通風網絡工況的計算與分析（6學時）
（一）、基本內容：
網絡自然分風數學模型、計算方法。
（二）、要求學生掌握的基本概念、理論、原理：
1、掌握網絡自然分風數學模型。
2、了解斯考德－恒斯雷法。
3、掌握牛頓法。
4、了解兩種計算方法的分析。
（三）、本章教學重點與難點： 網絡自然分風數學模型和牛頓法。第六章 通風網絡風流控制與調節（8學時）
（一）、基本內容：
礦井通風網絡的風流控制、調節方法、風量調節計算、井下發生火災時期的風流控制。
（二）、要求學生掌握的基本概念、理論、原理：
1、掌握礦井通風網絡的風流控制。
2、掌握調節方法。
3、掌握自然分風子網絡的風量計算。
4、掌握風量調節計算。
5、掌握火災時期受災區域的確定。
6、掌握火災時期風流控制的基本要求和原則。
（三）、本章教學重點、難點：
礦井通風網絡的風流控制、調節方法、風量調節計算、火災時期受災區域的確定、火災時期風流控制的基本要求和原則。
五、考核
閉卷考試（考試成績除筆試外，還包括平時上課、作業和實驗成績）。
第四篇：圖論在道路建設中的應用
龍源期刊網 http://.cn
圖論在道路建設中的應用
作者：張可波 鄭大斌
來源：《科技創新導報》2012年第03期
摘要：在修建道路的過程中，如何既保證各地之間運輸的需求又節約資源。這就是我們需要解決的問題。本文從當前我國經濟已經進入到了一個以資源節約．提高效率為主的時代的前提出發。利用圖論中的相關理論。較好地解決了道路網的量優化修建問題．井對這一類問題的解決提供一種新的思路。
關鍵詞；道路建設 最優化
最小生成樹Dijkstra算法 Greedy算法
第五篇：離散數學圖論習題
第4章圖論
綜合練習
一、單項選擇題
1．設L是n階無向圖G上的一條通路，則下面命題為假的是()．
(A)L可以不是簡單路徑，而是基本路徑
(B)L可以既是簡單路徑,又是基本路徑
(C)L可以既不是簡單路徑，又不是基本路徑
(D)L可以是簡單路徑，而不是基本路徑
答案：A
2．下列定義正確的是()．
(A)含平行邊或環的圖稱為多重圖(B)不含平行邊或環的圖稱為簡單圖
(C)含平行邊和環的圖稱為多重圖(D)不含平行邊和環的圖稱為簡單圖答案：D
3．以下結論正確是()．
(A)僅有一個孤立結點構成的圖是零圖
(B)無向完全圖Kn每個結點的度數是n
(C)有n(n>1)個孤立結點構成的圖是平凡圖
(D)圖中的基本回路都是簡單回路
答案：D
4．下列數組中，不能構成無向圖的度數列的數組是()．
(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)
答案：B
5．下列數組能構成簡單圖的是()．
(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)
答案：C
6．無向完全圖K3的不同構的生成子圖的個數為（）．
(A)6(B)5(C)4(D)
3答案：C
7．n階無向完全圖Kn中的邊數為（）．(A)n(n?1)n(n?1)(B)(C)n(D)n(n+1)2
2答案：B
8．以下命題正確的是()．
(A)n(n?1)階完全圖Kn都是歐拉圖
(B)n(n?1)階完全圖Kn都是哈密頓圖
(C)連通且滿足m=n－1的圖
(D)n(n?5)階完全圖Kn都是平面圖
答案：C
10．下列結論不正確是()．
(A)無向連通圖G是歐拉圖的充分必要條件是G不含奇數度結點
(B)無向連通圖G有歐拉路的充分必要條件是G最多有兩個奇數度結點
(C)有向連通圖D是歐拉圖的充分必要條件是D的每個結點的入度等于出度
(D)有向連通圖D有有向歐拉路的充分必要條件是除兩個結點外，每個結點的入度等
1于出度 答案：D
11．無向完全圖K4是（）．
（A）歐拉圖（B）哈密頓圖（C）樹答案：B
12．有4個結點的非同構的無向樹有()個．
(A)2(B)3(C)4(D)5 答案：A
13．設G是有n個結點，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹．
(A)m?n?1(B)n?m(C)m?n?1(D)n?m?1 答案：A
14．設G是有6個結點的完全圖，從G中刪去()條邊，則得到樹．(A)6(B)9(C)10(D)15 答案：C
二、填空題
1．數組{1，2，3，4，4}是一個能構成無向簡單圖的度數序列，此命題的真值是.答案：0
2．無向完全圖K3的所有非同構生成子圖有個． 答案：
43．設圖G??V,E?，其中?V??n,?E??m．則圖G是樹當且僅當G是連通的，且m?． 答案：n－
14．連通圖G是歐拉圖的充分必要條件是 答案：圖G無奇數度結點
5．連通無向圖G有6個頂點9條邊，從G中刪去G的一棵生成樹T． 答案：4
6．無向圖G為歐拉圖，當且僅當G是連通的，且G中無 答案：奇數度
7．設圖G??V,E?是簡單圖，若圖中每對結點的度數之和，則G一定是哈密頓圖． 答案：?
8．如圖1所示帶權圖中最小生成樹的權是．
答案：1
2三、化簡解答題
1．設無向圖G＝
圖
1圖
2(2)寫出結點v2, v4，v6的度數；(3)判斷圖G是簡單圖還是多重圖．解：(1)圖G的圖形如圖5所示．
(2)deg(v2)?4,deg(v4)?3,deg(v6)?0．
(3)圖G是多重圖．作圖如圖2.2．設圖G＝
V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}
試作出圖G的圖形，并指出圖G是簡單圖還是多
重圖？是連通圖嗎？說明理由.be
解：圖G如圖8所示．.圖G中既無環，也無平行邊，是簡單圖． cd 圖G是連通圖．G中任意兩點都連通.圖
3所以，圖G有9個結點．作圖如圖3．
四、計算題
1．設簡單連通無向圖G有12條邊，G中有2個1度結點，2個2度結點，3個4度結點，其余結點度數為3．求G中有多少個結點．試作一個滿足該條件的簡單無向圖．
解：設圖G有x個結點，由握手定理
2?1+2?2+3?4+3?（x?2?2?3）＝12?
23x?24?21?18?27x＝9 故圖G有9個結點． 圖
4滿足該條件的簡單無向圖如圖4所示
2．設圖G(如圖5表示)是6個結點a,b,c, d,e,f的圖，試求，圖G的最小生成樹，并計算它的權．
c 解：構造連通無圈的圖，即最小生成樹，用
克魯斯克爾算法：
第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9圖5第五步： 取bc=2
3如圖6．權為1+4+3+9+23=40
3．一棵樹T有兩個2度頂點，1個3度頂點；3個4
問它有幾片樹葉？
解：設T有n頂點，則有n－1條邊．T中有2個 2度頂點，1個3度頂點，3個4度頂點，其余n－2－1-3個1度頂
點．
由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片樹葉
五、證明題
1．若無向圖G中只有兩個奇數度結點，則這兩個結點一定是連通的．
證：用反證法．設G中的兩個奇數度結點分別為u和v．假若u和v不連通．
即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數度結點．這與握手定理的推論矛盾．因而u和v一定是連通的．
點擊咨詢 