Công nghệ Thông tin

TOÁN RỜI RẠC
Chương III
Đồ thị

Đồ thị
Những khái niệm và tính chất cơ bản
Định nghĩa đồ thị

Định nghĩa 1. Đồ thị vô hướng G = (V, E) gồm:
i) V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh (vertex) của G.
ii) E là đa tập hợp gồm các cặp không sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh (edge) của G. Ký hiệu uv.
3
4
Ta nói cạnh uv nối u với v, cạnh uv kề với u,v.
Nếu uvE thì ta nói đỉnh u kề đỉnh v.
Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song.
Cạnh uu có hai đầu mút trùng nhau gọi là một khuyên.
Chú ý
5
Những khái niệm và tính chất cơ bản
6
Định nghĩa 2. Đồ thị vô hướng không có cạnh song song và không có khuyên gọi là đơn đồ thị vô hướng.
Định nghĩa 3. Đồ thị vô hướng cho phép có cạnh song song nhưng không có khuyên gọi là đa đồ thị vô hướng.
Định nghĩa 4. Đồ thị vô hướng cho phép có cạnh song song và có khuyên gọi là giả đồ thị
7
Những khái niệm và tính chất cơ bản
8
b
c
9
Những khái niệm và tính chất cơ bản
10
Những khái niệm và tính chất cơ bản
11
Những khái niệm và tính chất cơ bản
Định nghĩa 5
12
Đa đồ thị có hướng G =(V,E) gồm:
i) V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh của G.
ii) E là đa tập hợp gồm các cặp có sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cung (cạnh) của G. Ký hiệu uv.
Ta nói cung uv đi từ u đến v, cung uv kề với u,v
Những khái niệm và tính chất cơ bản
13
a
b
c
d
Nếu uv là một cung thì ta nói:
Đỉnh u và v kề nhau.
Đỉnh u gọi là đỉnh đầu (gốc), đỉnh v là đỉnh cuối (ngọn) của cung uv. Đỉnh v là đỉnh sau của đỉnh u.
Hai cung có cùng gốc và ngọn gọi là cung song song.
Cung có điểm gốc và ngọn trùng nhau gọi là khuyên.
14
Chú ý
Những khái niệm và tính chất cơ bản
15
Những khái niệm và tính chất cơ bản
Định nghĩa 6. Đa đồ thị có hướng không chứa các cạnh song song gọi là đồ thị có hướng
16
Cho đồ thị vô hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh kề với v, trong đó một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy.
19
Những khái niệm và tính chất cơ bản
Bậc của đỉnh
20
c
Bậc đỉnh a:
deg(a) = 2
Bậc đỉnh b:
deg(b) = 5
Bậc đỉnh c:
deg(c) = 3
Bậc đỉnh d:
deg(d) = 2
21
Bậc của các đỉnh?
1) deg-(v):= số cung có đỉnh cuối là v, gọi là bậc vào của v.
2) deg +(v):= số cung có đỉnh đầu là v,gọi là bậc ra của v
3) deg(v):= deg- (v) + deg+(v)
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo
22
Những khái niệm và tính chất cơ bản
Cho đồ thị có hướng G = (V, E), vV
23
24
a
b
d
c
f
e
Bậc đỉnh a:
Bậc đỉnh b:
Bậc đỉnh c:
Bậc đỉnh d:
Bậc đỉnh e:
Bậc đỉnh f:
deg-(a)= 1 ; deg+(a)=1
deg-(b)= 1 ; deg+(b)=3
deg-(c)= 1 ; deg+(c)=2
deg-(d)= 0 ; deg+(d)=0
deg-(e)= 1 ; deg+(e)=0
deg-(f)= 2 ; deg+(f)=0
Cho đồ thị G = (V,E), m là số cạnh (cung)

25
Những khái niệm và tính chất cơ bản
Định lí
1)
2) Nếu G có hướng thì:
3) Có một số chẵn các đỉnh bậc lẻ
Ta sử dụng ma trận kề.

