圖論算法-2013資料

現(xiàn)代圖論算法目錄一，引例二，基本圖論概念三，圖的表示四，“簡單”圖論問題五，“困難”圖論問題六，現(xiàn)代圖論算法七，例子：最大團(tuán)、社團(tuán)發(fā)現(xiàn)八，習(xí)題一，引例哥尼斯堡的七橋問題BACD

當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問題：一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地？

為了尋找答案，1736年歐拉把陸地縮為一點(diǎn)，把橋作為連接點(diǎn)的邊，將這個(gè)問題抽象成圖形的一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。BACD“巧渡河”問題問題：人、狼、羊、菜用一條只能同時(shí)載兩位的小船渡河，“狼羊”、“羊菜”不能在無人在場時(shí)共處，當(dāng)然只有人能架船。圖模型：頂點(diǎn)表示“原岸的狀態(tài)”，兩點(diǎn)之間有邊當(dāng)且僅當(dāng)一次合理的渡河“操作”能夠?qū)崿F(xiàn)該狀態(tài)的轉(zhuǎn)變。起始狀態(tài)是“人狼羊菜”，結(jié)束狀態(tài)是“空”。問題的解：找到一條從起始狀態(tài)到結(jié)束狀態(tài)的盡可能短的通路。“巧渡河”問題的解注意：在“人狼羊菜”的16種組合中允許出現(xiàn)的只有10種。(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河?xùn)|=(人,狼,羊,菜)

將10個(gè)頂點(diǎn)分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.其他模型網(wǎng)絡(luò)流問題全一問題最短網(wǎng)絡(luò)問題……網(wǎng)絡(luò)流問題隨著中國經(jīng)濟(jì)快速的增長，城市化是未來中國的發(fā)展方向。人大通過的“十五”規(guī)劃，把物流業(yè)作為戰(zhàn)略重點(diǎn)列入要大力發(fā)展的新興服務(wù)產(chǎn)業(yè)。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。

網(wǎng)絡(luò)流問題1956年Ford和Fulkerson提出了關(guān)于網(wǎng)絡(luò)流問題的一個(gè)重要定理。最大流最小割定理：在任何網(wǎng)絡(luò)中，最大流的值等于最小割的容量。由這個(gè)定理可以引出求網(wǎng)絡(luò)最大流的一個(gè)算法——標(biāo)號(hào)法。1970年，Edmonds和Karp

對標(biāo)號(hào)程序加以改進(jìn)，使之成為一個(gè)好的算法。全一問題

假設(shè)博物館里有若干個(gè)房間，每個(gè)房間里有一盞燈和一個(gè)開關(guān)，每次按下某個(gè)房間的開關(guān)，可以改變這個(gè)房間以及它相鄰的房間的燈的狀態(tài)。全一問題問是否可以找到一種開燈的方案，使得所有房間的燈由全亮變?yōu)槿珳纾窟@就是Sutner于1989年提出的“全一問題”（All-OnesProblem)。最短網(wǎng)絡(luò)問題

如何用最短的線路將三部電話連起來？此問題可抽象為設(shè)△ABC為等邊三角形，，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC最短網(wǎng)絡(luò)問題

但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為PA＋PB＋PC。最短新路徑之長N比原來只連三點(diǎn)的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。

ABCPPollak－Gilbert猜想由于最短網(wǎng)絡(luò)在運(yùn)輸、通訊和計(jì)算機(jī)等現(xiàn)代經(jīng)濟(jì)與科技領(lǐng)域中都有重要的應(yīng)用，對這個(gè)問題的研究也越來越深入。問題的對象已由三個(gè)點(diǎn)擴(kuò)展到任意有限個(gè)點(diǎn)集。Pollak－Gilbert猜想斯坦納（Steiner）最小樹是可以在給定的點(diǎn)之外再增加若干個(gè)點(diǎn)(稱為斯坦納點(diǎn))，然后將所有這些點(diǎn)連起來。如果不允許增加任何額外的點(diǎn)作為網(wǎng)絡(luò)的頂點(diǎn)，這種最短網(wǎng)絡(luò)稱為最小生成樹。在前面的例子中Steiner最小樹的長為而最小生成樹的長為2。Pollak－Gilbert猜想1968年貝爾實(shí)驗(yàn)室數(shù)學(xué)中心主任波雷克(Pollak)和研究員吉爾伯特(Gilbert)提出如下猜想：平面上任意n點(diǎn)集，斯坦納最小樹長與最小生成樹之長的比值的最小值是。

這個(gè)猜想又被稱為斯坦納比猜想。Pollak－Gilbert猜想1990年，中科院應(yīng)用數(shù)學(xué)所研究員堵丁柱與美籍華人黃光明合作，證明了Pollak－Gilbert猜想。在美國離散數(shù)學(xué)界引起轟動(dòng)，被列為1989—1990年度美國離散數(shù)學(xué)界與理論計(jì)算機(jī)科學(xué)界的兩項(xiàng)重大成果之一。

在《不列顛百科全書1992年鑒》的數(shù)學(xué)評論中，該成果被列為世界上當(dāng)年六項(xiàng)數(shù)學(xué)成果首項(xiàng)。該成果被我國列為1992年十大科技成就之一。

二，基本圖論概念圖（graph）是由一些結(jié)點(diǎn)或頂點(diǎn)（nodesorvertices）以及連接點(diǎn)的邊（edges）構(gòu)成。記做G={V,E}，其中V是頂點(diǎn)的集合，E是邊的集合。如果E的每一條邊都是無向邊,則稱G為無向圖;如果E的每一條邊都是有向邊,則稱G為有向圖無向圖與有向圖[定義]孤立點(diǎn)

