Bài giảng Toán tổ hợp - Chương 4: Đại cương về đồ thị
Chương 4.
ĐẠI CƯƠNG VỀ ĐỒ THỊ
Nội dung
1. Giới thiệu
2. Các khái niệm cơ bản
3. Biểu diễn đồ thị
4. Đẳng cấu đồ thị
5. Đường đi, chu trình
2
1. Giới thiệu
Bài toán. Thành phố Königsberg, Đức nằm trên một
con sông, có hai hòn đảo lớn nối với nhau và với đất
liền bởi bảy cây cầu. Bài toán đặt ra là có thể đi theo
một tuyến đường mà đi qua mỗi cây cầu đúng một
lần rồi quay lại điểm xuất phát hay không?
3
Năm 1736, nhà toán học
Leonhard Euler đã chứng
minh rằng điều đó là không
thể được.
4
Bài toán 1. Có thể vẽ hình phong bì thư bởi một nét
bút hay không? Nếu có hãy chỉ ra tuần tự các nét vẽ
1
3
2
4
5
5
Bài toán 2. Một đoàn kiểm tra chất lượng các con
đường. Để tiết kiệm thời gian, đoàn kiểm tra muốn đi
qua mỗi con đường đúng 1 lần. Kiểm tra xem có cách
đi như vậy không?
4
7
5
1
8
6
2
3
6
Bài toán 3. Một sinh viên muốn đi từ nhà đến trường
thì phải đi như thế nào? Cách đi nào là ngắn nhất?
7
2. Các khái niệm cơ bản
Định nghĩa. Một đồ thị vô hướng
(undirected graph) G=(V, E) được
định nghĩa bởi:
• Tập hợp V được gọi là tập các
đỉnh (vertex) và n = |V| gọi là cấp
của đồ thị;
• Tập hợp E là tập các cạnh (edge)
của đồ thị; Mỗi cạnh eE được liên
kết với một cặp đỉnh {i, j}, không
phân biệt thứ tự
8
Đỉnh kề
Định nghĩa. Trên đồ thị vô hướng, xét cạnh e được
liên kết với cặp đỉnh {i, j}:
. Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề
với cạnh e); có thể viết tắt e=ij
. Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i
kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i)
. Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song
song.
. Cạnh có hai đỉnh trùng nhau gọi là một khuyên
9
Đỉnh kề
Tập các đỉnh kề với đỉnh v được viết là
(v) {u V :(v,u) E}
Nhận xét. Đồ thị G hoàn toàn được xác định nếu
chúng ta biết
(v),vV
nên đồ thị G cũng có thể định nghĩa như sau:
G (V,)
10
Đỉnh kề
. Cạnh song song: e1, e7
. Khuyên: e9
. Đỉnh treo: 5
. Đỉnh cô lập: 6
(2) {1, 3, 4}
.
11
Một số loại đồ thị vô hướng
Định nghĩa. Cho G là đồ thị vô hướng. Khi đó G
được gọi là:
a) đơn đồ thị (hay đồ thị đơn) nếu G không có
khuyên và không có cạnh song song
b) đa đồ thị nếu G không có khuyên, cho phép có
cạnh song song
c) giả đồ thị nếu G cho phép có cạnh song song và
có khuyên
12
c
e
b
b
a
a
d
h
c
k
g
d
b
a
d
c
13
Các dạng đồ thị
. Đồ thị rỗng: tập cạnh là tập rỗng
. Đồ thị đủ: đồ thị vô hướng, đơn,
giữa hai đỉnh bất kỳ đều có đúng
một cạnh.
B
A
. Đồ thị đủ n đỉnh ký hiệu là Kn.
C
푛 n−1
. Kn có
cạnh.
2
. Đồ thị k-đều: là đồ thị mà mọi đỉnh
đều có bậc bằng nhau và bằng k.
14
. Đồ thị lưỡng phân: đồ thị vô
hướng G=(V, E) được gọi là đồ thị
lưỡng phân nếu tập V được chia
thành hai tập V1 và V2 thỏa:
A
D
. V1 và V2 phân hoạch V;
B
. Cạnh chỉ nối giữa V1 và V2.
E
. Đồ thị lưỡng phân đủ: là đồ thị
lưỡng phân thỏa điều kiện mỗi đỉnh
trong V1 kề với mọi đỉnh trong V2.
C
• V1=n và V2=m, ký hiệu Kn,m
15
K4
K4
K3
K2 K1, 1
K3, 3
K2, 3
16
GV: Döông Anh Ñöùc
16
Đồ thị có hướng
Định nghĩa. Một đồ thị có hướng
G=(V, U) được định nghĩa bởi:
• Tập hợp V được gọi là tập
các đỉnh.
• Tập hợp U là tập các cạnh (cung)
của đồ thị; Mỗi cạnh uU được
liên kết với một cặp đỉnh (i, j)V2.
Ký hiệu u=(i,j) hoặc u=ij.
17
Đỉnh kề
Trên đồ thị có hướng, xét cạnh u được liên kết với
cặp đỉnh (i, j):
. i được gọi là đỉnh đầu, j được gọi là đỉnh cuối
. Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j
kề với cạnh u); có thể viết tắt u=(i, j). Cạnh u đi ra
khỏi đỉnh i và đi vào đỉnh j.
18
Đỉnh kề
Định nghĩa. Cho đồ thị có hướng G=(V, E) và e=(u, v)E
• v là đỉnh sau của u
• u là đỉnh trước của v
• Tập hợp các đỉnh sau và đỉnh trước của v lần lượt là
(v), (v)
Nhận xét. Đồ thị G hoàn toàn được xác định
nếu chúng ta biết
(v),vV
nên đồ thị G cũng có thể được định nghĩa như sau:
G (V,)
19
Đỉnh kề
h
e
2
4
g
l
Ví dụ.
a
6
f
1
c
k
j
b
i
d
3
5
(v)
(v)
v
1
2
3
5
6
20
Tải về để xem bản đầy đủ
67 trang
15/01/2024
11900
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán tổ hợp - Chương 4: Đại cương về đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_to_hop_chuong_4_dai_cuong_ve_do_thi.pdf