Cho G = (V,E) với V={1,2,…,n}.
Ma trận kề của G là ma trận A = (aij)n xác định như sau:

aij = số cạnh (số cung) đi từ đỉnh i đến đỉnh j
26
Biểu diễn ma trận của đồ thị.
27
c
Tìm ma trận kề
28
Tìm ma trận kề
Định nghĩa
Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). Ta nói rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn tại song ánh f :V→ V’sao cho:
uv là cạnh của G  f(u)f(v) là cạnh của G’
29
Đẳng cấu
Chú ý
30
Nếu G và G’ là các đơn đồ thị vô hướng đẳng cấu qua ánh xạ f thì chúng có:
Cùng số đỉnh
Cùng số cạnh
Cùng số đỉnh với bậc cho sẵn (vd: số đỉnh bậc 2 của G và G’ bằng nhau)
deg v = deg f(v)
Đẳng cấu
31
Đẳng cấu
Không có đỉnh bậc 1
Không đẳng cấu
32
Ví dụ
a
b
c
d
e
f
1
2
3
6
5
4
33
Đẳng cấu
a
b
4
d
e
1
2
3
c
5
34
Không đẳng cấu
35
Đẳng cấu không?
a
b
c
d
e
Định nghĩa. Cho G = (V,E). Trên V ta định nghĩa
quan hệ tương đương như sau:
u~v  u = v hay có một đường đi từ u đến v
Nếu u~v thì ta nói hai đỉnh u và v liên thông với nhau
Mỗi lớp tương đương được gọi là một thành phần liên thông của G
Nếu G chỉ có một thành phần liên thông thì G gọi là liên thông
36
Đường đi, chu trình, đồ thị liên thông:
37
Định nghĩa. Cho G = (V,E) là đồ thị vô hướng
liên thông
Đỉnh v được gọi là đỉnh khớp nếu G – v không liên thông (G – v là đồ thị con của G có được bằng cách xoá v và các cạnh kề với v)
Cạnh e được gọi là cầu nếu G- e không liên thông( G-e là đồ thị con của G có được bằng cách xoá cạnh e).
38
Đường đi, chu trình, đồ thị liên thông:
39
Cho G = (V,E) là đồ thị vô hướng u,vV
Đường đi (dây chuyền) có chiều dài k nối hai đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau
v0e1v1e2…vk-1ekvk sao cho:
v 0=u ,v k = v, e i=v i-1v i , i=1,2,…,k
40
Đường đi, chu trình, đồ thị liên thông:
a) Đường đi không có cạnh nào xuất hiện quá một lần gọi là đường đi đơn
b) Đường đi không có đỉnh nào xuất hiện quá một lần gọi là đường đi sơ cấp
c) Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh
41
Đường đi, chu trình, đồ thị liên thông:
42
(a,e1,b,e2,c,e3,d,e4,b ) là đường đi từ đỉnh a tới đỉnh b có chiều dài là 4.
Tuy nhiên, trong trường hợp này, đồ thị của chúng ta là đơn đồ thị, do vậy có thể gọi đường đi này bằng 1 cách ngắn gọn như sau: (a,b,c,d,b)
Chu trình sơ cấp: (b,c,d,b) (b,f,e,b)
Chu trình sơ cấp nào không?
Bài toán đường đi ngắn nhất
Đồ thị không có trọng số: đường đi từ đỉnh A đến đỉnh B được gọi là ngắn nhất nếu như số cạnh nó đi qua là ít nhất.
Đồ thị có trọng số: đường đi từ đỉnh A đến đỉnh B là ngắn nhất nếu như tổng các trọng số của các cạnh là bé nhất.
Bài toán đường đi ngắn nhất
Nhiều bài toán có thể mô hình bằng đồ thị có trọng số .
Đó là đồ thị mà mỗi cạnh của nó được gán một con số
(nguyên hoặc thực) gọi là trọng số ứng với cạnh đó. Ví
dụ cần mô hình một hệ thống đường hàng không của
nước ta. Trong mô hình cơ sở, mỗi sân bay được
biểu diễn bằng một đỉnh, mỗi chuyến bay là một cạnh
nối hai đỉnh tương ứng. Nếu trong bài toán đang xét ta
cần tính đến khoảng cách giữa các chuyến bay thì cần
gán cho mỗi cạnh của đồ thị trên khoảng cách giữa các
chuyến bay tương ứng.
Bài toán đường đi ngắn nhất
Nếu quan tâm đến thời gian của mỗi chuyến bay thì ta sẽ
gán các thời lượng này cho mỗi cạnh của đồ thị . Nếu
trong bài toán đang xét chúng ta lại tính đến chi phí của
mỗi chuyến bay thì ta gán chi phí như trọng số ứng với
cạnh nối hai thành phố tương ứng. Trên hình biểu diễn
các cách gán trọng số khác nhau cho các cạnh của đồ thị
tùy theo mục đích của bài toán đặt ra.
Bài toán đường đi ngắn nhất
Khoảng cách
Bài toán đường đi ngắn nhất
Thời gian bay
Bài toán đường đi ngắn nhất
Chi phí
Bài toán đường đi ngắn nhất
Điều kiện tồn tại:
Điều kiện cần và đủ để tồn tại đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong một đồ thị có trọng số là đồ thị phải liên thông.
Nếu hai đỉnh bất kì có đường đi ngắn nhất => đồ thị liên thông.
Nếu đồ thị liên thông
Xét hai đỉnh bất kì a và b, gọi W là tập tất cả các đường đi từ a -> b => W khác rổng, W là tập hửu hạn => trong W chọn được đường đi có tổng trọng số bé nhất.
Bài toán đường đi ngắn nhất
Giải thuật Moore_Dijkstra:
Input: G = (V, E) liên thông, có trọng số w(i, j), V= {1,……,n}
Output: đường đi ngắn nhất từ đỉnh a đến đỉnh z.
Bước 1: L(a):=0, L(ui):=, ∀v  V, va, S:=
Bước 2: nếu z  S thì đi tới bước 4.
Chọn đỉnh có nhãn bé nhất không thuộc S gọi đó là u:
S:=S U {u}
Bước 3: với mỗi đỉnh v kề u không  S
Nếu L(u)+w(u,v) < L(v)
Thì L(v):= L(u)+w(u,v)
Quay lại bước 2
Bước 4: xuất đường đi ngắn nhất từ a -> z
70
65
25
40
0
1
2
3
4
5
5
15
20
60
10
5
80
30
25
40
30
Xem đồ thị hình trên hãy tìm đường đi ngắn nhất
từ nút 0 đến nút 5 theo giải thuật Dijkstra

