資源描述：
《離散數(shù)學(xué) 圖論》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、第六章圖論基礎(chǔ)圖是建立和處理離散數(shù)學(xué)模型的一種重要工具。圖論是一門應(yīng)用性很強的學(xué)科。許多學(xué)科，諸如運籌學(xué)、網(wǎng)絡(luò)理論、控制論、化學(xué)、生物學(xué)、物理學(xué)、社會科學(xué)、計算機科學(xué)等，凡是研究事物之間關(guān)系的實際問題或理論問題，都可以建立圖論模型來解決。隨著計算機科學(xué)的發(fā)展，圖論的應(yīng)用也越來越廣泛，同時圖論也得到了充分的發(fā)展。這里將主要介紹與計算機科學(xué)關(guān)系密切的圖論的內(nèi)容。6.1圖的基本概念我們已知集合的笛卡爾積的概念，為了定義無向圖，還需要給出集合的無序積的概念。任意兩個元素a,b構(gòu)成的無序?qū)Γ║norderedpair）記作(a,b)，這里總有。設(shè)為兩個集
2、合，無序?qū)Φ募戏Q為集合A與B的無序積（UnorderedProduct），記作。無序積與有序積的不同在于。例如，設(shè)，，則,。為了引出圖的定義，我們先介紹如下的例子。MHBS圖6.1-1starts=0,i=1i=1i=11?i=i+1s=s+1printsendNY圖6.1-2例6.1-1(1)北京、上海、香港、澳門是中國的幾個著名的城市，分別用字母表示為,城市的集合為，這些城市間現(xiàn)有的航空線的集合是。我們也可以將這些城市間的航空線關(guān)系用圖6.1-1來表示。⑵的程序框圖如圖6.1-21586.1.1圖的定義及相關(guān)概念定義6.1-1一個無向圖(
3、UndirectedGraph)G是一個有序二元組，記作，其中是一個非空集合，V中的元素稱為結(jié)點或頂點（Vertex）；E是無序積的多重子集（元素可重復(fù)出現(xiàn)的集合），稱E為G的邊集(EdgeSet)，E中的元素稱為無向邊或簡稱邊(Edge)。在一個圖中，為了表示V和E分別是圖G的結(jié)點集和邊集，常將V記成，而將E記成。以上給出的是一個無向圖的數(shù)學(xué)定義。它們可以用圖形來表示，而這種圖形有助于我們理解圖的性質(zhì)。在這種表示法中，每個結(jié)點用點來表示，每條邊用線來表示，這樣的線連接著代表該邊端點的兩個結(jié)點。例如,,G的圖形如圖6.1-3所示。圖6.1-4圖
4、6.1-3定義6.1-2 一個有向圖(DirectedGraph)G是一個有序二元組，記作，其中V是一個非空的結(jié)點（或頂點）集；E是笛卡爾積V×V的多重子集，其元素稱為有向邊(DirectedEdge)，也簡稱邊或弧(Arc)。對于一個有向圖G，一般也可畫出圖形來表示。例如，其中,,的圖形為圖6.1-4。給圖的結(jié)點標(biāo)以名稱，如圖6.1-3中的這樣的圖稱為標(biāo)定圖(Labledgraph)。同時也可對邊進(jìn)行標(biāo)定，圖6.1-3中,,,,,.當(dāng)時,稱和是的端點（或頂點）(EndPoint)，并稱與和是關(guān)聯(lián)的(Incidence)，而稱結(jié)點與是鄰接的(A
5、djacent)。若兩條邊關(guān)聯(lián)于同一個結(jié)點，則稱兩邊是鄰接的(Adjacent)。無邊關(guān)聯(lián)的結(jié)點稱為孤立點(Isolatedpoint)；若一條邊關(guān)聯(lián)的兩個結(jié)點重合，則稱此邊為環(huán)(Ring)或自回路(Selfcircuit)。若，則稱與（或）關(guān)聯(lián)的次數(shù)是1;若，稱與關(guān)聯(lián)的次數(shù)為2；若不是的端點，則稱與的關(guān)聯(lián)次數(shù)為0158（或稱e與u不關(guān)聯(lián)）。在圖6.1-3中，,,是的端點，與、的關(guān)聯(lián)次數(shù)均為1，是孤立點，是環(huán)，與關(guān)聯(lián)的次數(shù)為2。當(dāng)是有向邊時，又稱是的始點(InitialPoint)，是的終點(TerminalPoint)。如果圖的結(jié)點集和邊集都
6、是有限集，則稱圖為有限圖(Finitegraph)，本書討論的圖都是有限圖。若圖中,,為了方便起見，這樣的圖也稱為圖，有時也簡稱階圖。這時圖稱為零圖(NullGraph)，圖稱為平凡圖(TrivialGraph)。關(guān)聯(lián)于同一對頂點的兩條邊稱為平行邊(ParallelEdge)（若是有向邊方向應(yīng)相同），平行邊的條數(shù)稱為邊的重數(shù)。不含平行邊和環(huán)的圖稱簡單圖(SimpleGraph)。在本書中除非特別聲明，一般是指簡單圖。6.1.2結(jié)點的度定義6.1-3設(shè)為一無向圖，,關(guān)聯(lián)邊的次數(shù)稱為v的度數(shù)，簡稱度(Degree)，記作的d(v)。設(shè)為一有向圖，,
7、v作為邊的始點的次數(shù)，稱為v的出度(OutDegree)，記作；v作為邊的終點的次數(shù)稱為v的入度(InDegree)，記作；v作為邊的端點的次數(shù)稱為v的度數(shù)，簡稱度(Degree)，記作，顯然。在圖6.1-3中，，，，；在圖6.1-4中，，，,,。稱度為1的結(jié)點為懸掛點(Hangingpoint)，與懸掛點關(guān)聯(lián)的邊稱為懸掛邊(Hangingedge)。如圖6.1-3中，是懸掛點，是懸掛邊。記,,分別稱為圖的最大度(MaxDegree)和最小度(MinDegree)。若是有向圖，除了,，還有如下的定義最大出度最大入度最小出度最小入度圖6.1-4中
8、,,,,,,.例6.1-2在圖6.1-3中而該圖有６條邊，即結(jié)點度數(shù)和是邊數(shù)的２倍。事實上這是圖的一般性質(zhì)。158定理6.1-1設(shè)圖為具有結(jié)點集的圖，
