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=(v_i,v_j)ÎE :

–       v_j được gọi là đỉnh sau của v_i

–       v_i là một đỉnh trước của v_j

•         Tập các đỉnh sau và đỉnh trước của v_i lần lượt được kí hiệu là G (v_i) và G^-1(v_i)

                    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à v_i Î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) v_i  : deg^- (v_i)= | G ^-1(v_i) |

–       nửa bậc ngoài (nửa bậc ra) = số các cung khởi đầu từ(hay đi ra từ) v_i :  deg⁺ (v_i)= | G (v_i) |

–       bậc của v_i : deg(v_i) =deg^- (v_i) + deg⁺ (v_i)

•         G=(V,E) vô hướng và v_i ÎV

–       bậc của v_i  : deg(v_i) = số cạnh kề với v_i, 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) K_n

•         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ả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 T_n

–       G là giả đối xứng hay cân bằng nếu d^-(v_i) = d⁺(v_i), "v_i Î V

–       G là k-đều nếu G đơn và d^-(v_i) = d⁺(v_i)=k, "v_i Î V

–       Cho G=(V,E) là đồ thị vô hướng. Ta bảo

–       G là k-đều nếu G đơn và d(v_i) =k, " "v_i Î V

–       Chu trình (vòng) C_n , với n ³ 3, là một đồ thị có n đỉnh v₁, v₂,…,v_n và các cạnh {v₁, v₂}, {v₂, v₃},…, {v_{n - 1}, v_n} và {v_n, v₁}

–       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 W_n

Ø Đồ thị lưỡng phân

–       G gọi là lưỡng phân nếu V có thể phân hoạch thành V_1, V₂ sao cho mọi cạnh của G đều nối 1 đỉnh trong V₁ với một đỉnh trong V₂

–       Nếu G đơn và mọi đỉnh trong V₁ đều nối với tất cả các đỉnh trong V₂ thì G gọi là đồ thị lưỡng phân đủ, ký hiệu K_n,m với n=|V₁| và m=|V₂|. Đặc biệt K_1,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à (v_i,v_j) Î E’ è v_i, v_j Î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 K_n = (V, E) và G = (V, E₁) là đồ thị khung của K_n

•         Đặt     = (V, E₂) với E₂ = E – E₁ thì      gọi là đồ thị bù của G

•         K_n = (V, E₁ ÈE₂) và E₁ Ç  E₂ = Æ

Ø Đẳ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(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 e₁ trong các cạnh của G.

Bước 2.Khi đã chọn k cạnh e₁,e₂,…e_k thì chọn tiếp cạnh

e_k+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ỳ v₁ để có cây T₁  chỉ gồm 1

đỉnh.

Bước 2. Khi đã chọn cây T_k thì chọn tiếp cây

T_k+1 = T_kÈ e_k+1. Trong đó e_k+1 là cạnh có trọng số nhỏ nhất trong các cạnh có một đầu mút thuộc T_k và đầu mút kia không thuộc T_k

Bước 3. Chọn được cây T_n-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, a₁) , (a₁, a₂) ,  ...  , (a_k-1, b)  

mà trên đó:    

                        l(a)    +  c(a,a₁)    =  l(a₁)

                        l(a₁)   +  c(a₁,a₂)  =  l(a₂)

                        .. . ..   . . . .. .. . . . . . . .. . .

                        l(a_k-1) + c(a_k-1,b)  =  l(b).

Cộng từng vế và khử các giá trị chung ở cả hai vế ta có: 

        c(a,a₁) + c(a₁,a₂) + ... + c(a_k-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)