若a∈V，a不與其他頂點(diǎn)相鄰，稱a為孤立點(diǎn)(isolatedvertex)。[定義]頂點(diǎn)的度

在無向圖G中，與a相鄰的頂點(diǎn)的數(shù)目稱為a的度(degree)。記為deg(a)或d(a)。在有向圖D中，以a為終點(diǎn)的邊的條數(shù)稱為a的入度(in-degree)。記為deg–(a)或d–(a)。以a為始點(diǎn)的邊的條數(shù)稱為a的出度(out-degree)。記為deg+(a)或d+(a)。[定理1(握手定理Handshaking)]

設(shè)無向圖G=<V,E>有n個(gè)頂點(diǎn)，m條邊，則G中所有頂點(diǎn)的度之和等于m的兩倍。即證明思路：利用數(shù)學(xué)歸納法。[定理2]

無向圖中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)恰有偶數(shù)個(gè)。證明思路：將圖中頂點(diǎn)的度分類，再利用定理1。[定理3]

設(shè)有向圖D=<V,E>有n個(gè)頂點(diǎn)，m條邊，則G中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，也等于m。即：證明思路：利用數(shù)學(xué)歸納法。一些特殊的簡單圖：

(1)無向完全圖Kn(CompleteGraphs)(2)有向完全圖

(3)零圖：E=.(4)平凡圖：E=且|V|=1.(5)正則圖：若圖G＝<V,E>中每個(gè)頂點(diǎn)的度均為n，稱此圖G是n-正則圖(n-regulargraph)。完全圖(n=1,2,3,4,5)[定理4]設(shè)無向完全圖G有n個(gè)頂點(diǎn)，則G有n(n-1)/2條邊。證明：每一頂點(diǎn)都與其余的n-1個(gè)頂點(diǎn)相鄰，即每一頂點(diǎn)的度為n-1，共有n個(gè)頂點(diǎn)，則圖G的度為n(n-1)，由握手定理，得邊數(shù)m=n(n-1)/2.正則圖（各頂點(diǎn)的度相同）3-正則圖3-正則圖[定義]子圖設(shè)G=<V,E>，G’=<V’,E’>是兩個(gè)圖，若V’V，且E’E，則稱G’為G的子圖(subgraph)。注：

當(dāng)V’=V時(shí)，稱G’為G的生成子圖。當(dāng)E’E，或V’V時(shí)，稱G’為G的真子圖。[定義]補(bǔ)圖

設(shè)G=<V,E>是n階無向簡單圖，以V為頂點(diǎn)集，以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G相對于完全圖Kn的補(bǔ)圖，簡稱G的補(bǔ)圖，記為。圖G與其補(bǔ)圖G’具有相同的頂點(diǎn)集，其邊集不相交，構(gòu)成相應(yīng)完全圖邊集的劃分。圖A圖B圖C圖D圖E圖F圖Ａ是一個(gè)無向完全圖圖Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子圖圖Ｃ的頂點(diǎn)ａ是孤立頂點(diǎn)圖Ｂ的邊(ａ，ｂ)是孤立邊圖Ｄ是圖Ｃ的子圖圖Ｅ是圖Ｃ的補(bǔ)圖例：有向圖例：abcde2(a)1(b)3(d)4(c)5(e)例：(1)畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無向簡單圖。(2)畫出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡單圖。?

(1)(2)⑴

鄰接矩陣鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)系.一個(gè)n階圖G的鄰接矩陣A=(aij)n×n,

其中

三，圖的表示無向圖G的鄰接矩陣A是一個(gè)對稱矩陣.

⑵

權(quán)矩陣一個(gè)n階賦權(quán)圖G=(V,E,F)的權(quán)矩陣A=(aij)n×n,

其中

有限簡單圖基本上可用權(quán)矩陣來表示.無向圖G的權(quán)矩陣A是一個(gè)對稱矩陣.

⑶

關(guān)聯(lián)矩陣（略）一個(gè)有m條邊的n階有向圖G的關(guān)聯(lián)矩陣A=(aij)n×m,

其中

若vi是ej的始點(diǎn);若vi是ej的終點(diǎn);若vi與ej不關(guān)聯(lián).有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)1,有且僅有一個(gè)

-

1.一個(gè)有m條邊的n階無向圖G的關(guān)聯(lián)矩陣A=(aij)n×m,

其中

若vi與ej關(guān)聯(lián);若vi與ej不關(guān)聯(lián).無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)1.0A141B0452C353D254E015F123BACDFE(4)鄰接表

142301201234ABCDE有向圖的鄰接表ABECF可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。typedefstructArcNode{

intadjvex;//該弧所指向的頂點(diǎn)的位置

structArcNode*nextarc;//指向下一條弧的指針

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvexnextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)typedefstructVNode{

VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧

}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標(biāo)志

}ALGraph;圖的結(jié)構(gòu)定義四，“簡單”圖論問題圖的遍歷（深度優(yōu)先，廣度優(yōu)先）最小生成樹（Kruskal,Prim）最短路徑問題(Dijkstra,Floyd)最大流問題(標(biāo)號(hào)法)。。。。。。“簡單”：都能在多項(xiàng)式時(shí)間內(nèi)解決樹：邊數(shù)比點(diǎn)數(shù)少1的連通圖稱作樹。生成樹：一棵樹是連通子圖，則稱作該圖的生成樹。連通圖GG的生成樹

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2圖的最小生成樹樹中次數(shù)為1的頂點(diǎn)稱為樹葉。一個(gè)無向圖的諸連通分圖均是樹,則稱該無向圖為森林,樹是森林。

