Thứ Ba, 29 tháng 5, 2012

Toán Rời Rạc - Lý thuyết Đồ thị


Đồ 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, E là 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
       Cho G=(V,E) là một đồ thị có hướng và e=(vi,vj)ÎE :
       vj được gọi là đỉnh sau của vi
       vi là 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

         đơ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ản xứ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,…,vn và 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, V2 sao 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à mi đỉnh trong V1 đều nối với tất cả các đỉnh trong V2 thì 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ận hay đồ 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 tp 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á mt 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ó mt 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ị 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(hay câ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 Tchỉ 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+1 là cạnh có trọng số nhỏ nhất trong các cạnh có một đầu mút thuộc Tk và đầ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   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