Đồ thị
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (281.71 KB, 72 trang )
1
Ch ng 4: Đ THươ Ồ Ị
2
4.1 Đ nh nghĩa và thí dị ụ
Định nghĩa:
Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp: tập
hợp các đỉnh V (vertices) với V≠Ø và tập hợp các
cạnh E (edges). Mỗi cạnh tương ứng với 2 đỉnh. Nếu
cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2
đỉnh liên kết hay kề với nhau và e được gọi là cạnh tới
các đỉnh v, w. Ký hiệu hay v w.
vwe
=
e
3
4.1 Đ nh nghĩa và thí dị ụ
Các đỉnh: A, B, C, D
Các cạnh: AB, AC, AD,
BD, BC
A
B
C
D
Cạnh không phân biệt thứ tự của đỉnh được gọi
là cạnh vô hướng. Đồ thị bao gồm các cạnh vô
hướng được gọi là đồ thị vô hướng.
4
4.1 Đ nh nghĩa và thí dị ụ
Định nghĩa:
Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi
là vòng (loop) hay khuyên.
A
B
C
5
4.1 Đ nh nghĩa và thí dị ụ
Hai cạnh phân biệt cùng tương ứng với một
cặp đỉnh gọi là 2 cạnh song song (parallel
edge).
A
B
C
6
4.1 Đ nh nghĩa và thí dị ụ
Đồ thị không có cạnh song song và khuyên
được gọi là đơn đồ thị (simple graph), ngược
lại là đa đồ thị (multi graph).
A
B
C
A B
C D
7
4.1 Đ nh nghĩa và thí dị ụ
Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub
graph) của đồ thị G = (V, E) nếu V’ ⊂ V và
E’ ⊂ E.
A
B
CD
E
B’
C’
A’
E’
8
4.1 Đ nh nghĩa và thí dị ụ
Đồ thị có số đỉnh và số cạnh hữu hạn gọi là
đồ thị hữu hạn (finite graph), ngược lại là đồ
thị vô hạn (infinite graph).
9
4.2 B c c a đ nhậ ủ ỉ
Bậc của một đỉnh
Bậc (degree) của một đỉnh v, ký hiệu là d(v),
chính là số cạnh tới đỉnh đó. Mỗi vòng tại một
đỉnh sẽ được xem như 2 cạnh tới đỉnh đó.
Nếu d(v) = 0, v được gọi là đỉnh cô lập.
Nếu d(v) = 1, v được gọi là đỉnh treo, cạnh tới
đỉnh treo được gọi là cạnh treo.
Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi
là đồ thị rỗng (null graph).
10
4.2 B c c a đ nhậ ủ ỉ
Bậc của các đỉnh:
A: 2
B: 5
C: 0 (đỉnh cô lập)
D: 2
E: 1 (đỉnh treo)
F: 4
A B C
D
E
F
X
Y
Z
T
G
G’
11
4.3 M t s đ n đ thộ ố ơ ồ ị
Đồ thị mà mọi cặp đỉnh đều kề nhau được
gọi là đồ thị đầy đủ (complete graph). Đồ thị
đầy đủ có n đỉnh được ký hiệu là K
n
.
A
B
CD
E
12
4.3 M t s đ n đ thộ ố ơ ồ ị
Đồ thị bù của một đồ thị G, ký hiệu là G, là
một đồ thị có cùng đỉnh với G và có các cạnh
là những cạnh mà ta phải bổ sung vàođể G
trở thành đầy đủ.
G G
13
4.3 M t s đ n đ thộ ố ơ ồ ị
Định lý:
Với mọi đồ thị G = (V, E), ta có:
Hệ quả:
Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ
thị là 1 số chẵn
Hệ quả:
Mọi đồ thị đều có một số chẵn các đỉnh bậc
lẻ.
∑
∈
=
Vv
Evd 2)(
14
4.3 M t s đ n đ thộ ố ơ ồ ị
Hệ quả:
Đồ thị K
n
có n(n-1) cạnh.
2
1
15
4.4 Bi u di n đ thể ể ồ ị
Danh sách kề
A B B D E
B A A C D E
C C C B D
D A B C E
E A B D
A
B
C
D
E
16
4.4 Bi u di n đ thể ể ồ ị
Ma trận kề:
A B C D E
A 0 2 0 1 1
B 2 0 1 1 1
C 0 1 1 1 0
D 1 1 1 0 1
E 1 1 0 1 0
A
B
C
D
E
17
4.4 Bi u di n đ thể ể ồ ị
Định lý:
Tổng các phần tử trên hàng (hoặc cột) thứ i
của ma trận kề của đồ thị G có n đỉnh bằng
bậc của đỉnh v
i
của đồ thị ấy, nghĩa là:
∑∑
==
==
n
k
ki
n
k
iki
mmvd
11
)(
18
4.5 Đ ng đi và chu trìnhườ
Đường đi và chu trình
Cho một đồ thị G. Một đường đi P trong G là
một dãy các cạnh nối tiếp có chung đầu mút
v
0
v
1
, v
1
v
2
,..., v
k-1
v
k
.
Ký hiệu: P = v
0
v
1
... v
k
hay P = v
0
v
1
...v
k
k (số cạnh tạo thành P) được gọi là chiều dài
của P. Ký hiệu l(P) = k.
e
1
e
2
e
k
19
4.5 Đ ng đi và chu trìnhườ
Đường đi P: EACB
l(P) = 3
A
B
C
E
D
20
4.5 Đ ng đi và chu trìnhườ
Một chu trình (cycle) trong G là một đường
đi trong G có dạng c=v
0
v
1
...v
k-1
v
0
với l(c) ≥ 1.
Một đường đi (hoặc chu trình) được gọi là
sơ cấp nếu nó không đi qua đỉnh nào quá
một lần. Một đường đi (hoặc chu trình) được
gọi là đơn giản nếu nó không đi qua cạnh
nào quá một lần.
21
4.5 Đ ng đi và chu trìnhườ
ABCA là một chu trình đơn
giản và sơ cấp.
ACB là một đường đi đơn
giản và sơ cấp.
EABCAD là một đường đi
đơn giản nhưng không sơ
cấp.
EACBADE là một chu trình
đơn giản nhưng không sơ
cấp.
A
B
C
E
D
22
4.5 Đ ng đi và chu trìnhườ
Liên thông
Một đồ thị được gọi là liên thông (connected)
nếu mọi cặp đỉnh của nó đều được nối với
nhau bởi một đường đi.
A
B
C
E
D
23
4.5 Đ ng đi và chu trìnhườ
Đồ thị không liên thông là hợp của hai hay
nhiều đồ thị con liên thông, mỗi cặp của các đồ
thị liên thông con này không có đỉnh chung.
Mỗi một đồ thị con liên thông của G và được gọi
là một thành phần liên thông (connected
component) của G.
24
4.5 Đ ng đi và chu trìnhườ
Hai thành phần liên thông bất kỳ của G thì
tách biệt.
A
B
C
D E
F
G
H
I
25
4.5 Đ ng đi và chu trìnhườ
Định lý :
Một đơn đồ thị G có n đỉnh và k thành phần
thì có tối đa là
(n – k)(n – k + 1) cạnh.
2
1