若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件：T是G的連通子圖T包含G的所有頂點(diǎn)T中無回路注意：（1）若在生成樹中刪除一條邊就會(huì)使該生成樹因變成非連通圖而不再滿足生成樹的定義；（2）若在生成樹中增加一條邊就會(huì)使該生成樹中因存在回路而不再滿足生成樹的定義；（3）一個(gè)連通圖的生成樹可能有許多；（4）有n個(gè)頂點(diǎn)的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。

1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無向圖和它的不同的生成樹

最小生成樹

一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是不唯一的，并且有保持圖連通的最少的邊。

如果無向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小代價(jià)生成樹，簡稱最小生成樹。水源某農(nóng)場的水稻田用堤埂分割成很多小塊。為了用水灌溉，需要挖開一些堤埂。問最少挖開多少條堤埂，才能使水澆灌到每小塊稻田？

生成樹的一個(gè)例子

構(gòu)造有n個(gè)頂點(diǎn)的無向連通帶權(quán)圖的最小生成樹必須滿足以下四條：（1）構(gòu)造的最小生成樹必須包括n個(gè)頂點(diǎn)；（2）構(gòu)造的最小生成樹中有且只有n-1條邊；（3）構(gòu)造的最小生成樹中不存在回路。（4）構(gòu)造的最小生成樹的邊的權(quán)值總和最小典型的構(gòu)造方法有兩種，一種稱作普里姆（Prim）算法，另一種稱作克魯斯卡爾（Kruskal）算法。

克魯斯卡爾算法：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中克魯斯卡爾算法構(gòu)造最小生成樹的過程例165432641356642516543212345克魯斯卡爾（Kruskal）算法：怎么判斷有沒有回環(huán)？普里姆（Prim）算法：設(shè)G=（V，E）為一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)的連通網(wǎng)絡(luò)，T=（U，TE）為構(gòu)造的生成樹。初始時(shí)，U={u0}，TE=；在所有uU

、vV-U

的邊（u,v）中選擇一條權(quán)值最小的邊，不妨設(shè)為（u,v)；(u,v)加入TE，同時(shí)將v加入U(xiǎn)；重復(fù)(2)、（3），直到U=V為止；例1654326513566425131163141643142116432142516543214253最短路問題最短路問題是指從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短（權(quán)值和最?。┑囊粭l路。某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃問題可以歸結(jié)為求最短路的問題。如選址問題、管道鋪設(shè)選線問題、設(shè)備更新、投資等問題。

最短路的求法：1.從某一點(diǎn)至其它各點(diǎn)之間最短距離的迪杰斯特拉(Dijksrta

)算法;2.求網(wǎng)絡(luò)圖中任意兩點(diǎn)之間的最短距離的矩陣算法。Dijstra,EdsgarWybe(1930-)荷蘭計(jì)算機(jī)科學(xué)家，1972年圖林獎(jiǎng)得主。最著名的成果：首先指出程序設(shè)計(jì)語言中的goto語句是有害的，并首創(chuàng)了結(jié)構(gòu)化程序設(shè)計(jì)方法。至今仍被廣泛應(yīng)用的算法：解決機(jī)器人運(yùn)動(dòng)路徑規(guī)劃問題的“最短路徑算法”。被引用最多的論斷：“程序測試只能用來證明有錯(cuò)，絕不能證明無錯(cuò)?！北灰米鳛槠?0歲生日紀(jì)念論文集書名的另一句名言：Beautyisourbusiness

一.Dijkstra算法1.設(shè)dij表示圖中兩相鄰點(diǎn)i與j的距離，若i與j不相鄰，令dij=∞，顯然dii=0。

Dijkstra算法假設(shè)：基本思路：如果v1→v2→v3→v4是v1→v4的最短路徑，則v1→v2→v3一定是v1→v3的最短路徑。v2→v3→v4一定是v2→v4的最短路徑。2.設(shè)Lsi表示從s點(diǎn)到i點(diǎn)的最短距離。Dijkstra算法步驟：1.對起始點(diǎn)s，因Lss=0，將0標(biāo)注在s旁的小方框內(nèi)，表示s點(diǎn)已標(biāo)號(hào)；2.從點(diǎn)s出發(fā)，找出與s相鄰的點(diǎn)中距離最小的一個(gè)，設(shè)為r，將Lsr=Lss+dsr的值標(biāo)注在r旁的小方框內(nèi)，表明點(diǎn)r也已標(biāo)號(hào)；3.從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)p，若有Lsp=min{Lss+dsp,Lsr+drp}，則對p點(diǎn)標(biāo)號(hào)，并將Lsp的值標(biāo)注在p點(diǎn)旁的小方框內(nèi)；4.重復(fù)第3步，直到t點(diǎn)得到標(biāo)號(hào)為止。求從起始點(diǎn)s到終止點(diǎn)t的最短路徑。例.求下圖中從v1到v7的最短路。解：(1)

從v1點(diǎn)出發(fā)，對v1點(diǎn)標(biāo)號(hào)，將L11=0標(biāo)注在旁的小方框內(nèi)，令v1∈V，其余點(diǎn)屬于；L1r=min{0+d12

,0+d13

}=min{5,2}=2=L13(2)

同v1相鄰的未標(biāo)號(hào)點(diǎn)有v2、v3，對v3

