版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第四篇 圖論
圖論是近年來(lái)發(fā)展迅速而又應(yīng)用廣泛的一門(mén)新興學(xué)科。它最早起源于一些數(shù)學(xué)游戲的難題研究,如1736年歐拉(L.Euler)所解決的哥尼斯堡七橋問(wèn)題。以及在民間廣為流傳的一些游戲問(wèn)題:例如迷宮問(wèn)題、棋盤(pán)上馬的行走路線(xiàn)問(wèn)題等等。這些古老的問(wèn)題當(dāng)時(shí)吸引了許多學(xué)者的注意,從而在這些問(wèn)題研究的基礎(chǔ)上,又提出了著名的四色猜想和環(huán)游世界各國(guó)的問(wèn)題。例:用定理解決哥尼斯堡橋的問(wèn)題
第四篇 圖論
圖論不斷發(fā)展,它在解決運(yùn)籌學(xué),網(wǎng)絡(luò)理論,信息論,控制論,博奕論以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域的問(wèn)題時(shí),顯示出越來(lái)越大的效果。對(duì)于這樣一門(mén)應(yīng)用廣泛的學(xué)科,其包含的內(nèi)容是豐富的,本篇我們只準(zhǔn)備介紹基本的概念和定理,為今后有關(guān)學(xué)科及課程的學(xué)習(xí)和研究提供方便。WWW電力網(wǎng)因特網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——技術(shù)網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的事例——社會(huì)網(wǎng)絡(luò)朋友關(guān)系網(wǎng)演員網(wǎng)科學(xué)家合著網(wǎng)科學(xué)引文網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——交通運(yùn)輸網(wǎng)絡(luò)城市公共交通網(wǎng)道路交通網(wǎng)航空網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——生物網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)生態(tài)網(wǎng)絡(luò)蛋白質(zhì)相互作用網(wǎng)絡(luò)基因網(wǎng)絡(luò)新陳代謝網(wǎng)絡(luò)SantaFe研究所的科學(xué)家合作網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——科學(xué)家合作網(wǎng)經(jīng)濟(jì)物理學(xué)科學(xué)家合作網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——科學(xué)家合作網(wǎng)復(fù)雜網(wǎng)絡(luò)的事例——中藥方劑網(wǎng)示意圖點(diǎn)(藥材),邊(藥材之間相互作用),局域世界(方劑)§1圖的基本概念定義:
圖(graph)G由一個(gè)三元組<V(G),E(G),G>表示,其中:非空集合V(G)={v1,v2,…,vr}
稱(chēng)為圖G的結(jié)點(diǎn)集,其成員vi(i=1,2,…,r)稱(chēng)為結(jié)點(diǎn)或頂點(diǎn)(nodes
orvertices);集合E(G)={e1,e2,…,es}
稱(chēng)為圖G的邊集,其成員ej(j=1,2,…s)稱(chēng)為邊(edges)。函數(shù)G
:E(G)→(V(G),V(G))
,稱(chēng)為邊與頂點(diǎn)的關(guān)聯(lián)映射(associatvemapping)§1圖的基本概念例:G=<V(G),E(G),G>其中V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6},G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d)abcde1e2e3e4e5e6§1圖的基本概念
討論定義:
(1)V(G)={V1,V2,…,Vn}為有限非空集合,Vi稱(chēng)為結(jié)點(diǎn),簡(jiǎn)稱(chēng)V是點(diǎn)集。
(2)E(G)={e1,…,em}為有限的邊集合,ei稱(chēng)邊,每個(gè)ei都有V中的結(jié)點(diǎn)對(duì)與之相對(duì)應(yīng),稱(chēng)E為邊集。即每條邊是連結(jié)V中的某兩個(gè)點(diǎn)的?!?圖的基本概念(3)若G中每一條邊e與有序偶對(duì)<vi,vj>或無(wú)序偶對(duì)(vi,vj)相關(guān)聯(lián),則可說(shuō)邊e連接結(jié)點(diǎn)vi和vj(4)可用e=<vi,vj>或e=(vi,vj),以結(jié)點(diǎn)來(lái)表示圖的邊,這樣可把圖簡(jiǎn)化成:G=<V,E>。例:有圖如下,試寫(xiě)成定義表達(dá)式G=〈V,E〉,其中V={v1,v2,v3,v4,v5}E={x1,x2,x3,x4,x5,x6}§1圖的基本概念例:對(duì)有向圖可表示為:G=〈V、E〉,其中V={a、b、c、d}E={<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>}§1圖的基本概念下面定義一些專(zhuān)門(mén)名詞:(1)有向邊:若邊ej與結(jié)點(diǎn)序偶<vj,vk>關(guān)聯(lián),那么稱(chēng)該邊為有向邊。(2)無(wú)向邊:若邊ej與結(jié)點(diǎn)無(wú)序偶(vj,vk)關(guān)聯(lián),那么稱(chēng)該邊為無(wú)向邊?!?圖的基本概念(3)鄰接結(jié)點(diǎn):由一條邊(有向或無(wú)向)連接起來(lái)的結(jié)點(diǎn)偶對(duì)。(4)(n,e)圖:具有n個(gè)結(jié)點(diǎn)(頂點(diǎn)),e條邊的圖?!?圖的基本概念(5)有向圖:在G中每一條邊均為有向邊。(6)無(wú)向圖:每條邊均為無(wú)向邊的圖。(7)混合圖:有些邊是無(wú)向邊,有些邊是有向邊的圖稱(chēng)為混合圖?!?圖的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)無(wú)向圖(b)有向圖(c)混合圖(孤立點(diǎn))v2v3環(huán)§1圖的基本概念(8)點(diǎn)和邊的關(guān)聯(lián):如ei=(u,v)或ei=<u,v>稱(chēng)u,v與ei關(guān)聯(lián)。(9)點(diǎn)與點(diǎn)的相鄰:關(guān)聯(lián)于同一條邊的結(jié)點(diǎn)稱(chēng)為鄰接點(diǎn)。(10)邊與邊的鄰接:關(guān)聯(lián)于同一結(jié)點(diǎn)的邊稱(chēng)為鄰接邊。§1圖的基本概念(11)孤立結(jié)點(diǎn):不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱(chēng)為孤立結(jié)點(diǎn)。(12)零圖:僅有孤立結(jié)點(diǎn)的圖。(13)平凡圖:僅有一個(gè)孤立結(jié)點(diǎn)的圖。(14)自回路(環(huán)):關(guān)聯(lián)于同一結(jié)點(diǎn)的邊稱(chēng)為自回路,或稱(chēng)為環(huán)?!?圖的基本概念(15)
平行邊:在有向圖中,始點(diǎn)和終點(diǎn)均相同的邊稱(chēng)為平行邊,無(wú)向圖中若兩點(diǎn)間有多條邊,稱(chēng)這些邊為平行邊,兩點(diǎn)間平行邊的條數(shù)稱(chēng)為邊的重?cái)?shù)。
定義:在圖G=<V,E>,vV,與結(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)稱(chēng)為該點(diǎn)的度數(shù),記為deg(v)。孤立結(jié)點(diǎn)的度數(shù)為0。圖G最大度記為(G)=max{deg(v)|vV(G)},最小度數(shù)記為(G)=min{deg(v)|vV(G)}§1圖的基本概念
定義:在有向圖中,vV,以v為始點(diǎn)的邊數(shù)稱(chēng)為該結(jié)點(diǎn)的出度,記作deg+(v);以v為終點(diǎn)的邊數(shù)稱(chēng)為該結(jié)點(diǎn)的入度,記作deg-(v)。顯然有
deg(v)=deg+(v)+deg-(v)如:G1是無(wú)向圖,deg(v1)=3,deg(v2)=1G2是有向圖,deg+(v1)=2,deg-(v1)=3,deg(v1)=5,v1v2G1v1v3v4v2G2定理:每個(gè)圖中,結(jié)點(diǎn)度數(shù)總和等于邊數(shù)的兩倍。即deg(v)=2|E|vV
定理:在任何圖中,度數(shù)為奇數(shù)的結(jié)點(diǎn)必定是偶數(shù)個(gè)。定理:在任何有向圖中,所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)的出度之和。定義:含有平行邊的圖稱(chēng)為多重圖。簡(jiǎn)單圖:不含平行邊和環(huán)的圖稱(chēng)為簡(jiǎn)單圖。定義:簡(jiǎn)單圖G=<V,E>中,若每一對(duì)結(jié)點(diǎn)間均有邊相連,則稱(chēng)該圖為完全圖。有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為Kn。定理:在任何圖中,n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為n(n-1)/2。無(wú)向完全圖:每一條邊都是無(wú)向邊不含有平行邊和環(huán)每一對(duì)結(jié)點(diǎn)間都有邊相連證明:n個(gè)結(jié)點(diǎn)中任取兩個(gè)結(jié)點(diǎn)的組合數(shù)為
Cn2
=
n(n-1)/2故的邊數(shù)為
|E|=n(n-1)/2定義:給定一個(gè)簡(jiǎn)單圖G,由G中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成的圖,稱(chēng)為G的相對(duì)于完全圖的補(bǔ)圖,或簡(jiǎn)稱(chēng)為G的補(bǔ)圖,記為G。即G=<V,E1>,G=<V,E2>,其中E2={(u,v)u,vV,(u,v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖K5(b)圖G(c)圖G的補(bǔ)圖G’定義:設(shè)圖G=<V,E>,如果有圖G’=<V’,E’>,且E’E,V’V,則稱(chēng)G’為G的子圖。當(dāng)V’=V時(shí),則稱(chēng)G’為G的生成子圖。相對(duì)于圖G的補(bǔ)圖定義:設(shè)G’=<V’,E’>是G=<V,E>的子圖,若給定另一個(gè)圖G”=<V”,E”>使得E”=E-E’,且V”中僅包含E”的邊所關(guān)聯(lián)的結(jié)點(diǎn),則稱(chēng)G”是子圖G’相對(duì)于圖G的補(bǔ)圖。定義:設(shè)圖G=<V,E>及圖G’=<V’,E’>,如果存在一一對(duì)應(yīng)的映射g:vivi’且e=(vi,vj)(或<vi,vj>)是G的一條邊,當(dāng)且僅當(dāng)e’=(g(vi),g(vj))(或<g(vi),g(vj)>)是G’的一條邊,則稱(chēng)G與G’同構(gòu),記作G≌G’。兩圖同構(gòu)的一些必要條件:1.結(jié)點(diǎn)數(shù)目相同;2.邊數(shù)相等;3.度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。§2路與回路
定義:
給定圖G=<V,E>,設(shè)v0,v1,…,vnV,e1,…,enE,其中ei是關(guān)聯(lián)于結(jié)點(diǎn)vi-1,vi的邊,交替序列v0e1v1e2…envn稱(chēng)為結(jié)點(diǎn)v0到vn的路(擬路徑Pseudopath)
。
v0和vn分別稱(chēng)為路的起點(diǎn)和終點(diǎn),邊的數(shù)目n稱(chēng)作路的長(zhǎng)度。當(dāng)v0=vn時(shí),這條路稱(chēng)作回路(閉路徑closedwalk)。
例如路:v1e2v3e3v2e3v3e4v2e6v5e7v3v5e8v4e5v2e6v5e7v3e4v2v4e8v5e6v2e1v1e2v3v2e1v1e2v3e7v5e6v2§2路與回路
若一條路中所有的邊e1,…,en均不相同稱(chēng)作跡(路徑walk)。若一條路中所有的結(jié)點(diǎn)v0,v1,…,vn均不相同,稱(chēng)作通路(Path)。閉的通路,即除v0=vn之外,其余結(jié)點(diǎn)均不相同的路,稱(chēng)作圈(回路circuit)。
§2路與回路
定理:
在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中,如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路,則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路?!?路與回路
推論:在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中,如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路,則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條邊數(shù)小于n的通路。§2路與回路
定義:
在無(wú)向圖G中,如果從結(jié)點(diǎn)u和結(jié)點(diǎn)v之間若存在一條路,則稱(chēng)結(jié)點(diǎn)u和結(jié)點(diǎn)v是連通的(connected)?!?路與回路
結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集V上的等價(jià)關(guān)系。把子圖G(V1),G(V2),…,G(Vm)稱(chēng)為圖G的連通分支(connectedcomponents),圖G的連通分支數(shù)記為W(G)
。§2路與回路
定義:若圖G只有一個(gè)連通分支,則稱(chēng)G是連通圖。顯然在連通圖中,任意兩個(gè)結(jié)點(diǎn)之間必是連通的?!?路與回路
對(duì)于連通圖,常常由于刪除了圖中的點(diǎn)或邊,而影響了圖的連通性。
刪除結(jié)點(diǎn):所謂在圖中刪除結(jié)點(diǎn)v,即是把v以及與v關(guān)聯(lián)的邊都刪除。刪除邊:所謂在圖中刪除某條邊,即是把該邊刪除。
§2路與回路v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e
定義:設(shè)無(wú)向圖G=<V,E>是連通圖,若有結(jié)點(diǎn)集V1V,使圖G中刪除了V1的所有結(jié)點(diǎn)后,所得到的子圖是不連通圖,而刪除了V1的任何真子集后,所得到的子圖仍是連通圖,則稱(chēng)V1是G的一個(gè)點(diǎn)割集(cut-set
ofnodes)。若某一個(gè)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集,則稱(chēng)該點(diǎn)為割點(diǎn)。sabcdabcdba§2路與回路
點(diǎn)連通度:為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目,也稱(chēng)為連通度,記為k(G)。即k(G)=min{|V1||是G的點(diǎn)割集}稱(chēng)為圖G的點(diǎn)連通度(node-connectivity)?!?路與回路(1)若G是平凡圖則k(G)=0(2)k(Kn)=n-1(3)若圖存在割點(diǎn),則k(G)=1(4)規(guī)定非連通圖的連通度k(G)=0§2路與回路v5v1v2v3v4v5v1v3v4點(diǎn)割集V1={v2}§2路與回路
定義:設(shè)無(wú)向圖G=<V,E>是連通圖,若有邊集E1E,使圖
G中刪除了E1的所有邊后,所得到的子圖是不連通圖,而刪除了E1的任何真子集后,所得到的子圖仍是連通圖,則稱(chēng)E1是G的一個(gè)邊割集(cut-setof
edges)。若某一條邊就構(gòu)成一個(gè)邊割集,則稱(chēng)該邊為割邊或橋。割邊e使圖G滿(mǎn)足W(G-e)>W(G)
。§2路與回路
邊連通度(edge-connectivity)
(G)定義:非平凡圖的邊連通度為
(G)=min{|E1||E1是G的邊割集}
邊連通度
(G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目?!?路與回路(1)若G是平凡圖則(G)=0(2)若G存在割邊,則(G)=1,(3)規(guī)定非連通圖的邊連通度為(G)=0§2路與回路
定理:
對(duì)于任何一個(gè)圖G,有k(G)≤(G)≤δ(G)
。δ(G)=min(deg(v),vV)§2路與回路
若G不連通,則k(G)=(G)=0,故上式成立。若G連通,可分兩步證明上式也成立:
1)先證明(G)≤(G):如果G是平凡圖,則(G)=0≤(G),若G是非平凡圖,則因每一結(jié)點(diǎn)的所有關(guān)聯(lián)邊必含一個(gè)邊割集,(因(G)=min{deg(v)|vV},設(shè)uV使的deg(u)=δ(G),與u相關(guān)聯(lián)的條邊必包含一個(gè)邊割集,至少這條邊刪除使圖不連通。)故(G)≤(G)?!?路與回路
2)再證k(G)≤(G):(a)設(shè)(G)=1,即G有一割邊,顯然這時(shí)k(G)=l,上式成立?!?路與回路
(b)設(shè)(G)≥2,則必可刪去某(G)條邊,使G不連通,而刪去其中(G)-1條邊,它仍是連通的,且有一條橋e=(u,v)。對(duì)(G)-1條邊中的每一條邊都選取一個(gè)不同于u,v的端點(diǎn),把這些端點(diǎn)刪去則必至少刪去(G)-1條邊。若這樣產(chǎn)生的圖是不連通的,則k(G)≤(G)-1<(G),若這樣產(chǎn)生的圖是連通的,則e仍是橋,此時(shí)再刪去u或v就必產(chǎn)生一個(gè)不連通圖,故k(G)≤(G)。由1)和2)得k(G)≤(G)≤(G)?!?路與回路
定理:一個(gè)連通無(wú)向圖G的結(jié)點(diǎn)v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和w,使得結(jié)點(diǎn)u和w的每一條路都通過(guò)v
?!?路與回路
1)先證:v是割點(diǎn)存在結(jié)點(diǎn)u和w的每條路都通過(guò)v
若v是連通圖G=<V,E>割點(diǎn),設(shè)刪去v得到的子圖G’,則G’至少包含兩個(gè)連通分支G1=<V1,E1>和G2=<V2,E2>
。任取uV1,wV2,因?yàn)镚是連通的,故在G中必有一條連結(jié)u和w的路C,但u和w在G’中屬于兩個(gè)不同的連通分支,故u和w必不連通,因此C必須通過(guò)v,故u和w之間的任意一條路都通過(guò)v
。
§2路與回路
2)再證:存在結(jié)點(diǎn)u和w的每條路都通過(guò)v
v是割點(diǎn)若連通圖G中的某兩個(gè)結(jié)點(diǎn)的每一條路都通過(guò)v,則刪去v得到子圖G’
,在G’中這兩個(gè)結(jié)點(diǎn)必然不連通,故v是圖G的割點(diǎn)?!?路與回路
在無(wú)向圖G中,從結(jié)點(diǎn)u到v若存在一條路,則稱(chēng)結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的?!?路與回路
對(duì)于任何一個(gè)有向圖G=<V,E>,從結(jié)點(diǎn)u和到結(jié)點(diǎn)v有一條路,稱(chēng)為從u可達(dá)v??蛇_(dá)性(accesible),是結(jié)點(diǎn)集上的二元關(guān)系,它是自反的和傳遞的,但是一般來(lái)說(shuō)不是對(duì)稱(chēng)的。故可達(dá)性不是等價(jià)關(guān)系。§2路與回路
如果u可達(dá)v,它們之間可能不止一條路,在所有這些路中,最短路的長(zhǎng)度稱(chēng)為u和v之間的距離(或短程線(xiàn)),記作d<u,v>,它滿(mǎn)足下列性質(zhì):
d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>§2路與回路如果從u到v是不可達(dá)的,則通常寫(xiě)成d<u,v>=∞注意:當(dāng)u可達(dá)v,且v也可達(dá)u時(shí),d<u,v>不一定等于d<v,u>§2路與回路有關(guān)距離的概念對(duì)無(wú)向圖也適用,把
D=maxd<u,v>,u,v∈V稱(chēng)作圖的直徑?!?路與回路
定義:
在簡(jiǎn)單有向圖G中,任何一對(duì)結(jié)點(diǎn)間,至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的,則稱(chēng)這個(gè)圖是單側(cè)連通的?!?路與回路
如果對(duì)于圖G中的任何一對(duì)結(jié)點(diǎn)兩者之間是相互可達(dá)的,則稱(chēng)這個(gè)圖是強(qiáng)連通的。如果在圖G中略去邊的方向,將它看成無(wú)向圖后,圖是連通的,則稱(chēng)該圖為弱連通的。顯然,強(qiáng)連通圖→單側(cè)連通圖→弱連通圖。而逆推均不成立。§2路與回路v2v3v4v1(a)強(qiáng)連通v2v3v4v1(b)單側(cè)連通v2v3v4v1(c)弱連通§2路與回路
定理:一個(gè)有向圖是強(qiáng)連通的充分必要條件是G有一個(gè)回路,它至少包含每個(gè)結(jié)點(diǎn)一次?!?路與回路
證明:充分性:如G中有一條有向回路,經(jīng)過(guò)每一點(diǎn)至少一次,則G中任意兩點(diǎn)u,v∈V,u可以沿著該有向回路的一部分的而到達(dá)v,則G是強(qiáng)連通圖。§2路與回路
必要性:任取u,v∈V,圖G是強(qiáng)連通圖,則u→v有有向路,v→u也有有向路,則u→v→u構(gòu)成了一個(gè)有向回路,如果該有向回路沒(méi)有包含w,而u→w,w→u均有有向路,則u→v→u→w→u又是一個(gè)有向回路,一直下去可以將圖中所有的點(diǎn)均包含進(jìn)去?!?路與回路
定義:在簡(jiǎn)單有向圖中,具有強(qiáng)連通性質(zhì)的最大子圖,稱(chēng)為強(qiáng)分圖;具有單側(cè)連通性質(zhì)的最大子圖,稱(chēng)為單側(cè)分圖;具有弱連通性質(zhì)的最大子圖,稱(chēng)為弱分圖。§2路與回路v4v2v3v1(a)v5v4v2v3v1(b)§2路與回路
定理:在有向圖G=<V,E>中,它的每一個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中?!?圖的矩陣表示
圖的鄰接矩陣表示方法
定義:設(shè)G=<V,E>是簡(jiǎn)單有向圖,其中V={v1,v2,…vn}定義一個(gè)nxn的矩陣A,并把其中各元素aij表示成:
則稱(chēng)矩陣A為圖G的鄰接矩陣?!?圖的矩陣表示例:設(shè)圖G=<V,E>如下圖所示討論定義:(1)圖G的鄰接矩陣中的元素為0和1,∴又稱(chēng)為布爾矩陣;(2)圖G的鄰接矩陣中的元素的次序是無(wú)關(guān)緊要的,只要進(jìn)行行和行、列和列的交換,則可得到相同的矩陣?!?圖的矩陣表示∴若有二個(gè)簡(jiǎn)單有向圖,則可得到二個(gè)對(duì)應(yīng)的鄰接矩陣,若對(duì)某一矩陣進(jìn)行行和行、列和列之間的交換后得到和另一矩陣相同的矩陣,則此二圖同構(gòu)。(3)當(dāng)有向圖中的有向邊表示關(guān)系時(shí),鄰接矩陣就是關(guān)系矩陣;(4)零圖的鄰接矩陣稱(chēng)為零矩陣,即矩陣中的所有元素均為0;(5)在圖的鄰接矩陣中,①行中1的個(gè)數(shù)就是行中相應(yīng)結(jié)點(diǎn)的引出次數(shù)②列中1的個(gè)數(shù)就是列中相應(yīng)結(jié)點(diǎn)的引入次數(shù)§3圖的矩陣表示2.矩陣的計(jì)算:§3圖的矩陣表示主對(duì)角線(xiàn)上的數(shù)表示結(jié)點(diǎn)i(或j)的引出次數(shù)。
主對(duì)角線(xiàn)上的數(shù)表示結(jié)點(diǎn)i(或j)的引入次數(shù)?!?圖的矩陣表示表示i和j之間具有長(zhǎng)度為2的路徑數(shù),表示i和j之間具有長(zhǎng)度為3的路徑數(shù),表示i和j之間具有長(zhǎng)度為4的路徑數(shù),§3圖的矩陣表示bij表示從結(jié)點(diǎn)vi到vj有長(zhǎng)度分別為1,2,3,4的不同路徑總數(shù)。此時(shí),bij0,表示從vi到vj是可達(dá)的。§3圖的矩陣表示定義:設(shè)G=<V,E>是簡(jiǎn)單有向圖,其中|V|=n(),定義一個(gè)矩陣P,它的元素為:則P稱(chēng)為圖G的可達(dá)性矩陣。
由可計(jì)算出可達(dá)性矩陣,其方法是:若中(i,j)是非“0”元素,則對(duì)應(yīng),否則。§3圖的矩陣表示定義:設(shè)無(wú)向圖G=<V,E>,
其中,則稱(chēng)B為無(wú)向圖G的完全關(guān)聯(lián)矩陣。
令可達(dá)矩陣表明了圖中任意兩結(jié)點(diǎn)間是否至少存在一條路以及在結(jié)點(diǎn)處是否有回路。從圖G的鄰接矩陣A可以得到可達(dá)矩陣P,即令Bn=A+A2+A3+…+An,再?gòu)腂n中非零元素改為1而零元素不變,這種變換后的矩陣即是可達(dá)矩陣P。§3圖的矩陣表示例:討論定義:(1)完全關(guān)聯(lián)矩陣為布爾矩陣;(2)對(duì)應(yīng)B中行均為0的結(jié)點(diǎn)為孤立結(jié)點(diǎn),只有一個(gè)“1”的行的結(jié)點(diǎn)一定為懸掛的邊,且一定不在任一循環(huán)中全部為1的行的結(jié)點(diǎn)必定聯(lián)結(jié)圖中所有的結(jié)點(diǎn)。3)每一條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),故每一列中只有兩個(gè)1。
4)每一行中元素之和等于該行對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)。
5)兩個(gè)平行邊其對(duì)應(yīng)的兩列相同。
6)同一個(gè)圖當(dāng)結(jié)點(diǎn)或邊的編號(hào)不同時(shí),其對(duì)應(yīng)的矩陣只有行序列序的差別。有向圖的關(guān)聯(lián)矩陣
定義:給定簡(jiǎn)單有向圖G=<V,E>,設(shè)v1,v2,…,vpV,e1,…,eqE,稱(chēng)p×q階矩陣M(G)=(mij)p×q
為圖G的完全關(guān)聯(lián)矩陣(incidencematrix)。其中:1
若vi是
ej的起點(diǎn)。
-1
若vi是
ej的終點(diǎn)。
0若vi不關(guān)聯(lián)
ej。mij=
有向圖的關(guān)聯(lián)矩陣的特點(diǎn):
(1)每一列中有一個(gè)1和一個(gè)-1,對(duì)應(yīng)一邊一個(gè)始點(diǎn)、一個(gè)終點(diǎn),元素和為零。
(2)每一行元素的絕對(duì)值之和為對(duì)應(yīng)點(diǎn)的度數(shù)。-1的個(gè)數(shù)等于入度,1的個(gè)數(shù)等于出度。
有向圖G的兩行相加定義為:第i行第j列的對(duì)應(yīng)元素算術(shù)相加;相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊,合并結(jié)點(diǎn)vi和vj
。合并后得到的新結(jié)點(diǎn)記為vi,j。無(wú)向圖G的兩行相加定義為:第i行第j列的對(duì)應(yīng)元素模2相加;相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊,合并結(jié)點(diǎn)vi和vj
。合并后得到的新結(jié)點(diǎn)記為vi,j。
3、關(guān)聯(lián)矩陣的秩
定理:
如果一個(gè)連通圖G=<V,E>,有r個(gè)結(jié)點(diǎn),則其完全關(guān)聯(lián)矩陣M(G)的秩為r-1,即rankM(G)=r-1
。推論:如果一個(gè)連通圖G=<V,E>,有r個(gè)結(jié)點(diǎn),w個(gè)最大連通子圖,則圖G的完全關(guān)聯(lián)矩陣M(G)的秩為r-w,即rankM(G)=r-w
。
例:寫(xiě)出如圖7-3.11所示的圖G的完全關(guān)聯(lián)矩陣,并驗(yàn)證其秩如定理7-3.2所述。e1e2e3e4e5e6e7e8e9A100001010B011000100C000110010D110000001E000011100F001100001完全關(guān)聯(lián)矩陣為:此圖為連通圖,由定理其秩為5。§4歐拉圖和漢密爾頓圖2.定理7-4.1
無(wú)向圖G具有一條歐拉路,當(dāng)且僅當(dāng)G連通,并且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。1.定義7-4.1
如果無(wú)孤立結(jié)點(diǎn)圖G上有一條經(jīng)過(guò)G的所有邊一次且僅一次的路徑,則稱(chēng)該路徑為圖G的歐拉路徑(Eulerwalk)。如果圖G上有一條經(jīng)過(guò)G邊一次且僅一次的的回路,則稱(chēng)該回路為圖G的歐拉回路,具有歐拉回路的圖稱(chēng)為歐拉圖(Eulergraph)。
由于有了歐拉路和歐拉回路的判別準(zhǔn)則,因此哥尼斯堡七橋問(wèn)題立即有了確切的否定答案,因?yàn)閺膱D中可以看到deg(A)=5,deg(B)=deg(C)=deg(D)=3,故歐拉回路必不存在。3.定理7-4.1的推論
無(wú)向圖G具有一條歐拉路,當(dāng)且僅當(dāng)G連通且所有結(jié)點(diǎn)度數(shù)皆為偶數(shù)。例:用定理解決哥尼斯堡橋的問(wèn)題一筆畫(huà)問(wèn)題要判定一個(gè)圖G是否可一筆畫(huà)出,有兩種情況:一是從圖G中某一結(jié)點(diǎn)出發(fā),經(jīng)過(guò)圖G的每一邊一次僅一次到達(dá)另一結(jié)點(diǎn)。另一種就是從G的某個(gè)結(jié)點(diǎn)出發(fā),經(jīng)過(guò)G的每一邊一次僅一次再回到該結(jié)點(diǎn)。上述兩種情況分別可以由歐拉路和歐拉回路的判定條件予以解決。定義7-4.2:給定有向圖G,通過(guò)圖中每邊一次且僅一次的一條單向路(回路),稱(chēng)作單向歐拉路(回路)??梢詫W拉路和歐拉回路的概念推廣到有向圖中。
定理7-4.2
有向圖G為具有一條單向歐拉回路,當(dāng)且僅當(dāng)G連通,并且每個(gè)結(jié)點(diǎn)的入度等于出度。有向圖G有單向歐拉路,當(dāng)且僅當(dāng)G連通,并且恰有兩個(gè)結(jié)點(diǎn)的入度與出度不等,它們中一個(gè)的出度比入度多1,另一個(gè)入度比出度多1。
例1有向歐拉圖應(yīng)用示例:計(jì)算機(jī)鼓輪的設(shè)計(jì)。鼓輪表面分成24=16等份,其中每一部分分別用絕緣體或?qū)w組成,絕緣體部分給出信號(hào)0,導(dǎo)體部分給出信號(hào)1,在下圖中陰影部分表示導(dǎo)體,空白體部分表示絕緣體,根據(jù)鼓輪的位置,觸點(diǎn)將得到信息4個(gè)觸點(diǎn)a,b,c,d讀出1101(狀態(tài)圖中的邊e13),轉(zhuǎn)一角度后將讀出1010(邊e10)。問(wèn)鼓輪上16個(gè)部分怎樣安排導(dǎo)體及絕緣體才能使鼓輪每旋轉(zhuǎn)一個(gè)部分,四個(gè)觸點(diǎn)能得到一組不同的四位二進(jìn)制數(shù)信息。01111111100000001110abcd
設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)的有向圖,如下圖所示。其結(jié)點(diǎn)分別記為三位二進(jìn)制數(shù){000,001,……,111},設(shè)ai{0,1},從結(jié)點(diǎn)a1a2a3可引出兩條有向邊,其終點(diǎn)分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法,對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊,在這種圖的任一條路中,其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式,即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊的頭三位數(shù)相同。由于圖中16條邊被記為不同的二進(jìn)制數(shù),可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息,即對(duì)應(yīng)于圖中的一條歐拉回路。
設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)的有向圖,如下圖所示。其結(jié)點(diǎn)分別記為三位二進(jìn)制數(shù){000,001,……,111},設(shè)ai{0,1},從結(jié)點(diǎn)a1a2a3可引出兩條有向邊,其終點(diǎn)分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法,對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊,在這種圖的任一條路中,其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式,即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊的頭三位數(shù)相同。由于圖中16條邊被記為不同的二進(jìn)制數(shù),可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息,即對(duì)應(yīng)于圖中的一條歐拉回路。
所求的歐拉回路為:
e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)
(從圖示位置開(kāi)始)
e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6(e13)
所求的二進(jìn)制序列為:
0000100110101111(0)
1101011110000100(1)(從圖示位置開(kāi)始)
上述結(jié)論可推廣到鼓輪具有n個(gè)觸點(diǎn)的情況。構(gòu)造2n-1
個(gè)結(jié)點(diǎn)的有向圖,每個(gè)結(jié)點(diǎn)標(biāo)記為n-1位二進(jìn)制數(shù),從結(jié)點(diǎn)a1a2a3...an-1出發(fā),有一條終點(diǎn)為a2a3...an-10的邊,該邊記為a1a2a3...an-10;還有一條終點(diǎn)標(biāo)記為a2a3...an-11的邊,該邊記為a1a2a3...an-11
。鄰接邊的標(biāo)記規(guī)則為:“第一條邊后n-1位與第二條邊前n-1位二進(jìn)制數(shù)相同”。二、漢密爾頓圖
與歐拉回路類(lèi)似的是漢密爾頓回路。它是1859年漢密爾頓首先提出的一個(gè)關(guān)于12面體的數(shù)學(xué)游戲:能否在圖7-4.6中找到一個(gè)回路,使它含有圖中所有結(jié)點(diǎn)一次且僅一次?若把每個(gè)結(jié)點(diǎn)看成一座城市,連接兩個(gè)結(jié)點(diǎn)的邊看成是交通線(xiàn),那么這個(gè)問(wèn)題就變成能否找到一條旅行路線(xiàn),使得沿著該旅行路線(xiàn)經(jīng)過(guò)每座城市恰好一次,再回到原來(lái)的出發(fā)地?他把這個(gè)問(wèn)題稱(chēng)為周游世界問(wèn)題。定義7-4.3:給定圖G,若存在一條路經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次,這條路稱(chēng)作漢密爾頓路。若存在一條回路,經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次,這條回路稱(chēng)作漢密爾頓回路。具有漢密爾頓回路的圖稱(chēng)作漢密爾頓圖。圖7-4.6存在一條漢密爾頓回路,它是漢密爾頓圖定理7-4.3若圖G=<V,E>具有漢密爾頓回路,則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S均有W(G-S)≤|S|,其中W(G-S)是G-S的連通分支數(shù)。證明設(shè)C是G的一條漢密爾頓回路,對(duì)于V的任何一個(gè)非空子集S,在C中刪去S中任一結(jié)點(diǎn)a1,則C-a1是連通的非回路,W(C-a1)=1,|S|≥1,這時(shí)W(C-S)≤|S|。若再刪去S中另一結(jié)點(diǎn)a2,則W(C-a1-a2)≤2,而|S|≥2,這時(shí)W(C-S)≤|S|。由歸納法可得:W(C-S)≤|S|。同時(shí)C-S是G-S的一個(gè)生成子圖,因而W(G-S)≤W(C-S),所以W(G-S)≤|S|。
此定理是必要條件,可以用來(lái)證明一個(gè)圖不是漢密爾頓圖。
如右圖,取S={v1,v4},則G-S有3個(gè)連通分支,不滿(mǎn)足W(G-S)≤|S|,故該圖不是漢密爾頓圖。
所以用此定理來(lái)證明某一特定圖是非漢密爾頓圖并不是總是有效的。例如,著名的彼得森(Petersen)圖,在圖中刪去任一個(gè)結(jié)點(diǎn)或任意兩個(gè)結(jié)點(diǎn),不能使它不連通;刪去3個(gè)結(jié)點(diǎn),最多只能得到有兩個(gè)連通分支的子圖;刪去4個(gè)結(jié)點(diǎn),只能得到最多三個(gè)連通分支的子圖;刪去5個(gè)或5個(gè)以上的結(jié)點(diǎn),余下子圖的結(jié)點(diǎn)數(shù)都不大于6,故必不能有5個(gè)以上的連通分支數(shù)。所以該圖滿(mǎn)足W(G-S)≤|S|,但是可以證明它是非漢密爾頓圖。說(shuō)明:此定理是必要條件而不是充分條件。有的圖滿(mǎn)足此必要條件,但也是非漢密爾頓圖。下面的定理給出一個(gè)無(wú)向圖具有漢密爾頓路的充分條件
定理7-4.4
設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。證明思路:1)先證G連通:
若G有兩個(gè)或多個(gè)互不連通的分支,設(shè)一個(gè)分圖有n1個(gè)結(jié)點(diǎn),任取一個(gè)結(jié)點(diǎn)v1,另一分圖有n2個(gè)結(jié)點(diǎn),任取一個(gè)結(jié)點(diǎn)v2,因?yàn)閐eg(v1)≤n1-1,deg(v2)≤n2-1,deg(v1)+deg(v2)≤n1+n2-2<n-1,與假設(shè)矛盾,G是連通的。2)先證(構(gòu)造)要求的漢密爾頓路存在:
設(shè)G中有p-1條邊的路,p<n,它的結(jié)點(diǎn)序列為v1,v2,…,vp。如果有v1或vp鄰接于不在這條路上的一個(gè)結(jié)點(diǎn),立刻擴(kuò)展該路,使它包含這個(gè)結(jié)點(diǎn),從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結(jié)點(diǎn),我們證明在這種情況下,存在一條回路包含結(jié)點(diǎn)v1,v2,…,vp。
若v1鄰接于vp,則v1,v2,…,vp即為所求。若v1鄰接于結(jié)點(diǎn)集{vl,vm,…,…,vj,…,vt}中之一,這里2≤l,m,...,j,...,t≤p-1,如果vp是鄰接于vl-1,vm-1,…,…,vj-1,…,vt-1中之一,譬如是vj-1,則v1v2…vj-1vpvp-1...vjv1是所求回路(如圖7-4.9(a)所示)。如果vp不鄰接于vl-1,vm-1,…,…,vj-1,…,vt-1中任一個(gè),則vp最多鄰接于p-k-1個(gè)結(jié)點(diǎn),deg(vp)≤p-k-1,deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1與vp度數(shù)之和最多為n-2,得到矛盾。至此,已經(jīng)構(gòu)造出一條包含結(jié)點(diǎn)v1,v2,…,vp的回路,因?yàn)镚是連通的,所以在G中必有一個(gè)不屬于該回路的結(jié)點(diǎn)vx與回路中某一結(jié)點(diǎn)vk鄰接,如圖7-4.9(b)所示,
于是就得到一條包含p條邊的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…,vj,v1,v2,…,vk-1),如圖7-4.9(c)所示,重復(fù)前述構(gòu)造方法,直到得到n-1條邊的路。例某地有5個(gè)風(fēng)景點(diǎn),若每個(gè)景點(diǎn)均有兩條道路與其他景點(diǎn)相通,問(wèn)是否可經(jīng)過(guò)每個(gè)景點(diǎn)一次而游完這5處。解將景點(diǎn)作為結(jié)點(diǎn),道路作為邊,則得到一個(gè)有5個(gè)結(jié)點(diǎn)的無(wú)向圖。由題意,對(duì)每個(gè)結(jié)點(diǎn)vi(i=1,2,3,4,5)有
deg(vi)=2。則對(duì)任兩點(diǎn)和均有
deg(vi)+deg(vj)=2+2=4=5–1
所以此圖有一條漢密爾頓回路。即經(jīng)過(guò)每個(gè)景點(diǎn)一次而游完這5個(gè)景點(diǎn)。例:在七天內(nèi)安排七門(mén)課程的考試,使得同一位教師所任的兩門(mén)課程不排在接連的兩天中,試證明如果沒(méi)有教師擔(dān)任多于四門(mén)課程,則符合上述要求的考試安排總是可能的。證明:設(shè)G為具有七個(gè)結(jié)點(diǎn)的圖,每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一門(mén)課程考試,如果這兩個(gè)結(jié)點(diǎn)對(duì)應(yīng)的課程考試是由不同教師擔(dān)任的,那么這兩個(gè)結(jié)點(diǎn)之間有一條邊,因?yàn)槊總€(gè)教師所任課程數(shù)不超過(guò)4,故每個(gè)結(jié)點(diǎn)的度數(shù)至少是3,任兩個(gè)結(jié)點(diǎn)的度數(shù)之和至少是6,故G總是包含一條漢密爾頓路,它對(duì)應(yīng)于一個(gè)七門(mén)考試課程的一個(gè)適當(dāng)?shù)陌才拧?.定理7-4.5
設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n,則G中存在一條漢密爾頓回路。證明思路:由定理7-4.4知,必有一條漢密爾頓路,設(shè)為v1,v2,…,vn,若v1與vn鄰接,則定理得證。若v1與vn不鄰接,假設(shè)v1鄰接于{vi1,vi2,…,vik},2≤ij≤n-1,vn必鄰接于vi1-1,vi2-1,…,vik-1中之一。若vn不鄰接于vi1-1,vi2-1,…,vik-1中之一,則vn至多鄰接于n-k-1個(gè)結(jié)點(diǎn),因而,
deg(vn)≤n-k-1,而
deg(v1)=k,
deg(v1)+deg(vn)≤n-k-1+k=n-1,與假設(shè)矛盾,所以必有一條漢密爾頓路v1v2…vj-1vnvn-1…vjv1,如圖7-4.11所示。
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年度事業(yè)單位行政管理人員勞動(dòng)合同示范文本3篇
- 2024年度國(guó)際貿(mào)易實(shí)訓(xùn):實(shí)訓(xùn)出口合同3篇
- 2024版品牌授權(quán)與產(chǎn)品代工合同3篇
- 2024年度應(yīng)急物資儲(chǔ)備與配送合同3篇
- 2024年某電商平臺(tái)服務(wù)外包合同
- 2024年度品牌故事視頻制作與傳播協(xié)議3篇
- 2024年標(biāo)準(zhǔn)化門(mén)窗安裝工程服務(wù)合同版
- 2024年度深圳市商品房買(mǎi)賣(mài)合同2篇
- 2024年標(biāo)準(zhǔn)版工程項(xiàng)目安全消防環(huán)保治安規(guī)范合同書(shū)版B版
- 2024嵊泗海參養(yǎng)殖基地供應(yīng)鏈管理服務(wù)合同3篇
- 交流變換為直流的穩(wěn)定電源(共15頁(yè))
- 構(gòu)造柱及圈梁施工方案
- 升壓站受電前質(zhì)量監(jiān)督檢查實(shí)施大綱
- 《Something Just Like This》歌詞
- 鐵路貨車(chē)廠修規(guī)程
- 電子研發(fā)項(xiàng)目獎(jiǎng)金分配獎(jiǎng)勵(lì)制度
- 數(shù)據(jù)結(jié)構(gòu)大話(huà)《數(shù)據(jù)結(jié)構(gòu)》PPT課件
- 餐飲管理標(biāo)準(zhǔn)培訓(xùn)課件.ppt
- 三國(guó)群英傳7秘籍大全 完整全秘籍編碼匯總
- 倍量左鋒突破前高回踩黃金線(xiàn)選股公式
- 血液內(nèi)科疾病診療指南(新)
評(píng)論
0/150
提交評(píng)論