GraphTheory离散数学、图论、双语精品PPT课件

Ch1-6 Copyright 黃鈴玲
Example
A graph G=(V,E), where
V={u, v, w, x, y, z}
E={{u,v}, {u,w}, {w,x}, {x,y}, {x,z}}
E={uv, uw, wx, xy, xz}
G 的 diagram
u
v
表示法:
w
z
An elementary example of graphs
4 students: A, B, C, D 4 positions: FF, SC, W, BS
四人各有喜好的工作：(如下圖，連線表示有興趣)
FF SC
W
BS
Q: Can all four
students find
jobs they like?
e=uv (e joins u and v) (e is incident with u, e is incident with v)
Ch1-8 Copyright 黃鈴玲
Graphs types
loop
multiedges, parallel edges
undirected graph:
• (simple) graph: loop (), multiedge ()
Ch1-2 Copyright 黃鈴玲
Graph Theory 的起源
1736, Euler solved the Königsberg Bridge Problem (七橋問題)
Q: 是否存在一 種走法，可以走 過每座橋一次， 並回到起點？
(Ch7 Euler graph)
Ch1-3 Copyright 黃鈴玲
eg. Animals: A, B, C, D, E
A
AC 不能與 BD 同區， E不能與其他動物同區
DE
B
Q: 將圖形的點著色 (一色表示一區)， 若相鄰兩點需塗不同色， 最少需多少顏色才夠？
Ans: 3 色 3 區
(Ch 10 Graph Coloring)
C 連線表示不能同區
Ch1-12 Copyright 黃鈴玲
Homework
Exercise 1.1: 1, 2, 3, 4
(Ch6 Matching)
A
B
C
D
Ans: No
Ch1-5
Copyright 黃鈴玲
Definition of a graph
A graph G is a finite nonempty set V(G) of vertices (also called nodes, 點) and a (possibly empty) set E(G) of 2-element subsets of V(G) called edges (or lines, 邊).
x
y
Ch1-7
Copyright 黃鈴玲
Adjacent and Incident
u, v : vertices of a graph G
e
u
v
u and v are adjacent in G if uv E(G) ( u is adjacent to v, v is adjacent to u)
V(G) : vertex set of G (只有一個 G 時常簡寫為 V) E(G) : edge set of G (只有一個 G 時常簡寫為 E) 常見的 edge 表示法: {u, v} = {v, u} = uv (or vu) 當邊有方向性時稱 G 為 directed graph (digraph)
Graph Theory
Chapter 1 An Introduction to Graphs
大葉大學 資訊工程系 黃鈴玲
Outline
1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs
The number of edges is its size (denoted by |E(G)| ).
Proposition 1: If |V(G)| = p and |E(G)| = q, then
q
p 2
A graph of order p and size q is called a (p, q) graph.
Kö nigsberg Bridge Problem
C
A
D
B
Q: 是否存在一種走法，可以走過每條邊一次，並回 到起點？
Ans: 因為每次經過一個點，都需要從一條邊進入該點，再用另
一條邊離開，所以經過每個點一次要使用掉一對邊。
每個點上連接的邊數必須是偶數才行
此種走法不存在
Ch1-4 Copyright 黃鈴玲
Ch1-10 Copyright 黃鈴玲
Application of graphs
一群人間兩兩互相認識或不認識(i.e., 沒有A認識B但 B不認識A的情形)，在安排一張圓桌的晚餐座位時， 是否存在一種排法能讓坐在一起的人都相互認識？
eg.
Tom, Dick know Sue, Linda.
Harry knows Dick and Linda.
• multigraph: loop (), multiedge ()
• Pseudograph: loop (), multiedge ()
Ch1-9 Copyright 黃鈴玲
order and size
The number of vertices in a graph G is called its order (denoted by |V(G)| ).
acquaintance k
Q: 圖中是否有一個通過 所有點的cycle?
(Ch8 Hamiltonian graph)
Sue
Linda
Harry
Ch1-11 Copyright 黃鈴玲
Application of graphs
動物園要用圍牆劃分區域，避免同區的動物互相捕食， 至少需分多少區？