標(biāo)號(hào)，將L13的值標(biāo)注在v3旁的小方框內(nèi)；將(v1,v3)加粗，并令V∪v3→V，。L1p=min{L11+d12

,L13+d34,L13+d36

}=min{0+5,2+7,2+4}=5=L12(3)

同v1,v3相鄰的未標(biāo)號(hào)點(diǎn)有v2、v4、v6，對v2

標(biāo)號(hào)，將L12的值標(biāo)注在v2旁的小方框內(nèi)；將(v1,v2)加粗，并令V∪v2→V，L1p=min{L12+d25

,L12+d24,

L13+d34

,L13+d36

}=min{5+7,5+2,2+7,2+4}=6=L16。(4)

同v1,v2,v3相鄰的未標(biāo)號(hào)點(diǎn)有v4、v5、v6，對v6

標(biāo)號(hào)，將L16的值標(biāo)注在v6旁的小方框內(nèi)；將(v3,v6)加粗，并令V∪v6→V，L1p=min{L12+d25

,L12+d24,L13+d34

,L16+d64,L16+d65,L16+d67

}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15(5)

同v1,v2,v3,v6相鄰的未標(biāo)號(hào)點(diǎn)有v4、v5、v7，對v4,v5同時(shí)標(biāo)號(hào)，將L14=L15的值標(biāo)注在v4,v5旁的小方框內(nèi)；將(v2,v4),(v6,v5)加粗，并令V∪v4∪v5→V，L1p=min{L15+d57

,L16+d67

}=min{7+3,6+6}=10=L17(6)

同v1,v2,v3,v4,v5,v6相鄰的未標(biāo)號(hào)點(diǎn)只有v7，

對v7

標(biāo)號(hào)，將L17的值標(biāo)注在v7旁的小方框內(nèi)；將(v5,v7)加粗。圖中粗線表明從點(diǎn)v1到網(wǎng)絡(luò)中其它各點(diǎn)的最短路，各點(diǎn)旁的數(shù)字就是點(diǎn)v1到各點(diǎn)的最短距離。Dijsktra算法其實(shí)求出了起始點(diǎn)到其他點(diǎn)的所有最短路徑這些最短路徑構(gòu)成了一棵生成樹！二.Floyd算法用Dijkstra算法只能計(jì)算從圖中某一點(diǎn)到其他點(diǎn)的最短距離，如果要計(jì)算各點(diǎn)之間的最短距離就需要對每個(gè)點(diǎn)分別計(jì)算，而用矩陣算法則可以同時(shí)求出所有各點(diǎn)間的最短距離。例.利用矩陣算法求上述網(wǎng)絡(luò)圖中各點(diǎn)間的最短距離。解.設(shè)dij表示圖中兩相鄰點(diǎn)i與j的距離，若i與j不相鄰，令dij=∞，顯然dii=0。建立距離矩陣：從上述距離矩陣可以看出從i點(diǎn)到j(luò)點(diǎn)的直接距離，但從i到j(luò)的最段距離不一定就是從i點(diǎn)直接到j(luò)點(diǎn)。如上述問題中，從v1→v2的最短距離應(yīng)該是min{d11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72}即min{d1r+dr2}。因此可以構(gòu)造一個(gè)新的矩陣D(1)，令D(1)中每一個(gè)元素為：dij(1)=min{dir+drj}，則矩陣D(1)給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)及經(jīng)由一個(gè)中間點(diǎn)時(shí)的最短距離。再構(gòu)造矩陣D(2)，dij(2)=min{dir(1)

+drj(1)}。依次類推構(gòu)造矩陣D(k)，

dij(k)=min{dir(k-1)

+drj(k-1)}

計(jì)算停止的控制：

p是圖中頂點(diǎn)數(shù)。輸入:

n×n維矩陣l[1···n，1···n]，以便對于有向圖G＝({1，2，···，n}，E)中的邊(i，j)的長度為l[i，j]。輸出:

矩陣D，使得D[i，j]等于i到j(luò)的距離。1.D←l

｛將輸入矩陣

l復(fù)制到D｝2.for

k←1to

n3.for

i←1to

n4.for

j←1to

n5.D[i，j]=min｛D[i，j]，D[i，k]+D[k，j]｝6.endfor7.endfor8.endforFloyd算法：該例中k=3