0
10
30
60



90

0->1->3->4->5
0->1->3->4->5
Duyệt đồ thị
Định nghĩa:




Duyệt đồ thị là hành động thăm tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần, theo một trình tự nào đó.
Có hai phương pháp duyệt cơ bản:
Duyệt theo chiều rộng.
Duyệt theo chiều sâu.
Duyệt theo chiều rộng:
Quá trình duyệt theo chiều rộng bắt đầu từ một đỉnh v nào đó của đồ thị. Sau đó thăm các đỉnh kề của v, rồi tiếp tục đến các đỉnh kề của đỉnh vừa thăm
Giải thuật này ưu tiên duyệt tất cả các đỉnh nằm lân cận với một đỉnh v đã duyệt nào đó rồi tiếp tục đến các mức tiếp theo nên gọi là duyệt theo chiều rộng.


Duyệt đồ thị – Duyệt theo chiều rộng (1)
Thực hiện các bước sau:
G(V, E), V={v1, v2, .…., vn)
Đưa đỉnh v1 vào hàng đợi
Trong khi hàng đợi khác rỗng:




Nếu thỏa yêu cầu của bài toán thì dừng.
Duyệt đồ thị – Duyệt theo chiều rộng (2)
Lấy một đỉnh từ hàng đợi v
Duyệt đỉnh v
Đưa các đỉnhkề với v nhưng chưa được duyệt
vào hàng đợi.
Duyệt đồ thị – Duyệt theo chiều rộng (2)
Giải thuật:
Dùng một mảng B có n phần tử để đánh dấu các đỉnh đã duyệt.
Procedure Bfs(v);
Begin
B[v]:=true;
Insert_queue(v,Q);
while not empty(Q) do
Begin
lấy 1đỉnh v nào đó trong hàng đợi.
For (mỗi đỉnh w kề với v ) do
if (B[w]=false) then
Begin
B[w]:=true; {duyệt W}
Insert_queue(w,Q);
End;
End;
End;
Duyệt đồ thị – Duyệt theo chiều rộng (3)
Ví dụ:





