Thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng

máy ở địa phƣơng, có một số máy chỉ có thể gửi tin đi, còn các kênh thoại cho phép truyền tin theo cả hai chiều đƣợc thay thế bởi hai cạnh có hƣớng ngƣợc chiều nhau. Hình 4. Mạng máy tính với các kênh thoại một chiều Ta đi đến định nghĩa sau: Định nghĩa 4. Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái niệm đa đồ thị có hướng: Định nghĩa 5. Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. Trong các phần tiếp theo, chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hƣớng và đơn đồ thị có hƣớng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn mỗi khi nhắc đến chúng. 11 1.2. Các thuật ngữ cơ bản Trong mục này, chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị. Trƣớc tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hƣớng. Định nghĩa 6. Hai đỉnh u và v trong đồ thị (vô hướng) G=(V, E) được gọi là liền kề nếu (u, v)E. Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta có định nghĩa sau : Định nghĩa 7. Bậc của đỉnh v trong đồ thị G=(V, E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Hình 5. Đồ thị vô hƣớng Ví dụ 1. Xét đồ thị cho trong hình 1, ta có deg(a)=1, deg(b)=4 , deg(c)=4 , deg(f)=3, deg(d)=1 , deg(e)=3 , deg(g)=0. 12 Đỉnh bậc 0 gọi là đỉnh cô lập, đỉnh bậc 1 đƣợc gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau: Định lý 1. Giả sử G=(V, E) là đồ thị vô hướng với m cạnh. Khi đó 2m=∑ deg(v) Chứng minh. Rõ ràng trong mỗi cạnh e=(u, v) đƣợc tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh Ví dụ 2. Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh ? Theo định lý 1, ta có 2m=6n. Từ đó suy ra số cạnh của đồ thị là 3n. Hệ quả. Trong đồ thị vô hƣớng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn. Chứng minh. Thực vậy, gọi O và U tƣơng ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị, ta có 2m=∑deg(v)= ∑deg(v)+ ∑deg(v) Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tƣơng tự cho đồ thị có hƣớng. Định nghĩa 8. Nếu e=(u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng 13 nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u (v) sẽ được gọi là đỉnh đầu (cuối) của cung (u, v). Tƣơng tự nhƣ khái niệm bậc, đối với đồ thị có hƣớng ta có khái niệm bán bậc ra (vào) của một đỉnh. Định nghĩa 9. Ta gọi bán bậc ra (vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và kí hiệu là deg+(v)(deg-(v)). Hình 6. Đồ thị có hƣớng G Ví dụ 3. Xét đồ thị cho trong hình 6. Ta có deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e)=2. deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2 Do mỗi cung (u, v) sẽ đƣợc tính một lần trong bán bậc vào của đỉnh v và một lần trong bán bậc ra của đỉnh u nên ta có Định lý 2. Giả sử G=(V, E) là đò thị có hướng, khi đó: ∑deg+(v)= ∑deg-(v)=|E| Rất nhiều tính chất của đồ thị có hƣớng không phụ thuộc vào hƣớng trên các cung của nó. Vì vậy, trong nhiều trƣờng hợp sẽ thuận tiện hơn nếu ta bỏ qua hƣớng trên các cung của đồ thị. Đồ thị vô hƣớng thu đƣợc bằng cách 14 bỏ qua hƣớng trên các cung đƣợc gọi là đồ thị vô hướng tương ứng với đồ thị có hƣớng đã cho. 1.3. Định nghĩa đƣờng đi, chu trình, đồ thị liên thông Định nghĩa 10. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G=(V, E) là dãy xo, x1 , ... , xn-1, xn trong đó u= x0 , v= xn, ( xi, xi+1 )  E , i= 0, 1, 2,..., n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng các cạnh: (x0, x1 ) , ( x1, x2), ... , ( xn-1, xn ). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối ( tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. Ví dụ 4. Trên đồ thị vô hƣớng cho trong hình 1: a, d, c, f, e là đƣờng đi đơn độ dài 4. Còn d, e, c, a không là đƣờng đi, do (e, c) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đƣờng đi a, b, e, d, a, b có độ dài là 5 không phải là đƣờng đi đơn, do cạnh (a, b) có mặt trong nó hai lần. Hình 7. Đƣờng đi trên đồ thị Khái niệm đƣờng đi và chu trình trên đồ thị có hƣớng đƣợc định nghĩa hoàn toàn tƣơng tự nhƣ trƣờng hợp đồ thị vô hƣớng, chỉ khác là ta chú ý đến hƣớng trên các cung. 15 Định nghĩa 11. Đường đi độ dài n từ đỉnh u đến đỉn v, trong đó n là số nguyên dương, trên đồ thị có hướng G=(V, A) là dãy xo, x1 , ... , xn-1, xn trong đó u=x0 , v=xn , ( xi, xi+1 )  A , i= 0, 1, 2,..., n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng các cung: (x0, x1 ) , ( x1, x2), ... , ( xn-1, xn ). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại. Ví dụ 5. Trên đồ thị có hƣớng cho trong hình 7: a, d, c, f, e là đƣờng đi đơn độ dài 4. Còn d, e, c, a không là đƣờng đi do (e, c) không phải là cung của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đƣờng đi a, b, e, d, a, b có độ dài là 5 không phải là đƣờng đi đơn, do cung (a, b) có mặt trong nó hai lần. Xét một mạng máy tính. Một câu hỏi đặt ra là hai máy tính bất kỳ trong mạng này có thể trao đổi đƣợc thông tin với nhau hoặc trực tiếp qua kênh nối chúng hoặc thông qua một hoặc vài máy tính trung gian trong mạng? Nếu sử dụng đồ thị để biểu diễn mạng máy tính này (trong đó các đỉnh của đồ thị tƣơng ứng với các máy tính, còn các cạnh tƣơng ứng với các kênh nối) câu hỏi đó đƣợc phát biểu trong ngôn ngữ đồ thị nhƣ sau: Tồn tại hay chăng đƣờng đi giữa mọi cặp đỉnh của đồ thị ? Định nghĩa 12. Đồ 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ó. Nhƣ vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin đƣợcvới nhau khi và chỉ khi đồ thị tƣơng ứng với mạng này là đồ thị liên thông. 16