Xem mẫu
- Lý thuyết đồ thị
Chương 1: Giới thiệu
1
- Chương 1: Giới thiệu
Định nghĩa:
Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập
hợp các đỉnh (vertices) V (V≠ Ø) và các cạnh
(edges) E. 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ề (adjacent)
với nhau và e được gọi là tới các đỉnh v, w. Ký
e = vw hay v e w.
hiệu
2
- Chương 1: Giới thiệu
A
Các đỉnh: A, B, C, D
Các cạnh: AB, AC, AD,
BD, BC
B
D
C
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.
3
- Chương 1: Giới thiệu
Đị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.
B
A
C
4
- Chương 1: Giới thiệu
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).
B
A C
5
- Chương 1: Giới thiệu
Đồ 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).
B
A B
A
C
C D
6
- Chương 1: Giới thiệu
Đồ 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 A’
E’ B’
E B
C’
D C
7
- Chương 1: Giới thiệu
Đồ 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).
8
- Chương 1: Giới thiệu
Biểu đồ
A’
A B B’
A”
C’
E’
D C B”
C”
D’
9
- Chương 1: Giới thiệu
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 (isolated
-
vertex).
Nếu d(v) = 1, v được gọi là đỉnh treo (perdant
-
vertex), cạnh tới đỉnh treo được gọi là cạnh treo
(perdant edge).
Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi
-
là đồ thị rỗng (null graph).
10
- Chương 1: Giới thiệu
Bậc của các đỉnh:
A B C
A: 2
G
B: 5
F D
C: 0 (đỉnh cô lập)
E
D: 2
Y
X E: 1 (đỉnh treo)
F: 4
G’ Z
T
11
- Chương 1: Giới thiệu
Đồ 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à Kn.
A
E B
D C
12
- Chương 1: Giới thiệu
Đồ 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
- Chương 1: Giới thiệu
Định lý 1.1:
Với mọi đồ thị G = (V, E), ta có:
∑d (v) = 2 E
v∈V
Hệ quả 1.1:
Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ
thị là 1 số chẵn
Hệ quả 1.2:
Mọi đồ thị đều có một số chẵn các đỉnh bậc
l ẻ.
14
- Chương 1: Giới thiệu
Hệ quả 1.3:
1
Đồ thị Kn có n(n-1) cạnh.
2
15
- Chương 1: Giới thiệu
Biểu diễn đồ thị - Danh sách kề
ABBDE C
BAACDE
CCCBD
B D
DABCE
EABD
A E
16
- Chương 1: Giới thiệu
Biểu diễn đồ thị - Ma trận kề:
C
A B C D E
A 0 2 0 1 1
B 2 0 1 1 1 B D
C 0 1 2 1 0
D 1 1 1 0 1
E 1 1 0 1 0
A E
17
- Chương 1: Giới thiệu
Định lý 1.2:
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 vi của đồ thị ấy, nghĩa là:
n n
d (vi ) = ∑ mik = ∑ mki
k =1 k =1
18
- Chương 1: Giới thiệu
Đườ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
v0v1, v1v2,..., vk-1vk.
Ký hiệu: P = v0 e1 v1 e2 ... ek vk
hay P = v0v1...vk
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.
19
- Chương 1: Giới thiệu
Đường đi P: EACB
A
l(P) = 3
B
E
D
C
20
nguon tai.lieu . vn