上述D(2)中的元素給出了各點(diǎn)間的最短距離，但是并沒有給出具體是經(jīng)過了哪些中間點(diǎn)才得到的這個(gè)最短距離，如果要知道中間點(diǎn)具體是什么，需要在計(jì)算過程中進(jìn)行記錄。網(wǎng)絡(luò)的最大流一.網(wǎng)絡(luò)最大流的有關(guān)概念1.有向圖與容量網(wǎng)絡(luò)圖中每條邊有規(guī)定指向的圖稱為有向圖，有向圖的邊稱為弧，記作(vi,vj)，表示方向從點(diǎn)vi指向點(diǎn)vj，有向圖是點(diǎn)與弧的集合，記作D(V,A)?；?vi,vj)的最大通過能力，稱為該弧的容量，記為c(vi,vj)，或簡記為cij。定義了弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)。容量網(wǎng)絡(luò)通常規(guī)定一個(gè)發(fā)點(diǎn)(源點(diǎn)，記為s)一個(gè)收點(diǎn)(匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其余的點(diǎn)稱為中間點(diǎn)。從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量稱為最大流。多個(gè)收(發(fā))點(diǎn)的網(wǎng)絡(luò)可以轉(zhuǎn)換為只含一個(gè)收(發(fā))點(diǎn)。2.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，對加在弧(vi,vj)上的負(fù)載量記作f(vi,vj)，或簡記作fij，若網(wǎng)絡(luò)上所有的fij=0，這個(gè)流稱為零流。以v(f)表示網(wǎng)絡(luò)中從s→t的流量，則零流是可行流，求最大流就是求v(f)的最大值。稱網(wǎng)絡(luò)上滿足下述條件(1)、(2)的流為可行流：(1)容量限制條件:對所有弧有0≤f(vi,vj)

≤c(vi,vj)(2)中間點(diǎn)平衡條件：∑f(vi,vj)-∑f(vj,vi)

=0(i≠s,t)二.割和流量割(集）是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使s→t的流中斷的一組弧的集合（截集）弧旁數(shù)字為cij(fij)有不同的割見教材162頁上圖中KK將網(wǎng)絡(luò)上的點(diǎn)分割成V和兩個(gè)集合，并有s∈V,t∈，稱弧的集合(V,)={(v1,v3),(v2,v4)}是一個(gè)割。注意，這里不包含(v3,v2)。割的容量是組成它的集合中各弧容量之和，用c(V,)表示，

f(V,)表示通過割(V,)中所有V→方向弧的流量的總和;f(,V)表示通過割中所有→V方向弧的流量的總和，則有：從s→t的流量等于通過割的從V→的流量減→V的流量，有：用v*(f)表示網(wǎng)絡(luò)中從s→t的最大流，則有因此，上例中最大流不會(huì)超過14（所有割集中最小者）。三.最大流最小割定理增廣鏈：如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條鏈上：所有指向?yàn)閟→t的弧（稱前向弧，記作μ+），存在f<c(非飽和)；（正向弧不飽和）所有指向?yàn)閠→s的?。ǚQ后向弧，記為μ

-），存在f>0(非零)，（反向弧非零流）這樣的鏈稱增廣鏈。當(dāng)有增廣鏈存在時(shí)，找出再令顯然，經(jīng)過計(jì)算后f’仍然為可行流，但較原來的可行流f流量增大了θ。因此，只有當(dāng)網(wǎng)絡(luò)圖中找不到增廣鏈時(shí)，s→t流才不可能進(jìn)一步增大。三.求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法

Ford-Fulkerson標(biāo)號(hào)算法，其本質(zhì)是判斷是否存在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；若不存在，則說明已達(dá)到最大流。第一步：首先給發(fā)點(diǎn)s標(biāo)號(hào)(0,ε(s))。第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)，因s是發(fā)點(diǎn)，因此記為0。第二個(gè)數(shù)字ε(s)表示從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值，s為發(fā)點(diǎn)，不限允許調(diào)整容量，故ε(s)=∞。第二步：列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：考慮從標(biāo)號(hào)點(diǎn)i出發(fā)的弧(i,j)（即正向弧)，如果有fij=cij，不給點(diǎn)j標(biāo)號(hào)；若fij<cij，則對j標(biāo)號(hào)，記為(i,ε(j))，其中

ε(j)=min{ε(i),(cij-fij)}考慮所有指向標(biāo)號(hào)點(diǎn)i的弧(h,i)（即反向弧)

，如果有fhi=0，對h不標(biāo)號(hào)，若fhi>0，則對h點(diǎn)標(biāo)號(hào)，記為(i,ε(h))，其中ε(h)=min{ε(i),fhi)}.如果某未標(biāo)號(hào)點(diǎn)k有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，可按(1),(2)中所述規(guī)則分別計(jì)算出ε(k)的值，并取其中的最大的一個(gè)標(biāo)記。第三步：重復(fù)第二步可能出現(xiàn)如下兩種結(jié)果：

1.標(biāo)號(hào)過程中斷，t得不到標(biāo)號(hào)，說明該網(wǎng)絡(luò)中不存在增廣鏈，給定流量即為最大流量。記已標(biāo)號(hào)點(diǎn)集為V，未標(biāo)號(hào)點(diǎn)集為，(V,)為網(wǎng)絡(luò)的最小割。t得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找到一條從s→t的有標(biāo)號(hào)點(diǎn)以及相應(yīng)的弧連接而成的增廣鏈。第四步：修改流量。設(shè)原圖中可行流為f，令這樣得到網(wǎng)絡(luò)上的一個(gè)新的可行流f’。第五步：抹掉圖上所有標(biāo)號(hào)，重復(fù)第一到第四步。注意：在求解步驟中，第三步起到控制運(yùn)算停止的作用，而不是第五步。例：用標(biāo)號(hào)法求下述網(wǎng)絡(luò)圖

s→t的最大流量，并找出該網(wǎng)絡(luò)圖的最小割。解：(1)先給s

點(diǎn)標(biāo)號(hào)(0,∞)；(2)從s點(diǎn)出發(fā)的弧(s,v2)，因有fs2<cs2，且ε(v2)=min{ε(s),(cs2-fs2)}=2故對v2

點(diǎn)標(biāo)號(hào)(s,2)。

(s,v1)飽和，不標(biāo)號(hào)。(3)弧(v1,v2)，因有f12>0

，且ε(v1)=min{ε(v2),f12)}=2故對v1

點(diǎn)標(biāo)號(hào)(v2

,2)。

(v2,v4)飽和，不標(biāo)號(hào)。(4)弧(v1,v3)，因有f13<c13，且ε(v3)=min{ε(v1),(c13-f13)}=2故對v3

點(diǎn)標(biāo)號(hào)(v1

,2)。(5)弧(v4,v3)，因有f43>0