Lấy A, duyệt các đỉnh kề với A là B, C, D.
Lấy B, duyệt các đỉnh kề với B là F.
Lấy C, các đỉnh kề với C đã duyệt.
Lấy D, duyệt các đỉnh kề với D là E, G.
Lấy F, các đỉnh kề với F đã duyệt.
Lấy E, các đỉnh kề với E đã duyệt.
Lấy G. Tất cả các nút đã được duyệt nên đồ thị đã duyệt xong.
Thứ tự các đỉnh được duyệt là A, B, C, D, F, E, G.






Duyệt đồ thị – Duyệt theo chiều sâu (1)
Duyệt theo chiều sâu:
Quá trình duyệt theo chiều sâu bắt đầu từ một đỉnh nào đó của đồ thị. Sau khi thăm đỉnh này, quá trình duyệt theo chiều sâu được lặp lại với tất cả các đỉnh kề với nó cho đến khi không còn thực hiện được nữa.
Giải thuật này duyệt theo một hướng nào đó sâu nhất có thể nên gọi là duyệt theo chiều sâu.
Duyệt đồ thị – Duyệt theo chiều sâu (2)
Giải thuật:
Để xác định đỉnh nào đã thăm rồi đỉnh nào chưa thì dùng một mảng B có n phần tử tương ứng với n đỉnh để đánh dấu.
Đầu tiên B[i]:=false ứng với đỉnh i chưa được thăm.
B[i]:=true khi đỉnh i đã được thăm.

Procedure Dfs(v);
Begin
B[v]:= true;
For (mỗi đỉnh w là đỉnh kề với v) do
If B[w]= false then
Dfs(w);
End;

Duyệt đồ thị – Duyệt theo chiều sâu (3)
Ví dụ:





Duyệt A, A có các đỉnh kề là B, C, D.
Duyệt B, B có đỉnh kề chưa duyệt là F.
Duyệt F, F có các đỉnh kề chưa duyệt là D, G.
Duyệt D, D có các đỉnh kề chưa duyệt là C, E, G.
Duyệt C, các đỉnh kề với C đã duyệt.
Duyệt E, các đỉnh kề với E chưa duyệt là G.
Duyệt G. Tất cả các nút đã được duyệt nên đồ thị đã duyệt xong.
Thứ tự các đỉnh được duyệt là A, B, F, D, C, E, G.






Duyệt đồ thị – Bài tập
Bài tập:
Duyệt chiều sâu và chiều rộng cho đồ thị sau:













Cây:
1.1 Định nghĩa:
Cây là đơn đồ thị liên thông, không có chu trình
Vd: Đồ thị nào trong các đồ thị là cây.


