【正文】 哥尼斯堡七橋問題 : 可否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點 ? A B D C 七橋問題模型圖 歐拉 (1736): 如果每塊陸地所連接的橋都是偶數(shù)座 , 則可 。 否則 , 不可 . 0 引言 ? ? ? ? ? 環(huán)球旅行問題 ([英 ]哈密頓 . 1859): 十二面體的 20個頂點代表世界上 20個城市 , 能否從某個城市出發(fā)沿著十二面體的棱經(jīng)過每個城市恰好一次 , 最后回到出發(fā)點 ? 十二面體骨架圖 十二面體 ? ? ? ? ? 圖的遍歷 (Travering Graph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)，有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是 (正 )鄰接鏈表。 [推薦了解大數(shù)據(jù)培訓(xùn)課程 ] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /details/42105127 Fleury (弗羅萊 ) 算法通俗解釋 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖的遍歷 (Travering Graph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)，有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是 (正 )鄰接鏈表。 [推薦了解大數(shù)據(jù)培訓(xùn)課程 ] ? ? ? ? ? 圖的遍歷 廣度優(yōu)先搜索算法 廣度優(yōu)先搜索 (BreadthFirst Search，簡稱 BFS)就像水波一樣逐漸向外擴展搜索，它先要盡可能“廣”地訪問每個節(jié)點所直接連接的其他節(jié)點。 ? ? ? ? ? 深度優(yōu)先搜索 (DepthFirst Search，簡稱 DFS)就像一條路走到黑的搜索，它先要盡可能“深”地訪問每個節(jié)點 ? ? ? ? ? 例如從 A出發(fā)，先訪問直接和 A相連的節(jié)點 B和 C，然后看看有哪些節(jié)點和已經(jīng)訪問過的節(jié)點相連，如 D和 E與 B相連， F、 G和 H與 C相連，然后訪問 D、 E等節(jié)點，直到把所有節(jié)點都訪問過一遍為止。 深度優(yōu)先搜索算法 四色問題 對任何一張地圖進行著色 , 兩個有共同邊界的國家染不同的顏色 , 則只需要四種顏色就夠了 . A B C F E D 同位素問題 : 圖論中的“圖” (graph)這個術(shù)語最早用來表示化學(xué)結(jié)構(gòu) : 點表示原子 , 邊表示化學(xué)鍵 . C3H7OH 的兩個同位素的結(jié)構(gòu)圖 (樹 ): 碳 (C),氫 (H),氧 (O)各有 4個 , 1個 , 2個價電子 . ? ? ? ? ? C3H7OH 的兩個同位素的結(jié)構(gòu)圖 (樹 ) 正丙醇 異丙醇 碳 60分子球 : 碳同位素 C60 (1985. 諾貝爾獎 1996, 另兩種為金剛石和石墨 ). 目前 , 對 Fullerene的分子結(jié)構(gòu)的研究在國際圖論界 , 化學(xué)界很熱門 . C60的分子模型 : 20個正六邊形和 12個正五邊形相互連接 ? ? ? ? ? C60的分子模型 : 20個正六邊形和 12個正五邊形相互連接 現(xiàn)實中有大量問題適合用“點 —邊”圖形來描述 . 這種圖形叫做“圖” . A B D C 圖論的首篇論文 : [瑞士 ]歐拉 /Euler. 哥尼斯堡七橋問題無解 . 1736 . 圖論的第一部專著 : [匈 ]寇尼格 /Konig. 有限圖與無限圖理論 . 1936年 . 標志著圖論開始突飛猛進 . 近 40年來 , 圖論發(fā)展速度驚人 , 活躍非凡 . 主要原因是 : ①計算機為圖論提供了計算工具 。 ② 現(xiàn)代科技在圖論中找到描述和解決問題的犀利手段 . 目前 , 圖論在計算機科學(xué)、物理學(xué)、化學(xué)、運籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會科學(xué)以及經(jīng)濟管理等諸多領(lǐng)域有著廣泛的應(yīng)用 . 預(yù)備知識： : A?B = {?a, b?|a?A ? b?B}. 有序?qū)? ?a, b? ? ?b, a?. : Aamp。B = {(a, b)|a?A ? b?B}. 無序?qū)? (a, b) = (b, a). {a, a, b, b, b, c, d} = {2?a, 3?b, 1?c, 1?d} ? {a, b, c, d}. a, b, c, d 的 重復(fù)度 分別為 2, 3, 1, 1. ?無序?qū)? (a, b) 就是多重集 {a, b}, 允許 a = b. ?? Aamp。B = Bamp。A. 無序積與多重集 圖 是一種數(shù)學(xué)結(jié)構(gòu)，是一個數(shù)學(xué)概念 , 它的圖形表示叫做 圖解 . G = ?V, E ,φG ?, 其中 V ? ?, 多重集 E ? Vamp。V. 例如 G = ?V, E, φG ?, 其中 V = {a, b, e, d, e}, E = {(a, a), (a, b), (b, c), (b, c), (b, e), (a, e), (d, e). 2. 把 amp。 改為 ?, 則為 有向圖 . ?相關(guān)概念 : 頂點集 ,頂點 , 邊集 , 無向邊 , 有向邊 . a e1 e2 e3 e4 e5 e6 e7 b c d e 1. 圖的定義及相關(guān)概念 有向圖表示二元關(guān)系 , 無向圖表示對稱的二元關(guān)系 . 有向圖 D = ?V, E , φG ?, 其中 V = {a, b, c, d}, E = {?a, a?, ?a, b?, ?a, b?, ?a, d?, ?c, d?, ?d, c?, ?c, b?} ? V?V, 可圖解為 a e1 e2 e3 e6 e7 e4 e5 b c d 有序?qū)?/ordered pair, 多重集 /multiset, 重復(fù)度 /multiplicity. 圖/graph, 無向圖 /undirected graph, 頂點 /vertex (pl. vertices), 邊 /edge, 有向圖 /directed graph, digraph, 有向邊 /directed edge, 圖解 /diagram 設(shè)圖 G 的圖解如下 . 求 G (集合表示 ). e3 e2 e1 u w v G = ?V, E? = ?{u, v, w}, {e1, e2, e3}? = ?{u, v, w}, {(u, u), (u, v), (v, w)}?. G = ?V, E? 或 D = ?V, E?. V(G) = V. E(G) = E. ?本課程中只討論有限圖 . ??空圖不是圖 ! 但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果 . ? n 階圖 : |V| = n. 有限圖 : |V| ?, |E| ?. ? n 階 零圖 Nn: E = ?. 平凡圖 : N1. ? 空圖 : 216。 = ?V, E? = ??, ?? N4 N1 216。 ?標定圖 , 非標定圖 , 基圖 (1)標定圖 e3 v e2 e1 u w (2)非標定圖 (3)標定圖 e3 v e2 e1 u w ?(1)是 (3)的基圖 . n 階圖 /graph of order n, 有限圖 /finite graph, 零圖 /null graph, 平凡圖 /trivial graph, 空圖 /empty graph, 標定圖 /labelled graph, 非標定圖 /unlabelled graph, 基圖 /base graph 端點 , 關(guān)聯(lián) : 點與邊 關(guān)聯(lián)次數(shù) : 環(huán) : 孤立點 : 相鄰 : 點與點 , 邊與邊 鄰接 到 (于 ): 點與點 , 邊與邊 始點 , 終點 1 1 1 ?1 2 ? endvertex, incident, loop, isolated vertex, adjacent, adjacent to, adjacent from, initial vertex, terminating vertex e1 e2 u v e 鄰域 NG(v). 閉鄰域 ?N G(v). 關(guān)聯(lián)集 IG(v). (閉 )鄰域 /(closed) neighborhood, 關(guān)聯(lián)集 /incidency set, 后繼 /successor, 先驅(qū) /predecessor v 后繼元集 : ? +(v). 先驅(qū)元集 : ? ?(v). 鄰域 : N(