，且ε(v4)=min{ε(v3),f43)}=1故對v4

點(diǎn)標(biāo)號(hào)(v3

,1)。

(v3,t)飽和，不標(biāo)號(hào),v2已標(biāo)號(hào)。(6)弧(v4,t)，因有f4t<c4t

，且ε(t)=min{ε(v4),(c4t-f4t)}=1故對t

點(diǎn)標(biāo)號(hào)(v4

,1)。(7)由于收點(diǎn)t

得到標(biāo)號(hào)，用反追蹤法找出網(wǎng)絡(luò)圖上的一條增廣鏈。(8)修改增廣鏈上各弧的流量：非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡(luò)圖上的一個(gè)新的可行流。重復(fù)上述標(biāo)號(hào)過程，由于對點(diǎn)s、v1、v2、v3標(biāo)號(hào)后，標(biāo)號(hào)中斷，故圖中的可行流即為最大流，v*(f)=14已標(biāo)號(hào)點(diǎn)集為V={s,v1,v2,v3}，未標(biāo)號(hào)點(diǎn)集，(V,)={(3,t),(2,4)}為網(wǎng)絡(luò)的最小割。五，“復(fù)雜”圖論問題“復(fù)雜”：不太可能找到多項(xiàng)式時(shí)間算法最小覆蓋問題最小控制集問題最大獨(dú)立集問題旅行商問題。。。。。。系統(tǒng)監(jiān)控模型

定義1設(shè)圖G=(V,E),KV如果圖G的每條邊都至少有一個(gè)頂點(diǎn)在K中,則稱K是G的一個(gè)點(diǎn)覆蓋.

若G的一個(gè)點(diǎn)覆蓋中任意去掉一個(gè)點(diǎn)后不再是點(diǎn)覆蓋,則稱此點(diǎn)覆蓋是G的一個(gè)極小點(diǎn)覆蓋.

頂點(diǎn)數(shù)最少的點(diǎn)覆蓋,稱為G的最小點(diǎn)覆蓋.例如,右圖中,{v0,v2,v3,v5,v6}等都是極小點(diǎn)覆蓋.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小點(diǎn)覆蓋.系統(tǒng)監(jiān)控問題之一

假設(shè)v1,v2,…,v7是7個(gè)哨所,監(jiān)視著11條路段(如下圖所示),為節(jié)省人力,問至少需要在幾個(gè)哨所派人站崗,就可以監(jiān)視全部路段?

這就是要求最小點(diǎn)覆蓋問題.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小點(diǎn)覆蓋,所以至少需要在4個(gè)哨所派人站崗來監(jiān)視全部路段.

到目前為止,還沒有找到求最小點(diǎn)覆蓋的有效算法,即多項(xiàng)式時(shí)間算法(算法步數(shù)不超過nc,n為G的頂點(diǎn)數(shù),c為常數(shù)).有一些啟發(fā)式近似算法.最大獨(dú)立點(diǎn)集

定義2設(shè)圖G=(V,E),IV如果I中任意兩個(gè)頂點(diǎn)在G中都不相鄰,則稱I是G的一個(gè)獨(dú)立點(diǎn)集.

若G的一個(gè)獨(dú)立點(diǎn)集中,任意添加一個(gè)點(diǎn)后不再是獨(dú)立點(diǎn)集,則稱此獨(dú)立點(diǎn)集是G的一個(gè)極大獨(dú)立點(diǎn)集.

頂點(diǎn)數(shù)最多的獨(dú)立點(diǎn)集,稱為G的最大獨(dú)立點(diǎn)集.例如,右圖中,{v1,v4}等都是極大獨(dú)立點(diǎn)集.{v1,v3,v5},{v2,v2,v6}

是最大獨(dú)立點(diǎn)集.最小控制集

定義3設(shè)圖G=(V,E),DV如果v∈V,要么v∈D,要么v與D的某個(gè)點(diǎn)相鄰,則稱D是G的一個(gè)控制集.

若G的一個(gè)控制集中任意去掉一個(gè)點(diǎn)后不再是控制集,則稱此控制集是G的一個(gè)極小控制集.

頂點(diǎn)數(shù)最少的控制集,稱為G的最小控制集.例如,右圖中,{v1,v3,v5}是極小控制集,{v0}是最小控制集.系統(tǒng)監(jiān)控問題之二

假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1,v2,…,v7表示被指揮的單位,邊表示可以直接下達(dá)命令的通信線路.欲在某些單位建立指揮站,以便可以通過指揮站直接給各單位下達(dá)命令,問至少需要建立幾個(gè)指揮站?

這就是要求最小控制集問題.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2個(gè)單位建立指揮站.

到目前為止,還沒有找到求最小控制集的有效算法..最小點(diǎn)覆蓋、最大獨(dú)立點(diǎn)集和最小控制集的關(guān)系

定理1設(shè)無向圖G=(V,E)中無孤立點(diǎn)(不與任何邊關(guān)聯(lián)的點(diǎn)),若D是G中極大獨(dú)立點(diǎn)集,則D是G中極小控制集.

定理2設(shè)無向圖G=(V,E)中無孤立點(diǎn),KV,則K是G的點(diǎn)覆蓋當(dāng)且僅當(dāng)Kc=V\K是G的獨(dú)立點(diǎn)集.

