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

Presentation on theme: "GRAPH THEORY 圖論 第二組 晏彩霞 陳弘益 王文斕."— Presentation transcript:

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

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

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

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

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

6 圖的基本概念

7 圖的定義 我們用 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

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

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

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

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

12 分集合 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} 每一個邊所連到的點都在不同的分集合!

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

14 生活中的一些例子

15

16 台大網路架構圖

17 一些特殊的圖

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

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

20 雙分圖 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

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

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

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

24 圖論的應用及演算法

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

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

27 廣度搜尋法(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) 完成!

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

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

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

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

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

33 References Graph Theory, Ronald Gould 圖論演算法, 黃國卿 沿著歐拉的足跡──圖論初探

34 報告完畢！