Xem mẫu
- Chương II. Lý thuyết đồ thị
I. Các khái niệm cơ bản
II. Biểu diễn đồ thị
III. Tính liên thông
IV. Chu trình Euler
V. Bài toán tìm đường đi ngắn nhất
VI. Đồ thị phẳng
VII.Tô màu đồ thị
- I. Các khái niệm cơ bản
1. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH)
Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh
đó. Được mô tả hình thức: G = (V, E)
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh
(Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai
đỉnh thuộc V.
Ví dụ:
Đường Mạng
phố máy tính
- 2. Phân loại đồ thị
G được gọi là đơn đồ thị nếu giữa hai đỉnh phân biệt u,
v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v.
G được gọi là đa đồ thị nếu giữa hai đỉnh phân biệt u, v
của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v
G được gọi là giả đồ thị nếu G là đa đồ thị và có thể có
cạnh nối từ một đỉnh đến chính nó. Cạnh đó được gọi là
khuyên
G được gọi là đồ thị vô hướng nếu các cạnh trong E
không có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là
đỉnh cuối.
G được gọi là đồ thị có hướng nếu các cạnh trong E có
sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối.
- Ví dụ
Đơn đồ Đơn đồ
thị thị
vô hướng có hướng
Đa đồ thị Đa đồ thị
vô hướng có hướng
- 3. Cạnh liên thuộc, đỉnh kề, bậc
Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e ∈ E, nếu
e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và
cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v.
Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v,
ký hiệu deg(v) là số cạnh liên thuộc với v.
Định lý: Giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi
đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m:
∑ deg(v) = 2m
v ⊂V
Chứng minh: Khi lấy tổng tất cả các bậc đỉnh tức là mỗi cạnh
e = (u, v) bất kỳ sẽ được tính một lần trong deg(u) và một lần
trong deg(v). Từ đó suy ra kết quả.
Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là số chẵn
-
Đối với đồ thị có hướng G = (V, E). Xét một cung e ∈ E, nếu e
= (u, v) thì đỉnh u khi đó được gọi là đỉnh đầu,đỉnh v được gọi
là đỉnh cuối của cung e.
Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: bậc ra
của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bậc vào ký
hiệu deg-(v) là số cung đi vào đỉnh đó.
Định lý: Giả sử G = (V, E) là đồ thị có hướng với m cung, khi
đó tổng tất cả các bậc ra bằng tổng tất cả các bậc vào và
bằng m:
∑ deg + (v) = ∑ deg − (v) = m
v ⊂V v ⊂V
- 4. Một số dạng đồ thị đặc biệt
a. Đồ thị đầy đủ Kn (n≥1) có n đỉnh và mỗi cặp đỉnh đều có
đúng một cạnh nối.
K4
K2 K3
- b. Chu trình Cn (n≥3) có n đỉnh v1,v2,..vn và các cạnh
(v1,v2); (v2,v3)....(vn-1,vn) và (vn,v1)
C4
C3
c5
- c. Đồ thị hình bánh xe
Khi thêm một đỉnh vào giữa chu trình Cn và nối đỉnh này với
các đỉnh của đồ thị Cn ta thu được đồ thị hình bánh xe.
W4
W3 W5
- d. Đồ thị hình khối Qn có 2n đỉnh, mỗi đỉnh được biểu diễn
bằng xâu nhị phân độ dài n. Hai đỉnh là liền kề nếu các xâu
nhị phân biểu diễn chúng khác nhau đúng một bit.
10 11 110 111
Q1 100 101
Q2 Q3
010
011
000 001
00 01
- e. Đồ thị phân đôi là đồ thị có tập các đỉnh V có thể
phân làm hai tập con không rỗng, rời nhau V1 và V2 sao
cho mỗi cạnh của đồ thị nối 1 đỉnh của V1 với 1 đỉnh
của V2
Đồ thị phân đôi đầy đủ Km,n là đồ thị có tập các đỉnh
được phân thành hai tập con tương ứng có m đỉnh và n
đỉnh và có cạnh giữa hai đỉnh nếu đỉnh thứ nhất thuộc
tập con này, đỉnh thứ hai thuộc tập con kia.
- II. Biểu diễn đồ thị
1. Ma trận liền kề (ma trận kề)
Giả sử G = (V, E) là một đơn đồ thị có số đỉnh là n, không
mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, ...,
n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông
cấp n A = [aij]. Trong đó:
aij= 1 nếu (i, j) ∈ E
aij = 0 nếu (i, j) ∉ E
Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có
điều nếu như (i, j) là cạnh thì không phải ta ghi số 1 vào vị trí
aij mà là ghi số cạnh nối giữa đỉnh i và đỉnh j
- Ví dụ
- Ưu điểm và nhược điểm
Ưu điểm của ma trận liền kề:
Đơn giản, trực quan, dễ cài đặt trên máy tính
Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau
hay không, ta chỉ việc kiểm tra bằng một phép so
sánh: auv≠ 0.
Nhược điểm của ma trận liền kề:
Tiêu tốn bộ nhớ: bất kể số cạnh của đồ thị là nhiều
hay ít, ma trận liền kề luôn luôn đòi hỏi n2 ô nhớ để
lưu các phần tử ma trận.
Khó làm việc với đồ thị có số lượng đỉnh lớn.
- 2. Danh sách cạnh
Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn
đồ thị dưới dạng danh sách cạnh, trong cách biểu diễn này,
người ta liệt kê tất cả các cạnh của đồ thị trong một danh
sách, mỗi phần tử của danh sách là một cặp (u, v) tương ứng
với một cạnh của đồ thị.
Danh sách được lưu trong bộ nhớ dưới dạng mảng hoặc danh
sách móc nối. Ví dụ với đồ thị dưới đây:
- Ưu điểm của danh sách cạnh:
Trong trường hợp đồ thị có số cạnh tương đối nhỏ: chẳng
hạn m < 6n cách biểu diễn bằng danh sách cạnh sẽ tiết
kiệm được không gian lưu trữ, bởi nó chỉ cần 2m ô nhớ để
lưu danh sách cạnh.
Dể dàng duyệt tất cả các cạnh của đồ thị.
Nhược điểm của danh sách cạnh:
Nhược điểm cơ bản của danh sách cạnh là khi ta cần
duyệt tất cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì
chẳng có cách nào khác là phải duyệt tất cả các cạnh, lọc
ra những cạnh có chứa đỉnh v và xét đỉnh còn lại.
- 3. Danh sách kề
Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, ta cho
tương ứng với nó một danh sách các đỉnh kề với v.
Đỉnh Đỉnh kề
1 2,3,5
2 1,3
3 1,2,4
Ưu điểm
Dễ
4 3,5
dàng duyệt tất cả các đỉnh kề với một
đỉnh v cho trước 5 1,4
Dễ dàng duyệt tất cả các cạnh
Nhược điểm: Cài đặt danh sách kề có phần
dài dòng hơn.
- III. Tính liên thông
Đường đi độ dài n từ đỉnh u đến đỉnh v trong đồ thị là
một dãy các cạnh e1, e2, ..en với (u,x1) = e1; (x1,x2) = e2; ..
(xn-1,v) = en
Độ dài đường đi bằng với số cạnh mà nó đi qua
Chu trình là đường đi mà nó bắt đầu và kết thúc tại cùng
một đỉnh
Chu trình (đường đi) gọi là đơn khi nó không đi qua cùng
1 cạnh quá một lần
Một đồ thị được gọi là liên thông nếu có đường đi giữa
mọi cặp đỉnh phân biệt của đồ thị
Định lý: Giữa mọi cặp đỉnh của một đồ thị vô hướng
liên thông luôn có đường đi đơn
- Một đồ thị không liên thông là hợp của 1 hay nhiều đồ thị con
liên thông. Các đồ thị này được gọi là các thành phần liên
thông
Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a
tới b và từ b tới a với a, b là hai đỉnh bất kỳ của đồ thị.
- IV. Chu trình và đường đi Euler
Bài toán bảy cây cầu Euler, còn gọi là Bảy cầu ở Königsberg
nảy sinh từ vấn đề cụ thể. Thành phố Königsberg, Đức (nay là
Kaliningrad, Nga) nằm trên sông Pregel, bao gồm 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. Câu hỏi đặ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. Năm
1736, Leonhard Euler đã chứng minh rằng điều đó là không
thể được. Trong lịch sử toán học, lời giải của Euler cho bài
toán bảy cây cầu ở Königsberg được coi là định lý đầu tiên
của lý thuyết đồ thị.
nguon tai.lieu . vn