CÂY VÀ CÂY KHUNG
1.2 Tính chất:
a. Cây có n đỉnh thì có n-1 cạnh.
Cm:
Nhận xét: cây có nhiều hơn 1 đỉnh thì có ít nhất một đỉnh treo.
Với n=1 dễ dàng thấy 1-1=0 cạnh
Giả sử cây có k đỉnh thì có k-1 cạnh
Ta chứng minh cây có k+1 đỉnh thì có k cạnh.
Theo nhận xét cây có ít nhất 1 đỉnh treo, giả sử đó là đỉnh a.
Ta xóa đi đỉnh a => đồ thị còn lại là cây có k đỉnh, có k-1 cạnh
Vậy cây ban đầu có k-1+1=k cạnh.
CÂY VÀ CÂY KHUNG(tt)
b. Trong một cây giửa hai đỉnh bất kỳ của cây có duy nhất một đường đi.
2. Cây khung:
Cho G=(V, E) là một đồ thị liên thông, cây
T gọi là cây khung của đồ thị G nếu nó đi qua tất cả các đỉnh của đồ thị G.
Điều kiện tồn tại cây khung:
Đồ thị vô hướng G(V, E) tồn tại cây khung khi và chỉ khi G là đồ thị liên thông
CÂY VÀ CÂY KHUNG(tt)
Cách tìm cây khung:
Trong khi đồ thị G có chu trình C
Xóa đi một cạnh bất kì trên C
Đồ thị G còn lại là cây khung.
Cây khung tối thiểu:
Cho G=(V, E) vô hướng liên thông có trọng số. Cây khung có tổng trọng số bé nhất gọi là cây khung tối thiểu.

CÂY VÀ CÂY KHUNG
Giải thuật tìm cây khung tối thiểu:
Giải thuật Prim:
Input: G=(V, E), V=n liên thông có trọng số
Output: Cây khung T của đồ thị
Chọn 1 đỉnh bất kỳ đưa vào T.
for i:=1 to n-1
Chọn một cạnh ei có trọng số nhỏ nhất
thỏa :
- Liên thuộc với 1 đỉnh thuộc T
- Không tạo thành chu trình trong T
3. Xuất cây khung T.
CÂY VÀ CÂY KHUNG
Giải thuật Kruskal tìm cây khung nhỏ nhất:
Input: G=(V, E), V=n liên thông có trọng số
Output: Cây khung T của đồ thị
1. T=O.
2. For i:=1 to n-1
chọn cạnh ei có trọng số nhỏ nhất không tạo thành chu trình trong T
T = T U {ei}
3. Xuất T.
CÂY VÀ CÂY KHUNG
Đường đi Euler
69
Bài toán. Thị trấn Königsberg chia thành 4 phần bởi các nhánh của dòng sông Pregel
Bốn phần này được nối kết bởi 7 cây cầu
70
Đường đi Euler
71
Đường đi Euler
Câu hỏi. Có thể đi qua bảy cây cầu mà không có cây cầu nào đi quá 1 lần
72
Đường đi Euler
A
B
C
D
A
B
C
D
73
Định nghĩa.
1. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh (cung) đúng một lần. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần.
2. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler
74
Đường đi Euler
Đường đi Euler
Điều kiện cần và đủ.
Cho G = (V,E) là đồ thị vô hướng liên thông. G là đồ thị Euler  Mọi đỉnh của G đều có bậc chẵn.
Nếu G có hai đỉnh bậc lẻ còn mọi đỉnh khác đều có bậc chẵn thì G có đường đi Euler
75
Đường đi Euler
Nhận xét.
- Nếu đồ thị G có 2 đỉnh bậc lẻ thì G có 1 đường đi Euler
- Nếu đồ thị G có 2k đỉnh bậc chẵn thì ta có thể vẽ đồ thị bằng k nét
Bắt đầu từ một đỉnh bất kỳ của G và tuân theo
qui tắc sau: Mỗi khi đi qua một cạnh nào đó thì
xoá nó đi, sau đó xoá đỉnh cô lập nếu có.
Không bao giờ đi qua một cầu trừ phi không
còn cách đi nào khác.
76
Thuật toán Fleury để tìm chu trình Euler.
Đường đi Euler
a
b
c
d
e
f
g
h
abcfdcefghbga
77
Đường đi Euler