Đồ thịlà một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh đó.
Ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng các cạnh nối các cặp đỉnh của đồ thị.
V, Elà các tập hữu hạn và không rỗng các phần tử nào đó và E Í V x V.
· G = (V,E) gọi là đồ thị hữu hạn.
o Mỗi phần tử v Î V gọi là một đỉnh của đồ thị
o Mỗi phần tử e =(x,y) Î E gọi là một cạnh của đồ thị
o V gọi là tập các đỉnh, E gọi là tập các cạnh
o n= |V|, m=|E|
Đơn đồ thị, đa đồ thị
Đồ thị G = (V,E) gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnh và không có khuyên
Đồ thị G = (V,E) gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh trở lên và không có khuyên
Giả đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết khác nhau) của V gọi là các cạnh.Các e được gọi là khuyên nếu có dạng e=(u,u)
Đồ thị có hướng
G = (V,E) là đồ thị có hướng nếu với mọi cạnh e=(x,y) Î E có phân biệt thứ tự các đỉnh x và y, có hướng x đến y, hay
(x,y) ¹ (y,x)
Đối với một cung e = (x, y):
x là đỉnh đi (gốc,đầu)
y là đỉnh đến(ngọn, cuối)
Cung e đi từ x và đến y
Đồ thị có hướng
ChoG=(V,E) là một đồ thị có hướng và e=(vi,vj)ÎE :
– vjđược gọi là đỉnh sau của vi
– vilà một đỉnh trước của vj
• Tập các đỉnh sau và đỉnh trước của vi lần lượt được kí hiệu là G (vi) và G-1(vi)
G (x)= {y Î V | (x,y) ÎE}
• G=(V,E)= (V, G)
Đồ thị vô hướng
• G = (V,E) là đồ thị vô hướng nếu với mọi cạnh e=(x,y) Î E không phân biệt thứ tự các đỉnh x và y, tức là từ x đến y không kể hướng, hay (x,y) = (y,x)
Đồ thị có trọng số
• Một đồ thị G = (V,E) gọi là có trọng lượng hay trọng số
nếu mỗi cạnh(hoặc cung) được gán 1 số,
• nghĩa là có một ánh xạ w: E àR.
• Khi đó w(e) gọi là trọng lượng của e.
Các thuật ngữ cơ bản
Kề nhau
• Cho G = (V,E) và e =(x,y) Î E là một cạnh nối đỉnh x và y. Khi đó ta nói e là cạnh chứa đỉnh x,y hoặc x,y là các đỉnh thuộc cạnh u. Khi đó x,y được gọi là hai đỉnh kề nhau
• Hai cạnh kề nhau nếu giữa chúng có đỉnh chung.
– Ví dụ với u=(x,y) và v =(y,z) thì u,v là hai cạnh kề nhau
Bậc của đỉnh
• G=(V,E) có hướng và vi ÎV
– nửa bậc trong(nửa bậc vào) = số các cung kết thúc tại (hay đi vào) vi : deg- (vi)= | G -1(vi) |
– nửa bậc ngoài (nửa bậc ra) = số các cung khởi đầu từ(hay đi ra từ) vi : deg+ (vi)= | G (vi) |
– bậc của vi : deg(vi) =deg- (vi) + deg+ (vi)
• G=(V,E) vô hướng và vi ÎV
– bậc của vi : deg(vi) = số cạnh kề với vi, trong đó một khuyên được đếm là 2
• Đỉnh có bậc = 0 được gọi là đỉnh cô lập
• Đỉnh có bậc = 1 được gọi là đỉnh treo và cung (cạnh) tới của nó được gọi là cạnh treo
• Sự liên hệ giữa đỉnh và cạnh
– Nếu G có hướng thì
–
– Số đỉnh bậc lẻ là số chẵn
3.3.Một số dạng đồ thị đặc biệt
Đồ thị đủ (vô hướng) Kn
• Là đơn đồ thị cấp n và giữa 2 đỉnh bất kỳ đều có một cạnh(mỗi đỉnh của đồ thị được nối đến tất cả các đỉnh khác trong đồ thị)
• Một đồ thị đủ có n đỉnh sẽ có cạnh
• Một đồ thị có hướng G gọi là đủ nếu đồ thị vô hướng tương ứng của nó là đầy đủ
• Cho G=(V,E) là đồ thị có hướng. Ta bảo
– Đồ thị đối xứng : (x,y) Î E è(y,x) Î E
Đồ thị phản xứng : (x,y) Î E è (y,x) Ï E.
– G là đối xứng đủ nếu G đơn và giữa 2 đỉnh có 2 cung ngược chiều nhau
G là phảnxứng đủ hay 1 vòng thi đấu nếu G đơn và giữa 2 đỉnh có đúng 1 cung. Kí hiệu Tn
– G là giả đối xứng hay cân bằng nếu d-(vi) = d+(vi), "vi Î V
– G là k-đều nếu G đơn và d-(vi) = d+(vi)=k, "vi Î V
– Cho G=(V,E) là đồ thị vô hướng. Ta bảo
– G là k-đều nếu G đơn và d(vi) =k, " "vi Î V
– Chu trình(vòng) Cn , với n ³ 3,là một đồ thị có n đỉnh v1, v2,…,vnvà các cạnh {v1, v2}, {v2, v3},…, {vn - 1, vn} và {vn, v1}
– G gọi là một bánh xe nếu G có :
– n-1 đỉnh và n-1 cạnh tạo thành một đa giác đều
– n-1 đỉnh của nó đều nối 1 đỉnh thứ n ở tâm đa giác.
– Kí hiệu Wn
Ø Đồ thị lưỡng phân
– G gọi là lưỡng phân nếu V có thể phân hoạch thành V1, V2sao cho mọi cạnh của G đều nối 1 đỉnh trong V1 với một đỉnh trong V2
– Nếu G đơn và mọi đỉnh trong V1 đều nối với tất cả các đỉnh trong V2thì G gọi là đồ thị lưỡng phân đủ, ký hiệu Kn,m với n=|V1| và m=|V2|. Đặc biệt K1,m gọi là đồ thị ngôi sao
Ø Đồ thị con
• Nếu trong đồ thị ta bỏ đi một số đỉnh nào đó và các cạnh chứa đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị đã cho.
• Nếu trong đồ thị ta bỏ đi một số cạnh giữ nguyên các đỉnh thì phần còn lại của đồ thị được gọi là đồ thị bộ phận của đồ thị đã cho.
• Cho G = (V,E) và G’ = (V’,E’) là 2 đồ thị cùng có hướng hoặc cùng không có hướng
• G’ được gọi là đồ thị con của G, kí hiệu G’ £ G nếu V’ Í V, E’ Í E và (vi,vj) Î E’ è vi, vj ÎV’
• Nếu G’ £ G với V’=V thì G’ gọi là đồ thị bộ phậnhay đồ thị khung của G.
• Nếu V’=V và E’=E – {e}, e Î E thì G’ được viết là G – e
Ø Đồ thị bù
• Cho Kn = (V, E) và G = (V, E1) là đồ thị khung của Kn
• Đặt = (V, E2) với E2 = E – E1 thì gọi là đồ thị bù của G
• Kn= (V, E1 ÈE2) và E1 Ç E2 = Æ
Ø Đẳng cấu(đẳng hình) đồ thị
• Hai đồ thị G = (V,E) và G’ = (V’,E’) gọi là đẳng cấu với nhau nếu :
– có một phép tương ứng 1 – 1(song ánh) giữa 2 tập V, V’
– và có một phép tương ứng 1 – 1 giữa 2 tập hợp E, E’
Sao cho:
nếu cạnh e = (v,w) Î E tương ứng với cạnh
e’ = (v’,w’) Î E’ thì cặp đỉnh v, w Î V cũng là tương ứng của cặp đỉnh v’, w’ Î V
• G, G’ đẳng cấu nếu tồn tại một song ánh j: VàV’ sao cho: (i, j) Î E (j(i), j(j)) Î E’.
• Nếu G, G’ là đẳng cấu qua ánh xạ j thì hai đồ thị:
• Có cùng số đỉnh, tức là |V| = |V’|
• Có cùng số cạnh: |E| = |E’|
• Có cùng số đỉnh với bậc cho sẵn
• Số đỉnh kề với đỉnh i Î V và j (i) Î V’ là như nhau.
3.4. Dây chuyền, đường đi,
chu trình, mạch. Đồ thị liên thong
• Dây chuyền trong một đồ thị không có định hướng: một dãy liên tiếp các cạnh, sao cho mỗi một cạnh có một đỉnh chung với cạnh tiếp theo.
• Chu trình: dây chuyền có đỉnh khởi đầu và đỉnh kết thúc trùng nhau
• Dây chuyền sơ cấp: không có đỉnh nào xuất hiện quá một lần
• Dây chuyền đơn: không có cạnh nào xuất hiện quá 1 lần
• chu trình đơn và chu trình sơ cấp?
• Đường và mạch là khái niệm dây chuyền và chu trình trong trường hợp đồ thị có định hướng
Ø Đồ thị vô hướng liên thong
• Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
• Trên V ta định nghĩa quan hệ tương đương ~ như sau:
x ~ y ó x = y hay có một dây chuyền nối x và y
Nếu x ~ y thì ta nói x liên thông với y
Quan hệ ~ sẽ phân G thành các lớp tương đương gọi là các thành phần liên thông.
Nếu G chỉ có 1 thành phần liên thông thì G liên thông
• Cho đồ thị vô hướng G = (V, E) liên thông
– Đỉnh i gọi là điểm khớp của G nếu G-i không liên thông
– Cạnh e Î E gọi là cầu nếu G-e không liên thông
– Số liên thông cạnh của G, kí hiệu là e(G) là số cạnh ít nhất xoá đi G không còn liên thông(1 đỉnh xem như không liên thông)
– Số liên thông đỉnh của G, kí hiệu là v(G) là số đỉnh ít nhất xoá đi G không còn liên thông
Ø Đồ thị hữu hướng liên thông mạnh
• Đồ thị có hướng G = (V, E) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó
• Trên V ta định nghĩa quan hệ tương đương ~ như sau
x ~ y ó x = y hay có một đường đi từ x đến y và có một đường đi từ y đến x
Nếu x ~ y thì ta nói x liên thông mạnh với y
Quan hệ ~ sẽ phân G thành các lớp tương gọi là các thành phần liên thông mạnh.
Nếu G chỉ có 1 thành phần liên thông mạnh thì G liên thông mạnh.
• Đồ thị có hướng G = (V, E) được gọi là liên thông yếu nếu đồ thị ị CHƯƠNG 6:Đồ thị và cây
Ø Duyệt đồ thịtheo chiều sâu – DFS
Giải thuật:
for (all(x)ÎV) Đd(x)=0; // Khởi tạo
procedure DS(D:đỉnh)
• Đd(D)=1;
• For (all(x)ÎV(D)) //V(D):tập các đỉnh kề của D
if (Đd(x)== 0) DS(x);
Ø Duyệt theo chiều rộng – BFS
Giải thuật:
• for (all(x) ÎV) Đd(x)=0;
• empty(Q); //Khởi tạo hàng đợi Q
• Bắt đầu duyệt từ đỉnh v
enqueue(v,Q);
Đd(v)=1;
while (Q<>Æ)
x=top(Q); dequeue(Q);
for (all(y) ÎV(x))
if(Đd(y)=0) - Đd(y)=1;
- enqueue(y,Q);
Định nghĩa và tính chất
Ø Định nghĩa Cây.
a) Cho G là đồ thị vô hướng. G được gọi là một cây nếu G liên thông và không có chu trình đơn.
b) Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.
Ø Định nghĩa cây khung.
Cho G = (V,E) là đồ thị vô hướng liên thông.
T = (V, E’) với E’Í E.
Nếu T là một cây thì T được gọi là cây khung(haycây tối đại, hay cây bao trùm) của đồ thịG.
Ø Định nghĩa Cây khung nhỏ nhất.
Cho G là đồ thị có trọng số. Cây khung T của G được gọi là cây khung nhỏ nhất (cây tối đại nhỏ nhất, cây bao trùm nhỏ nhất, cây khung tối tiểu) nếu nó là cây khung của G mà có trọng số nhỏ nhất.
Cây khung ngắn nhất
Thuật toán tìm cây khung ngắn nhất
a)Thuật toán Kruscal:
Cho G là đồ thị liên thông, có trọng số, n đỉnh.
Bước 1.Trước hết chọn cạnh có trọng số nhỏ nhất e1 trong các cạnh của G.
Bước 2.Khi đã chọn k cạnh e1,e2,…ek thì chọn tiếp cạnh
ek+1 ngắn nhất trong các cạnh còn lại của G sao cho không
tạo thành chu trình với các cạnh đã chọn trước.
Bước 3.Chọn đủ n-1 cạnh thì dừng.
b)Thuật toán Prim.
Bước 1. Chọn 1 đỉnh bất kỳ v1 để có cây T1 chỉ gồm 1
đỉnh.
Bước 2. Khi đã chọn cây Tk thì chọn tiếp cây
Tk+1 = TkÈ ek+1. Trong đó ek+1là cạnh có trọng số nhỏ nhất trong các cạnh có một đầu mút thuộc Tkvà đầu mút kia không thuộc Tk
Bước 3. Chọn được cây Tn-1 thì dừng.
Chương 7:
Bài toán đường đi ngắn nhất
THUẬT TOÁN DIJKSTRA
• Thuật toán 8.2
1. Với đỉnh xuất phát a, gán nhãn l(a) = 0, các đỉnh khác gán nhãn ¥
2. Nếu có cạnh (i, j) mà đỉnh i đã được gán nhãn và đỉnh j chưa được gán nhãn hoặc đỉnh j đã được gán nhãn nhưng l(i)+ c(i,j) < l(j) thì giảm nhãn:
l(j) = l(i) + c(i,j).
3. Lặp lại bước 2 cho đến khi không gán hoặc giảm nhãn được nữa.
Định lý 8.1: Tại mỗi đỉnh b giá trị nhãn l(b) cuối cùng (nếu có) chính là độ dài của đường đi ngắn nhất từ đỉnh a đến đỉnh b.
Chứng minh:
Sau khi đã thực hiện xong thuật toán trên, nếu nhãn l(b) xác định thì ta có đường đi từ đỉnh a tới đỉnh b.
Khôi phục đường đi từ a đến b như sau:
Xuất phát từ đỉnh b, tìm cạnh có đỉnh cuối là b và
đỉnh đầu là i sao cho:
l(i) + c(i,b) = l(b).
Đỉnh i như thế chắc chắn phải tồn tại vì xảy ra đẳng
thức ở lần gán hoặc giảm nhãn l(j) cuối cùng.
Cứ tiếp tục như thế cho đến khi gặp đỉnh a.
Giả sử ta nhận được dãy các cạnh:
(a, a1), (a1, a2) , ... ,(ak-1, b)
mà trên đó:
l(a) + c(a,a1) = l(a1)
l(a1) + c(a1,a2) = l(a2)
.. . .. . . . .. .. .. . . .. .. . .
l(ak-1) + c(ak-1,b) = l(b).
Cộng từng vế và khử các giá trị chung ở cả hai vế ta có:
c(a,a1) + c(a1,a2) + ... + c(ak-1,b) = l(b).
Vậy giá trị nhãn l(b) chính là độ dài đường đi nói trên.
Bất kỳ đường đi nào khác từ đỉnh a đến đỉnh b cũng
có các hệ thức tương tự nhưng có dấu ³.
Vậy nhãn l(b) là độ dài của đường đi ngắn nhất.
Để đơn giản việc tính toán, ta xây dựng ma trận trọng số C :
c(i,j) , nếu (i, j) Î E,
C[i,j] = ¥ , nếu (i, j) Ï E,
0 , nếu i = j.
1 procedure DIJKSTRA(a) ;
2 {
3 for (j ÎV )
4 { L[j] = C[a, j] ; Truoc[j] = a;}
5 T = V \ {a} ;
6 while (T ¹ Æ )
7 {
8 chọn đỉnh i Î T mà L[i] = =min {L[j] ½ j ÎT } ;
9 T = T \ {i} ;
10 for (jÎ T)
11 if (L[j] > L[i] + C[i, j])
12 {
13 L[j] = L[i] + C[i, j] ;
14 Truoc[j] = i ;
15 }
18 }
19 }
Biến mảng Truoc dùng để khôi phục đường đi. (đưa ra các đỉnh nằm trên đường đi)
0 nhận xét:
Đăng nhận xét