【正文】 = Σ d+(v)=e 記住了嗎？ 幾個(gè)重要定理 ? 例 證明任何一群人中 ， 有偶數(shù)個(gè)人認(rèn)識(shí)其中奇數(shù)個(gè)人 .(匈牙利數(shù)學(xué)競(jìng)賽試題 ) ? [證 ] 用 n個(gè)頂點(diǎn)表示 n個(gè)人 .如果兩個(gè)人相識(shí) ，就用一條線把他們對(duì)應(yīng)的一對(duì)頂點(diǎn)連起來 ，這樣就得到了一個(gè)圖 的數(shù)目就是他對(duì)應(yīng)的頂點(diǎn)的次 ， 于是問題就轉(zhuǎn)化為證明圖 G中奇點(diǎn)的個(gè)數(shù)為偶數(shù) ， 而這正是定理 . 權(quán)： 是指對(duì)邊賦予的有意義的數(shù)值量。 證明思路：考慮每條邊在求和中的情況。 證明思路：將圖中頂點(diǎn)的次分類，再利用定理 1。 證明思路：考慮每條邊在求和中的貢獻(xiàn)。 圖的邏輯結(jié)構(gòu) 圖的基本術(shù)語 頂點(diǎn)的入度： 在有向圖中 ， 頂點(diǎn) v的 入度 是指以該頂點(diǎn)為弧頭的弧的數(shù)目 ， 記為 ID (v)； 頂點(diǎn) 的 出度： 在有向圖中 ， 頂點(diǎn) v的 出度 是指以該頂點(diǎn)為弧尾的弧的數(shù)目 ， 記為 OD (v)。 V1 V2 V3 V1 V2 V3 V4 圖的基本概念 稀疏圖： 稱邊數(shù)很少的圖為稀疏圖； 稠密圖： 稱邊數(shù)很多的圖為稠密圖 。 圖的基本術(shù)語 V1 V2 V3 V1 V2 V3 V4 圖的基本概念 含有 n個(gè)頂點(diǎn)的無向完全圖有 多少 條邊 ？ 含有 n個(gè)頂點(diǎn)的有向完全圖有 多少 條弧 ？ 含有 n個(gè)頂點(diǎn)的無向完全圖有 n (n1)/2條邊。 F E C B A D 線性結(jié)構(gòu) A B C D E F 樹結(jié)構(gòu) V1 V2 V3 V4 V5 圖結(jié)構(gòu) 不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比 無向完全圖 ：在無向圖中 ， 如果任意兩個(gè)頂點(diǎn)之間都存在邊 ， 則稱該圖為無向完全圖 。 V1 V2 V3 V4 V1的鄰接點(diǎn)： V2 、 V3 V3的鄰接點(diǎn)： V4 圖的基本概念 在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系； 在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系； 在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。 圖的基本概念 圖的基本術(shù)語 鄰接 、 依附 無向圖 中 ， 對(duì)于任意兩個(gè)頂點(diǎn) vi和頂點(diǎn) vj， 若存在邊(vi， vj)， 則稱頂點(diǎn) vi和頂點(diǎn) vj互為鄰接點(diǎn) ， 同時(shí)稱邊(vi， vj)依附于頂點(diǎn) vi和頂點(diǎn) vj。 V1 V2 V3 V4 V5 V1 V2 V3 V4 圖的基本概念 圖的基本術(shù)語 簡(jiǎn)單圖： 在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn) 。 若從頂點(diǎn) vi到 vj的邊有方向，則稱這條邊為 有向邊 ，表示為 vi,vj。 如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是 無向邊 ， 則稱該圖為 無向圖 。 圖的基本概念 圖的定義 圖是由 頂點(diǎn) 的 有窮 非空 集合和頂點(diǎn)之間 邊 的集合組成，通常表示為： G=(V， E) 其中： G表示一個(gè)圖， V是圖 G中頂點(diǎn)的集合， E是圖 G中頂點(diǎn)之間邊的集合。后來也有不少論文討論這個(gè)問題，在理論和應(yīng)用上都很有價(jià)值 。 ? 這是一個(gè)圖論優(yōu)化問題，最早由美國(guó)數(shù)學(xué)家威特涅于 1934年在普林斯頓一次討論班上提出。 ? 正十二面體的頂點(diǎn)與棱的關(guān)系可以用平面上的圖表示 ， 把正十二面體的頂點(diǎn)與棱分別對(duì)應(yīng)圖的頂點(diǎn)與邊 ， 就得到正十二面體圖 。它起源于 1856年 ， 當(dāng)時(shí)英國(guó)數(shù)學(xué)家 Hamilton設(shè)計(jì)了一種名為周游世界的游戲 。 圖論 ——?dú)W拉 能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？ 哥尼斯堡七橋問題 C A D B 七橋問題的圖模型 哥尼斯堡七橋問題 歐拉回路的判定規(guī)則： 兩個(gè)，則不存在歐拉回路； 橋，可以從這兩個(gè)地方之一出發(fā)，找到歐拉回路； 數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。 1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長(zhǎng)，直到 1766年，重回彼得堡，沒有多久，完全失明。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了 886本書籍和論文，其中分析、代數(shù)、數(shù)論占 40%，幾何占 18%，物理和力學(xué)占 28%，天文學(xué)占 11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占 3%。 歐拉 1707年出生在瑞士的巴塞爾城， 19歲開始發(fā)表論文，直到 76歲。 這就是著名的 K246。nigsberg七橋位于前蘇聯(lián)的加里寧格勒 ， 歷史上曾是德國(guó)東普魯士省的省會(huì) ， 霹雷格爾橫 ? 穿城堡 ， 河中有兩個(gè)小島 B與 C， 并有七座橋連接島與河岸及島與島 （ 見圖 ） 。nigsberg七橋問題的論文 ， 這是圖論的第一篇文章 . ? 第二階段 從十九世紀(jì)中葉到二十世紀(jì)中葉 .在此階段，圖論問題大量出現(xiàn) .如著名的四色問題、 Hamilton問題以及圖的可平面問題等 . 在第二個(gè)階段還應(yīng)該特別提到 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域， Kirchhoff用樹去研究電網(wǎng)絡(luò)的分析問題 .在漫長(zhǎng)的 300年中，圖論幾乎停留在數(shù)學(xué)游戲階段 .雖然這階段里 21歲的 在 1847年從電網(wǎng)絡(luò)問題， 1857年從計(jì)算有機(jī)化學(xué)的同分異構(gòu)等不止一次地建立起圖論的基本概念，但是直到 1936年 表的經(jīng)典著作 有限圖與無限圖理論 才有了圖論的第一本專著 . ? 二十世紀(jì)中葉以后是圖論發(fā)展的 第三階段 ，即圖論的應(yīng)用階段 .由于生產(chǎn)管理 、 軍事 、 交通運(yùn)輸 、 計(jì)算機(jī)網(wǎng)絡(luò) 、 計(jì)算機(jī)科學(xué) 、 數(shù)字通訊 、 線性規(guī)劃 、 運(yùn)籌學(xué)等方面提出的實(shí)際問題的需要 ， 特別是許多離散性問題的出現(xiàn) 、刺激和推動(dòng) ， 以及由于有了大型電子計(jì)算機(jī) ，而使大規(guī)模問題的求解成為可能 ， 圖論及其應(yīng)用的研究得到了飛速的發(fā)展 .這個(gè)階段的開創(chuàng)性工作是以 Ford和 Fulkerson建立的網(wǎng)絡(luò)流理論為代表的 .圖論與其它學(xué)科的相互滲透 ，以及圖論在生產(chǎn)實(shí)際中廣泛地應(yīng)用 ， 都使圖論的發(fā)展更加充滿活力 . 幾個(gè)有趣的圖論問題 ? K246。第六章 圖 本章的主要內(nèi)容是 : 圖的基本概念 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷 最小生成樹 最短路徑 AOV網(wǎng)與拓?fù)渑判? AOE網(wǎng)與關(guān)鍵路徑 圖論發(fā)展史 ? 圖論是組合數(shù)學(xué)的一個(gè)分支 ， 也是近幾十年來最活躍的數(shù)學(xué)分支之一 .到目前為止 ， 它已有二百六十多年的發(fā)展歷史 .圖論的發(fā)展歷史大體可以分為三個(gè)階段： ? 第一階段 是圖論的萌芽階段 ， 它從十八世紀(jì)中葉到十九世紀(jì)中葉 .這時(shí) ， 圖論的多數(shù)問題是圍繞游戲而產(chǎn)生的 ， 其代表性的工作就是K246。nigsberg七橋問題 .1736年 他著名的 K246。nigsberg七橋背后的故事 ? K246。 是否存在一種走發(fā) ， 從四塊陸地中的任意一塊開始 ， 通過每一座橋恰好一次再回到起點(diǎn) 。nigsberg七橋問題 ，即一筆畫問題；也是圖論的起源 。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。 1733年，年僅 26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。歐拉在數(shù)學(xué)上的建樹很多，對(duì)著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。 四色問題 ? 為了能夠迅速地區(qū)分一個(gè)平面地圖或球面地圖上的各個(gè)國(guó)家（假設(shè)這些國(guó)家在地圖上都是連通的），需要用若干種顏色對(duì)這些國(guó)家著色，使得具有公共邊界的兩個(gè)國(guó)家涂染不同的顏色 .那么，要保證每張地圖都能如此著色，最少需要多少種顏色？這個(gè)問題是 1850年被一名剛畢業(yè)的大學(xué)生 Francis Guthrie首先提出的，直到 1976年，四色問題被美國(guó)Illinois大學(xué)的 正確的，這個(gè)證明令數(shù)學(xué)界震驚，它用了 1200多小時(shí)，作出 100億個(gè)獨(dú)立的邏輯判斷 .盡管有了這個(gè)機(jī)器證明，但它仍然是數(shù)學(xué)上未解決的問題之一 . Hamilton問題 ? Hamilton問題是圖論中一直懸而未解的一大問題 。 他在一個(gè)實(shí)心的正十二面體的十二個(gè)頂點(diǎn)上標(biāo)以世界上著名的二十座城市的名字 ， 要求游戲者沿十二面體的棱從一個(gè)城市出發(fā) ， 經(jīng)過每座城市恰好一次 ， 然后返回到出發(fā)點(diǎn) ，即 “ 繞行世界 ” 。 正十二面體 Peterson圖 旅行售貨員問題 ? 給出城市之間的距離，要求一位推銷員從某一城市出發(fā)，周游每個(gè)城市一次，然后回到出發(fā)的城市，并且選的路徑最短。 1954年幾位美國(guó)數(shù)學(xué)家寫了第一篇論文，用線性方程的方法解決了 49個(gè)城市的旅行售貨員問題。 生活中 ， 人們常常需要考慮一些對(duì)象之間的某種特定的關(guān)系 .如某區(qū)域內(nèi) ， 兩城市之間有無交通線；一群人中 ， 兩個(gè)人之間相識(shí)或不相識(shí)等等 .這種關(guān)系是對(duì)稱的 ， 即如果甲對(duì)于乙有某種關(guān)系 ， 則乙對(duì)于甲也有這種關(guān)系 .可以用一個(gè)圖形來描述給定對(duì)象之間的某個(gè)關(guān)系 ?：我們用平面上的點(diǎn)分別表示這些對(duì)象 ， 若對(duì)象甲和乙有關(guān)系 ?， 就用一條線連接表示甲和乙的兩個(gè)點(diǎn) .這種由一些點(diǎn)與連接其中某些點(diǎn)對(duì)的線所構(gòu)成的圖形就是圖論中所研究的圖 . 圖 /Graph：可直觀地表示離散對(duì)象之間的相互關(guān)系 ， 研究它們的共性和特性 ， 以便解決具體問題 。 在線性表中，元素個(gè)數(shù)可以為零，稱為空表； 在樹中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱為空樹； 在圖中，頂點(diǎn)個(gè)數(shù)不能為零，但可以沒有邊。 若頂點(diǎn) vi和 vj之間的邊沒有方向，則稱這條邊為 無向邊 ，表示為 (vi,vj)。 如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是 有向邊 ， 則稱該圖為 有向圖 。 V3 V4 V5 V1 V2 V3 V4 V5 V1 V2 非簡(jiǎn)單圖 非簡(jiǎn)單圖 簡(jiǎn)單圖 V1 V2 V3 V4 V5 ? 數(shù)據(jù)結(jié)構(gòu)中討論的都是簡(jiǎn)單圖。 V1 V2 V3 V4 V5 V1的鄰接點(diǎn)： V2 、 V4 V2的鄰接點(diǎn)： V1 、 V3 、 V5 圖的基本概念 圖的基本術(shù)語 鄰接 、 依附 有向圖 中 ， 對(duì)于任意兩個(gè)頂點(diǎn) vi和頂點(diǎn) vj， 若存在弧vi， vj， 則稱頂點(diǎn) vi鄰接到頂點(diǎn) vj， 頂點(diǎn) vj鄰接自頂點(diǎn) vi， 同時(shí)稱弧 vi， vj依附于頂點(diǎn) vi和頂點(diǎn) vj 。 F E C B A D 線性結(jié)構(gòu) A B C D E F 樹結(jié)構(gòu) V1 V2 V3 V4 V5 圖結(jié)構(gòu) 不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比 在線性結(jié)構(gòu)中，元素之間的關(guān)系為 前驅(qū) 和 后繼 ； 在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為 雙親 和 孩子 ； 在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為 鄰接 。 有向完全圖 ：在有向圖中 ， 如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧 ， 則稱該圖為有向完全圖。 含有 n個(gè)頂點(diǎn)的有向完全圖有 n (n1)條邊。 頂點(diǎn)的度： 在無向圖中 ， 頂點(diǎn) v的 度 是指依附于該頂點(diǎn)的邊數(shù) ， 通常記為 TD (v)。 V1 V2 V3 V4 V5 圖的基本術(shù)語 在具有 n個(gè)頂點(diǎn) 、 e條邊的無向圖 G中 ， 各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系 ？ ? = = n i i e v TD 1 2 ) ( 圖的基本概念 V1 V2 V3 V4 圖的基本術(shù)語 在具有 n個(gè)頂點(diǎn) 、 e條邊的有向圖 G中 ， 各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系 ？ 與邊數(shù)之和的關(guān)系 ？ e v OD v ID i i i i = = ? ? = = 1 1 ) ( ) ( n n 圖的基本概念 定理 (Handshaking) 設(shè)無向圖 G=（ V， E）有 e條邊，則 G中所有頂點(diǎn)的度之和等于 e的兩倍。 定理 無向圖中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)恰有偶數(shù)個(gè)。 定理 設(shè)有向圖 G=（ V， A）有 e條邊，則 G中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，也等于 e。 即 Σd(v)=2e 即 Σd175。 網(wǎng)： 邊上帶權(quán)的圖，也稱網(wǎng)圖。 若 G是有向圖 ， 則路徑也是有方向的 ， 頂點(diǎn)序列滿足 vij1,vij∈ E。 V1 到 V4的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4 圖的基本概念 路徑長(zhǎng)度： 圖的邏輯結(jié)構(gòu) 圖的基本術(shù)語 非帶權(quán)圖 —— 路徑 上邊的 個(gè)數(shù) 帶權(quán)圖 —— 路徑上 各邊的 權(quán)之和 V1 V2 V3 V4 V5 V1 V4：長(zhǎng)度為 1 V1 V2 V3 V4 ：長(zhǎng)度為 3 V1 V2 V5V3 V4 ：長(zhǎng)度為 4 路徑長(zhǎng)度： 圖的基本術(shù)語 非帶權(quán)圖 —— 路徑 上邊的 個(gè)數(shù) 帶權(quán)圖 —— 路徑上 各邊的 權(quán)之和 V1 V4：長(zhǎng)度為 8 V1 V2 V3 V4 ：長(zhǎng)度為 7 V1 V2 V5V3 V4 ：長(zhǎng)度