GRAPH THEORY 圖論 第二組 晏彩霞 陳弘益 王文斕

Contents 圖論的起源+圖的基本概念 一些特殊的圖 在電腦上表示圖的方法 一些圖論的應用

什麼是圖？ 圖論中所謂的圖是由一些點(vertices)，和一些連接兩點的邊(edges)所形成的 一些表示是有限(finite)的

圖論的起源 哥尼斯堡七橋問題: 要如何走過每座橋恰一次，再返回出發點？ 普瑞格爾河 哥斯尼堡:介於立陶宛和波瀾之間 1736 年，年29 的數學家歐拉(Euler, 1707-1783)嚴格地證明了上述哥尼斯堡七橋問題無 解，並且由此開創了圖論的典型思維方式及論證方式，1736 年遂被公認為圖論元年。 普瑞格爾河

一筆畫問題 哥尼斯堡七橋問題可以看成是：對這樣一個封閉的圖形，是否可以一筆畫完成它並且回到原點 數學家歐拉(Euler, 1707-1783) 於1736年嚴格地證明了上述哥尼斯堡七橋問題無解，並且由此開創了圖論的典型思維方式及論證方式

圖的基本概念

圖的定義 我們用 G=(V,E) 來表示一個圖，其中 相鄰(adjacent):由一邊所連接的兩個點稱相鄰 獨立(independent):兩點沒有邊相連 V={a, b, c} E={e1, e2} ={ac, ab} b and c are independent a is adjacent to b and c

一些基本的圖形 Graph (無向圖) Digraph (有向圖) Multigraph (多圖) Pseudograph loop

Path and Cycle 路徑(path):是一個有限非空的點和邊的交錯序列，其中的點兩兩不相同 E.g. 路徑P=fdabce 迴圈C=abca

連通性 connectivity 對於圖中的任意兩點x,y 皆存在(x,y) 路徑 這是一個由兩個連通子圖所構成的非連通圖

加權圖 weighted graph 加權圖(weighted graph):對每一個邊賦以一個實數的權值

分集合 Partite sets A graph G is m-partite if it can be partitioned into m partite sets such that each edge of G joins two vertices in different partite sets This graph can be partitioned into 3 partite sets V1={A,B} V2={C} V3={D} 每一個邊所連到的點都在不同的分集合!

Isomorphism G is isomorphic to H (G~H) if: G上的每一點在H上都只有一個對應的點，使得在G上相鄰的兩個點在H上面也是相鄰的 The three graphs above are isomorphic 這三個圖表示相同的概念

生活中的一些例子

台大網路架構圖

一些特殊的圖

完整的圖 Complete graphs 任意兩點之間都有一個邊與其相連的圖稱為完整的圖，以Kn 來表示，n為點數，邊數為

樹狀圖 Trees 樹(tree):一個連通的無圈無向圖 生成樹 (spanning tree):包括圖中所有的頂點，並且是一顆樹 tree 任兩點間僅有一條路徑 生成樹 (spanning tree):包括圖中所有的頂點，並且是一顆樹 tree A connected graph G Spanning trees of G

雙分圖 Bipartite graphs A graph that can be decomposed into two partite sets but not fewer is bipartite It is a complete bipartite if its vertices can be divided into two non-empty groups, A and B. Each vertex in A is connected to B, and vice-versa The graph is bipartite Complete bipartite graph K2,3

平面圖 Planar graphs A planar graph is a graph that can be embedded in a plane so that no edges intersect Planar: = NOT Planar:

在電腦上表示圖的方法 Incident list Incident matrix Adjacency list Adjacency matrix

Adjacency list and adjacency matrix A:B B:A,C,D C:B,D D:B,C adjacency list adjacency matrix

圖論的應用及演算法

連通性問題(Connectivity) Question : 判斷一個圖形是否具有連通性 Main Algorithms: 深度搜尋法(Depth-first search) 廣度搜尋法(Breadth-first search)

深度搜尋法(Depth-first search) Example: a graph with 10 vertices (1) (2) (8) (3) (9) (10) 完成! (5) (4) (7) (6)

廣度搜尋法(Breadth-first search) Check A B D E C H J F G I Queue A BDE DEC EC C HJFG JFGI FGI GI I (0) (1) (3) (2) (4) (1) (1) (3) (3) (3) 完成!

日常生活中的例子： 深度搜尋法(Depth-first search)

一筆畫問題 (Euler Tour) Question : 判斷圖形可否一筆畫完，亦即筆尖不離開 紙面，而且每條線都只畫一次而不重複. 一筆畫定理：一個圖形是一筆畫的 iff 它是連通且奇頂點(odd vertex)的個數等於0 或2

一筆畫問題 (Euler Tour) 哥尼斯堡(Konigsberg)七橋問題

一筆畫問題 (Euler Tour) 中國郵路問題 可以一筆畫 不能一筆畫

更複雜的一筆畫問題 哈密頓（Hamilton）環遊世界問題 如何一次歷遍二十個城市而不重覆？ 這是一個NP Complete的問題

References Graph Theory, Ronald Gould 圖論演算法, 黃國卿 沿著歐拉的足跡──圖論初探 http://www.all-science-fair-projects.com/science_fair_projects_encyclopedia/

報告完畢！