Đồ thị Nguyễn Thế Vinh-ĐHKH
68
Ví dụ:
Ta có deg(v
1
)=7, deg(v
2
)=5, deg(v
3
)=3, deg(v
4
)=0, deg(v
5
)=4,
deg(v
6
)=1, deg(v
7
)=2. Đỉnh v
4
là đỉnh cô lập và đỉnh v
6
là đỉnh treo.
Trong một đồ thị có hướng bậc- vào của đỉnh v kí hiệu deg
-
(v) là số
cạnh có đỉnh cuối là v. Bậc-ra của đỉnh v kí hiệu là deg
+
(v) là số cạnh có đỉnh
đầu là v
Định lí 1: Một đồ thị vô hướng G=(V,E) có n cạnh thì tổng các bậc của
đỉnh là 2n
∑
∈
=
Vv
nv 2)deg(
Định lí 2: Một đồ thị vô hướng có một số chẵn các đỉnh bậc lẻ.
Chứng minh: Gọi V1 là tập các đỉnh bậc lẻ, V2 là tập các đỉnh bậc chẵn
của đồ thi G=(V,E) với số cạnh là n theo định lí 1 ta có
∑ ∑
∈ ∈
+=
1 2
)deg()deg(2
Vv Vv
vvn
Như vậy tổng trên là một số chẵn trong đó V2 là tập các đỉnh bậc chẵn
nên tổng
∑
∈ 2
)deg(
Vv
v
là một số chẵn, suy ra tổng
∑
∈ 1
)deg(
Vv
v
cũng là một số
chẵn. Mặt khác theo giả thiết V1 là số các đỉnh bậc lẻ do vậy chúng phải tồn
tại chẵn số các số hạng, hay số các đỉnh bậc lẻ là số chẵn. (đpcm)
4.3.2. Đường đi và chu trình: Đường đi độ dài n từ đỉnh u tới đỉnh v,
với n là một số nguyên không âm trong một đồ thị vô hướng là một dãy các
cạnh {x
0
,x
1
},{x
1
,x
2
},…,{x
n-1
,x
n
}, với u=x
0
và x
n
=v. Đường đi được gọi là một
chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh.
4.3.3.Tính liên thông: Một đồ thị vô hướng G=(V,E) đượ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ị.
v
6
v
1
v
2
v
3
v
4
v
5
v
7
Đồ thị Nguyễn Thế Vinh-ĐHKH
69
Một đồ 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 mọi đỉnh a và b của đồ thị.
Một đồ thị có hướng gọi là liên thông yếu nếu luôn tồn tại đường đi
giữa hai đỉnh khi ta không quan tâm tới hướng của các cạnh.
4.3.4. Thành phần liên thông: Một đồ thị G=(V,E) 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ác đồ thị con này không
có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các
thành phần liên thông của đồ thị G=(V,E).
4.3.5. Điểm khớp: Một đỉnh v được gọi là điểm khớp của đồ thị
G=(V,E) nếu loại bỏ v cùng các cạnh liên thuộc với nó khỏi đồ thị sẽ làm tăng
số thành phần liên thông của đồ thị.
4.3.6. Cầu của đồ thị: Một cạnh của đồ thị G=(V,E) gọi là cầu, nếu loại
bỏ cạnh đó khỏi đồ thị sẽ làm tăng số thành phần liên thông của đồ thị.
4.4. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT
4.4.1. Đồ thị đầy đủ: Đồ thị đầy đủ n đỉnh, ký hiệu là K
n
, là đơn đồ thị
mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. Như vậy, K
n
có n(n-1)/2
cạnh và mỗi đỉnh của K
n
có bậc là n−1.
Ví dụ:
4.4.2. Đồ thị vòng: Đơn đồ thị n đỉnh v
1
, v
2
, , v
n
(n≥3) và n cạnh
(v
1
,v
2
), (v
2
,v
3
), , (v
n-1
,v
n
), (v
n
,v
1
) được gọi là đồ thị vòng, ký hiệu là C
n
. Như
vậy, mỗi đỉnh của C
n
có bậc là 2.
Ví dụ:
C
3
C
4
C
5
C
6
v
1
v
1
v
2
v
1
v
2
v
3
v
1
v
2
v
3
v
4
v
5
v
2
v
1
v
3
V
4
v
1
v
2
v
3
v
1
v
2
v
4
v
3
v
1
v
5
v
2
v
4
v
3
v
1
v
6
v
5
v
2
v
3
v
4
Đồ thị Nguyễn Thế Vinh-ĐHKH
70
4.4.3. Đồ thị bánh xe:Từ đồ thị vòng C
n
, thêm vào đỉnh v
n+1
và các
cạnh (v
n+1
,v
1
), (v
n+1
,v
2
), , (v
n+1
,v
n
), ta nhận được đơn đồ thị gọi là đồ thị bánh
xe, ký hiệu là W
n
. Như vậy, đồ thị W
n
có n+1 đỉnh, 2n cạnh, một đỉnh bậc n và
n đỉnh bậc 3.
Ví dụ:
4.4.4. Đồ thị lập phương: Đơn đồ thị 2
n
đỉnh, tương ứng với 2
n
xâu nhị
phân độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị phân tương ứng với
hai đỉnh này chỉ khác nhau đúng một bit được gọi là đồ thị lập phương, ký
hiệu là Q
n
. Như vậy, mỗi đỉnh của Q
n
có bậc là n và số cạnh của Q
n
là n.2
n-1
Ví dụ:
4.4.5. Đồ thị phân đôi (đồ thị hai phe): Đơn đồ thị G=(V,E) sao cho
V=V
1
∪V
2
, V
1
∩V
2
=∅, V
1
≠∅, V
2
≠∅ và mỗi cạnh của G được nối một đỉnh
trong V
1
và một đỉnh trong V
2
được gọi là đồ thị phân đôi.
Nếu đồ thị phân đôi G=(V
1
∪V
2
,E) sao cho với mọi v
1
∈V
1
, v
2
∈V
2
,
(v
1
,v
2
)∈E thì G được gọi là đồ thị phân đôi đầy đủ. Nếu |V
1
|=m, |V
2
|=n thì đồ
thị phân đôi đầy đủ G ký hiệu là K
m,n
. Như vậy K
m,n
có m.n cạnh, các đỉnh của
V
1
có bậc n và các đỉnh của V
2
có bậc m.
v
6
v
5
v
2
v
3
v
4
v
7
v
1
v
1
v
5
v
2
v
4
v
3
v
6
v
1
v
2
v
4
v
3
v
5
v
2
v
3
v
1
v
4
010
001
011
0
1
10
11
01
00
000
100 101
111
110
Đồ thị Nguyễn Thế Vinh-ĐHKH
71
Ví dụ:
K
2,4
K
3,3
4.5. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
4.5.1. Ma trận kề và ma trận trọng số
Giả sử G=(V,E) là một đơn đồ thị với n đỉnh.
Ma trận kề không- một cấp n x n
A=[a
ij
] trong đó:
a
ij
= 0 nếu không có cạnh nối đỉnh i với đỉnh j
a
ij
=1 nếu có cạnh nối đỉnh i với đỉnh j
v1 v2 v3 v4 v5
v1 0 1 1 0 1
v2 1 0 0 1 0
v3 1 0 0 1 1
v4 0 1 1 0 1
v5 1 0 1 1 0
Chú ý: Ma trận kề của một đơn đồ thị là ma trận đối xứng.
Ma trận kề là một ma trận thưa khi đồ thị tương đối ít cạnh
Trong trường hợp mỗi cạnh {i,j} được gắn với một trọng số k nào đó.
Ta thay ma trận không-một bằng ma trận trọng số A=[a
ij
] trong đó:
a
ij
=∞ nếu không có cạnh nối đỉnh i với đỉnh j
a
ij
=k nếu có cạnh nối đỉnh i với đỉnh j có trọng số k
v
1
v
2
v
3
v
4
v
5
v
6
v
1
v
2
v
3
v
4
v
5
v
6
v
1
v
2
v
4
v
5
v
3
Đồ thị Nguyễn Thế Vinh-ĐHKH
72
4.5.2. Ma trận liên thuộc
Một cách thường dùng nữa để biểu diễn đồ thị là dùng ma trận liên
thuộc. Giả sử G=(V,E) là một đồ thị vô hướng với các đỉnh v
1
, v
2
, v
n
và các
cạnh là e
1
, e
2
, e
m
.
Khi đó ma trận liên thuộc M=[m
ij
] kích thước n x m trong đó:
m
ij
=0 nếu cạnh e
j
không nối với đỉnh v
i
m
ij
=l nếu cạnh e
j
nối với đỉnh v
i
Ví dụ:
Giả sử e
1
={v
1
,v
2
};
e
2
={v
1
,v
3
}; e
3
={v
1
,v
5
};
e
4
{v
2
,v
4
}; e
5
={v
3
,v
4
};
e
6
{v
3
,v
5
}; e
7
={v
4
,v
5
};
Khi đó ma trận liên thuộc tương ứng sẽ là
e1 e2 e3 e4 e5 e6 e7
v1 1 1 1 0 0 0 0
v2 1 0 0 1 0 0 0
v3 0 1 0 0 1 1 0
v4 0 0 0 1 1 0 1
v5 0 0 1 0 0 1 1
4.5.3. Danh sách kề
Biểu diễn đồ thị bởi danh sách kề là cách liệt kê tất cả các cạnh của đồ
thị {(v
1
,v
2
); (v
1
,v
3
); (v
1
,v
5
); (v
2
,v
4
); (v
3
,v
4
}); (v
3
,v
5
}); (v
4
,v
5
)};. Hoặc là danh
sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị.
v
1
v
2
v
4
v
5
v
3
Đồ thị Nguyễn Thế Vinh-ĐHKH
73
Ví dụ:
Danh sách đỉnh kề
Đỉnh Đỉnh nối
v
1
v
2
, v
3 ,
v
5
v
2
v
1
,v
4
v
3
v
1
, v
4
,v
5
v
4
v
2
,v
3
,v
5
v
5
v
1
,v
3 ,
v
4
Người ta dùng danh sách liên kết đơn thuận hoặc nghịch để biểu diễn
chúng dưới dạng đỉnh kề hoặc cạnh kề.
4.6. THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ.
Một vấn đề quan trọng trong lí thuyết đồ thị là bài toán duyệt tất cả các
đỉnh có thể đến được từ một đỉnh xuất phát S nào đó của đồ thị. Vấn đề này
đưa về bài toán liệt kê mà yêu cầu không được bỏ sót hay lặp lại bất kì đỉnh
nào. Chính vì vậy chúng ta phải xây dựng những thuật toán cho phép duyệt
một cách có hệ thống các đỉnh, những thuật toán như vậy được gọi là thuật
toán tìm kiếm trên đồ thị. Dưới đây sẽ trình bày hai thuật toán cơ bản nhất là
tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng.
4.6.1. Tìm kiếm theo chiều sâu DFS (Depth First Search)
Tư tưởng của thuật toán dựa trên nhận xét sau đây: Trước hết xét mọi
đỉnh u kề với S tất nhiên sẽ tới được S, như vậy với mỗi đỉnh v kề với u cũng
sẽ tới được từ S và cứ tiếp tục như vậy v lại đóng vai trò của u…
Điều đó gợi ý cho chúng ta xây dựng một thủ tục duyệt đệ quy xuất
phát từ một đỉnh u bất kì ta sẽ tới được đỉnh v chưa thăm kề với u. Ta sử dụng
kĩ thuật đánh dấu các đỉnh đã thăm Free[u] tương ứng với TRUE hoặc FALSE
và để lưu lại đường đi ta sử dụng kĩ thuật lưu vết T[v]=u có nghĩa là đỉnh u
liền trước đỉnh v. Quá trình tìm kiếm kết thúc khi tới được đỉnh đích F.
Đồ thị Nguyễn Thế Vinh-ĐHKH
74
Procedure DFS(u∈V);
Begin
Free[u]:=false;
for (∀v∈V: Free[v]) and ((u,v) ∈ E) do
begin
T[v]:=u;
DFS(v);
end;
End;
Ví dụ:
Thứ tự các đỉnh duyệt theo chiều sâu bắt đầu từ đỉnh s sẽ là:
s, w, v, t, x, u, y, z.
Trong phương pháp này mỗi lần duyệt một đỉnh ta duyệt đến tận cùng
mỗi nhánh rồi mới chuyển sang duyệt nhánh khác. Thuật toán duyệt theo
chiều sâu, đỉnh được thăm càng muộn càng sớm trở thành duyệt xong. Do vậy
Thuật toán được tổ chức dưới dạng ngăn xếp STACK để lưu trữ các đỉnh đang
duyệt là thích hợp nhất.
4.6.2. Tìm kiếm theo chiều rộng BFS (Breadth First Search)
Tư tưởng thuật toán giống như duyêt theo chiều sâu, tuy nhiên cơ sở
của phương pháp này là "lập lịch" để duyệt các đỉnh thứ tự ưu tiên là chiều
rộng nghĩa là: Bắt đầu từ một đỉnh u nào đó sẽ thăm tất cả các đỉnh kề với u,
sau khi thăm u sẽ thăm đỉnh v với thứ tự ưu tiên là đỉnh gần với u nhất. Quá
trình tìm kiếm kết thúc khi tới được đỉnh đích F.
Giả sử ta có một danh sách "chờ" chưa thăm. Tại mỗi bước ta thăm một
đỉnh đầu danh sách và cho những đỉnh chưa thăm "xếp hàng". Vì nguyên tắc
đó nên danh sách các đỉnh chờ sẽ được tổ chức dưới dạng hàng đợi (QUEUE)
u
s
v
w
t
x
y
z
Đồ thị Nguyễn Thế Vinh-ĐHKH
75
với thủ tục Push(v) đẩy đỉnh v vào hàng đợi và hàm Pop trả về một đỉnh lấy ra
từ hàng đợi.
Procedure BFS(v
0
∈V);
Begin
Free[v
0
]:=false; Queue:=Φ; push(v
0
);
repeat
u:=pop;
for (∀v∈V: Free[v]) and ((u,v) ∈ E) do
begin
T[v]:=u; free[v]:=false; push(v);
end;
until (Queue=Φ);
End;
Ví dụ:
Thứ tự các đỉnh duyệt theo chiều rộng bắt đầu từ đỉnh s sẽ là:
s, w, y, v, z, x, t, u.
Chi phí về thời gian trong quá trình tìm kiếm trên đồ thị phụ thuộc vào
việc biểu diễn đồ thị, với mỗi phương pháp biểu diễn đồ thị (n đỉnh và m
cạnh) khác nhau sẽ có chi phí về mặt thời gian khác nhau.
Nếu biểu diễn bằng danh sách kề, cả hai thuật toán đều có độ phức tạp
tính toán là O(n+m). Đây là cài đặt tốt nhất
Nếu biểu diễn bằng ma trận kề thì độ phức tạp tính toán là O(n+n
2
)
Nếu biểu diễn bằng danh sách cạnh, khi duyệt một đỉnh u sẽ phải duyệt
tất cả các cạnh, nên độ phức tạp tính toán là O(n.m). Đây là cài đặt tồi nhất.
u
s
v
w
t
x
y
z
Đồ thị Nguyễn Thế Vinh-ĐHKH
76
4.7. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER.
Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố
lời giải “bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler
(1707-1783). Thành phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc
Nga) được chia thành bốn vùng bằng các nhánh sông Pregel, các vùng này
gồm hai vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa hai nhánh
của sông Pregel. Vào thế kỷ 18, người ta xây bảy chiếc cầu nối các vùng này
với nhau.
G
Dân thành phố từng thắc mắc: “Có thể nào đi dạo qua tất cả bảy cầu,
mỗi cầu chỉ một lần thôi không?”. Nếu ta coi mỗi khu vực A, B, C, D như một
đỉnh và mỗi cầu qua lại hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ
của Konigsberg là một đa đồ thị G như hình trên.
Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần có thể
được phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong
đa đồ thị G chứa tất cả các cạnh?
4.7.1. Định nghĩa: Chu trình đơn chứa tất cả các cạnh của đồ thị G
được gọi là chu trình Euler. Đường đi Euler trong G là đường đi đơn chứa mọi
cạnh của G. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler, và gọi
là đồ thị nửa Euler nếu nó có đường đi Euler.
Điều kiện cần và đủ để một đồ thị là đồ thị Euler được Euler tìm ra vào
năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thời đó về bảy cái cầu
ở Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị.
A D
B
C
D
A
C
B
Đồ thị Nguyễn Thế Vinh-ĐHKH
77
Ví dụ: Đồ thị G
1
trong hình là đồ thị Euler vì nó có chu trình Euler a, e,
c, d, e, b, a. Đồ thị G
3
không có chu trình Euler nhưng nó có đường đi Euler a,
c, d, e, b, d, a, b, vì thế G
3
là đồ thị cửa Euler. Đồ thị G
2
không có chu trình
cũng như đường đi Euler.
Đồ thị G
1
, G
2
, G
3
4.7.2. Định lý 1: Một đa đồ thị liên thông có chu trình Euler khi và chỉ
khi mọi đỉnh của nó đều có bậc chẵn.
Để chứng minh định lí ta chứng minh bổ đề sau
Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa
chu trình đơn.
Chứng minh: Nếu G có cạnh bội hoặc có khuyên thì khẳng định của bổ
đề là hiển nhiên. Vì vậy giả sử G là một đơn đồ thị. Gọi v là một đỉnh nào đó
của G. Ta sẽ xây dựng theo quy nạp đường đi từ v tới v
1
, v
1
tới v
2
…
trong đó v
1
là đỉnh kề với v, cứ như vậy chọn v
i+1
là đỉnh kề với v
i
và v
i+1
≠ v
i-1
(có thể chọn như vậy vì deg(v
i
) ≥ 2), v
0
= v. Do tập đỉnh của G là hữu hạn, nên
sau một số hữu hạn bước ta phải quay lại một đỉnh đã xuất hiện trước đó. Gọi
k là số nguyên dương đầu tiên để v
k
=v
i
(0≤i<k). Khi đó, đường đi v
i
, v
i+1
, ,
v
k-1
, v
k
(v
k
= v
i
) là một chu trình đơn cần tìm.
Chứng minh định lí:
Điều kiện cần: Giả sử G là đồ thị Euler, tức là tồn tại chu trình Euler P
trong G. Khi đó cứ mỗi lần chu trình P đi qua một đỉnh nào đó của G thì bậc
của đỉnh đó tăng lên 2. Mặt khác, mỗi cạnh của đồ thị xuất hiện trong P đúng
một lần. Do đó mỗi đỉnh của đồ thị đều có bậc chẵn.
v
v
1
v
2
Không có nhận xét nào:
Đăng nhận xét