推論設(shè)無向圖G=(V,E)中無孤立點(diǎn),KV,則K是G的最小(極小)點(diǎn)覆蓋當(dāng)且僅當(dāng)Kc=V\K是G的最大(極大)獨(dú)立點(diǎn)集.旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線？即：從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地（最小哈密爾頓回路）對于n個(gè)節(jié)點(diǎn)的旅行商問題，n個(gè)節(jié)點(diǎn)的任意一個(gè)全排列都是問題的一個(gè)可能解（假設(shè)任意兩個(gè)點(diǎn)之間都有邊）。G個(gè)節(jié)點(diǎn)的全排列有(n-1)!個(gè)，因此間題歸結(jié)為在(n-1)!個(gè)回路中選取最小回路。目錄一，引例二，基本圖論概念三，圖的表示四，“簡單”圖論問題五，“困難”圖論問題六，現(xiàn)代圖論算法七，例子：最大團(tuán)問題八，習(xí)題六，現(xiàn)代圖論算法圖論問題大多隸屬于組合優(yōu)化，解空間是離散的。例：旅行商問題的解空間大小為n!傳統(tǒng)求解策略：1，窮舉（回溯法）2，有技巧的窮舉（如分枝定界法）現(xiàn)代圖論算法現(xiàn)代的求解策略：1，貪心算法2，爬山法3，近似算法4，隨機(jī)算法5，遺傳算法6，模擬退火7，蟻群。。。。。。注：以上算法的分類有重合！貪心算法原理：每一步都做出當(dāng)前最優(yōu)的選擇。例子：1，最小生成樹2，找零錢但是，貪心法不一定找到全局最優(yōu)！例如：旅行商問題爬山法爬山算法是一種簡單的貪心搜索算法。該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏點(diǎn)無論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。近似算法通常需要考慮算法的近似比：最小化問題：Alg(I)<=r*OPT(I)最大化問題：r*Alg(I)>=OPT(I)即保證：r>=1近似算法調(diào)度問題（Scheduling）例：三臺(tái)機(jī)器，作業(yè)用時(shí)：2,3,4,6,2,2（貪心法）總時(shí)間：T=8（最優(yōu)解）總時(shí)間：T=762M123M224M36M124M2223M3近似算法（貪心法分析）假設(shè)有m臺(tái)機(jī)器，最后一臺(tái)機(jī)器用時(shí)最長，最后一臺(tái)機(jī)器的最后一項(xiàng)作業(yè)用時(shí)t_j,則t_j<=T_opt最后一臺(tái)機(jī)器的其他作業(yè)總用時(shí)t,則t<=(\sumt_j)/m<=T_opt所以Alg(I)=t+t_j<=2*T_opt近似比為2.隨機(jī)算法在搜索解空間時(shí)，為了跳出局部最優(yōu)解，可以隨機(jī)地作出一些不是最優(yōu)的選擇。例：3-SAT問題（合取范式可滿足問題）(x1+x2+x3)*(x1+x3+x4)*(x2+x3+x4)可否存在使其為真的賦值？若隨機(jī)賦值，則每個(gè)子句為假的概率為1/8，那么為真的概率為7/8，所以隨機(jī)賦值滿足的子句的個(gè)數(shù)的期望值不少于最優(yōu)值的7/8。隨機(jī)算法其他例子：RSA算法中，要生成大的素?cái)?shù)，如何判斷其素性？用隨機(jī)算法！遺傳算法(Geneticalgorithm)依靠群體智慧，“適者生存”，強(qiáng)大的個(gè)體才能生存下來，繁衍下一代。遺傳算法編碼：將問題的解空間抽象為個(gè)體的集合，每個(gè)個(gè)體為一個(gè)定長的01串。如：0000001110000000010000基本步驟：選擇，交叉，變異選擇(choose)可以有不同的選擇策略：1，選擇最好的；2，隨機(jī)選擇較好的個(gè)體；（輪盤賭）3，替他策略。。?！拜啽P賭策略”(RouletteWheelSelection)：假設(shè)群體的個(gè)體總數(shù)是n，那么那么一個(gè)體Xi被選中的概率為f(Xi)/(f(X1)+f(X2)+……..+f(Xn))其中f(.)是適應(yīng)度函數(shù)，非負(fù)，衡量每個(gè)解的最優(yōu)性，越大越好。適應(yīng)度越大，被選上的概率也就越大。intRWS(){m=0;r=Random(0,1);//r為0至1的隨機(jī)數(shù)

for(i=1;i<=N;i++){

/*產(chǎn)生的隨機(jī)數(shù)在m~m+P[i]間則認(rèn)為選中了i*因此i被選中的概率是P[i]*/m=m+P[i];if(r<=m)returni;}}交叉（Crossover）由兩個(gè)解來生成下一代的兩個(gè)解，生成的方式可由具體問題作出調(diào)整：例：交叉前：00000|011100000000|1000011100|000001111110|00101交叉后：00000|000001111110|1000011100|011100000000|00101變異（Mutate）在繁殖過程，新產(chǎn)生的染色體中的基因會(huì)以一定的概率出錯(cuò)，稱為變異。例：變異前：000001110000000010000變異后：000001110000100010000如何設(shè)計(jì)變異概率是算法設(shè)計(jì)的藝術(shù)！基本遺傳算法偽代碼/**Pc：交叉發(fā)生的概率*Pm：變異發(fā)生的概率*M：種群規(guī)模*G：終止進(jìn)化的代數(shù)*Tf：進(jìn)化產(chǎn)生的任何一個(gè)個(gè)體的適應(yīng)度函數(shù)超過Tf，則可以終止進(jìn)化過程*/初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Popdo{計(jì)算種群Pop中每一個(gè)體的適應(yīng)度F(i)。初始化空種群newPopdo{根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個(gè)個(gè)體if(random(0,1)<Pc){對2個(gè)個(gè)體按交叉概率Pc執(zhí)行交叉操作}if(random(0,1)<Pm){對2個(gè)個(gè)體按變異概率Pm執(zhí)行變異操作}將2個(gè)新個(gè)體加入種群newPop中}until(M個(gè)子代被創(chuàng)建)用newPop取代Pop}until(任何染色體得分超過Tf，或繁殖代數(shù)超過G)遺傳算法包含選擇，交叉和變異三個(gè)過程，如果下一代解的產(chǎn)生方式由交叉推廣到其他一些更一般的策略，則稱這樣的算法為進(jìn)化算法。進(jìn)化算法(Evolutionaryalgorithm)：選擇，生成下一代解，變異。模擬退火算法(Simulatedannealing)貪心法每次都選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。“一定的概率”：初期接受差解的概率比較大，后期接受差解的概率比較?。ㄅc工業(yè)上的金屬冶煉退火有關(guān)）

