Chapter 2 Basic Concepts in Graph Theory 大葉大學 資訊工程系 黃鈴玲 2011.9

Contents 2.1 Paths and Cycles 2.2 Connectivity 2.3 Homomorphisms and Isomorphisms of Graphs 2.4 More on Isomorphisms on Simple Graphs 2.5 Formations and Minors of Graphs 2.6 Homomorphisms and Isomorphisms for Digraphs 2.7 Digraph Connectivity

2.1 Paths and Cycles

is a walk of length 7

contain

Theorem 2.4 Proof Hint: Let P be a u, v-walk of shortest length. Show that P is a u, v-path. Ex 2.1, 2.2

2.2 Connectivity as components

Theorem 2.13 For a simple graph G with n vertices and k components we have Proof Let H1, H2, …, Hk be the k components of G, and |V(Hi)| = ni for each i. By Lemma 2.14, Ex 2.4, 2.5

2.3 Homomorphisms and Isomorphisms of Graphs 當 f 是 G  G’的 homomorphism時， 若u,v兩點在G中相連，則這兩點對應過去的f(u)與f(v)也在G’中相連

Let f : G G’ be defined by f = (f1, f2), where

Example 2.17

原因1：左圖有一條edge，一個端點連接multiedge， 另一端點連接loop，但右圖沒有此種edge Example 2.19 No! 原因1：左圖有一條edge，一個端點連接multiedge， 另一端點連接loop，但右圖沒有此種edge 原因2：左圖只有一點degree=2，它的neighbor的degree 分別是3及4，但與右圖degree=2節點的neighbor degree不等

Ex2.13. Show that the graphs shown in Figure 2.25 are isomorphic.

2.4 More on Isomorphisms on Simple Graphs Observation 2.22 Def 2.24 Theorem 2.25 Ex 2.22, 2.23

Example 2.26 Both graphs are 3-regular with 6 vertices. G has 3-cycles, but G’ has no 3-cycles.  No! Another reason: G is planar but G’ is not. (see Chapter 7)

complement not isomorphic

Ex2. 14. Which, if any, of the graphs G1, G2, G3, and G4 in Figure 2 Ex2.14. Which, if any, of the graphs G1, G2, G3, and G4 in Figure 2.26 are isomorphic?

Ex2. 16. Which, if any, of the graphs G1, G2, and G3 in Figure 2 Ex2.16. Which, if any, of the graphs G1, G2, and G3 in Figure 2.27 are isomorphic?

2.5 Formations and Minors of Graphs Def 2.27

Def 2.30

Def 2.33 Ex 2.28 Def 2.34 The contraction (收縮) of G by e (denoted by Ge) (將e的兩端點u, v黏成一點w，原先與u或v相連的點，都與w相連， 新圖的總邊數只比原圖少一條)

Def 2.36 Simple contraction of G by e (denoted by G/e) (將Ge改為simple graph，即去除multiedge)

Def 2.37 For G’ c sequ 1. 2. Example 2.38 Ex 2.31, 2.32

2.6 Homomorphisms and Isomorphisms for Digraphs f: GG’ is a homomorphism on digraphs v f(v)  u f(u) G G’

All vertices indegree=1 outdegree=1 2 vertices indegree=1 outdegree=1 They are adjacent. 2 vertices indegree=1 outdegree=1 They are not adjacent.

2.7 Digraph Connectivity Def 2.44

A digraph is called weakly connected if its underlying graph is connected. Def 2.47 These two directed paths are not necessarily edge disjoint.

Example 2.50

補充題: Show that there is no tournament on 6 vertices all of whose vertices have the same outdegree.