偽代碼/**J(y)：在狀態(tài)y時(shí)的評價(jià)函數(shù)值*Y(i)：表示當(dāng)前狀態(tài)*Y(i+1)：表示新的狀態(tài)*r：用于控制降溫的快慢*T：系統(tǒng)的溫度，系統(tǒng)初始應(yīng)該要處于一個(gè)高溫的狀態(tài)*T_min：溫度的下限，若溫度T達(dá)到T_min，則停止搜索*/while(T>T_min){dE=J(Y(i+1))-J(Y(i));if(dE>=0)//表達(dá)移動(dòng)后得到更優(yōu)解，則總是接受移動(dòng)Y(i+1)=Y(i);//接受從Y(i)到Y(jié)(i+1)的移動(dòng)else{

//函數(shù)exp(dE/T)的取值范圍是(0,1)，dE/T越大，則exp(dE/T)也越大if(exp(dE/T)>random(0,1))Y(i+1)=Y(i);//接受從Y(i)到Y(jié)(i+1)的移動(dòng)}T=r*T;//降溫退火，0<r<1。r越大，降溫越慢；r越小，降溫越快

/**若r過大，則搜索到全局最優(yōu)解的可能會(huì)較高，但搜索的過程也就較長。若r過小，則搜索的過程會(huì)很快，但最終可能會(huì)達(dá)到一個(gè)局部最優(yōu)值*/i++;}七，例子：最大團(tuán)問題最大團(tuán)問題（maxcliqueproblem）:對于給定圖G=(V,E)。圖G的團(tuán)就是G的一個(gè)完全子圖的頂點(diǎn)集合。頂點(diǎn)最多的極大團(tuán)，稱之為圖G的最大團(tuán)。最大團(tuán)問題的目標(biāo)就是要找到給定圖的最大團(tuán)。七，例子：最大團(tuán)問題七，例子：最大團(tuán)問題1,進(jìn)化算法Q.Zhang,J.Sun,andE.Tsang,“Anevolutionaryalgorithmwithguidedmutationforthemaximumcliqueproblem,”EvolutionaryComputation,IEEETransactionson,vol.9,no.2,pp.192–200,2005.七，例子：最大團(tuán)問題2，模擬退火X.Geng,J.Xu,J.Xiao,andL.Pan,“Asimplesimulatedannealingalgorithmforthemaximumcliqueproblem,”InformationSciences,vol.177,no.22,pp.5064–5071,2007.七，例子：社團(tuán)發(fā)現(xiàn)現(xiàn)代的圖論難題社團(tuán)發(fā)現(xiàn)圖分解圖聚類更多的圖挖掘問題。。。。問題本身并沒有統(tǒng)一的目標(biāo)函數(shù)，只有一些訓(xùn)練集來檢驗(yàn)！138MartinRosvall,CarlT.Bergstrom,PNAS,vol.105,no.4.1118-1123,2007自然科學(xué)論文引用網(wǎng)絡(luò)：6128期刊,約600萬次引用，劃分為88個(gè)模塊和3024條模塊間的連接，刻畫了學(xué)科之間的聯(lián)系139一個(gè)社會(huì)網(wǎng)絡(luò)的例子1970年美國大學(xué)里的一個(gè)空手道俱樂部關(guān)系網(wǎng)絡(luò)：節(jié)點(diǎn)是其34名成員，邊是他們兩年間的友誼關(guān)系，邊數(shù)為78。俱樂部里的矛盾導(dǎo)致其分裂為兩個(gè)小的俱樂部。問題是能否用網(wǎng)絡(luò)的模塊結(jié)構(gòu)來重現(xiàn)這個(gè)過程？它是模塊探測研究中的經(jīng)典例子。W.W.Zachary,Aninformationflowmodelforconflictandfissioninsmallgroups,JournalofAnthropologicalResearch

33,452-4731977Footballteamnetwork八，習(xí)題已知某個(gè)QQ群中有34個(gè)人，他們兩兩之間聊天的次數(shù)如下表所示，成員編號(hào)從1開始。（1）該QQ群中成員因內(nèi)部矛盾分裂，獨(dú)立為兩個(gè)團(tuán)體，請根據(jù)聊天次數(shù)推測分裂后的團(tuán)隊(duì)構(gòu)成；（2）若該QQ群分裂為三個(gè)團(tuán)體，那么各團(tuán)隊(duì)成員構(gòu)成又如何？注：分裂后的團(tuán)隊(duì)之間互不相交。A=[0453333220231300020202000000