Bài giảng môn toán rời rạc học phần lý thuyết đồ thị

Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông.. Do vậy mạng này c

MỤC LỤC 1

Chương 7 LÝ THUYẾT ĐỒ THỊ 3

7.1 MỞ ĐẦU 3

7.2 CÁC THUẬT NGỮ VỀ ĐỒ THỊ 6

7.2.1 Những thuật ngữ cơ sở 6

7.2.3 Những đồ thị đơn đặc biệt 7

7.2.4 Đồ thị phân đôi 8

7.2.5 Một vài ứng dụng của các đồ thị đặc biệt 9

7.2.6 Đồ thị con 11

7.3 BIỂU DIỄN ĐỒ THỊ VÀ SỰ ĐẲNG CẤU 11

7.3.1 Mở đầu 11

7.3.2 Biểu diễn đồ thị bằng danh sách liền kề 12

7.3.3 Ma trận liền kề, ma trận trọng số 12

7.3.4 Ma trận liên thuộc 13

7.3.5 Sự đẳng cấu của các đồ thị 13

7.4 TÍNH LIÊN THÔNG 14

7.4.1 Mở đầu 14

7.4.2 Đường đi 14

7.4.3 Tính liên thông trong đồ thị vô hướng 16

7.4.4 Tính liên thông trong đồ thị có hướng 17

7.4.5 Đường đi và sự đẳng cấu 18

7.4.6 Đếm đường đi giữa các đỉnh 19

7.4.7 Phương pháp duyệt đồ thị 20

7.5 ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON 25

7.5.1 Đường đi và chu trình EULER 25

7.5.2 Đường đi và chu trình Hamilton 34

7.6 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 36

7.6.1 Mở đầu 36

7.6.2 Thuật toán Dijkstra xác định các đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại 37

7.6.3 Thuật toán Floyd xác định đường đi ngắn nhất giữa mọi cặp đỉnh 46

7.7 ĐỒ THỊ PHẲNG 47

7.7.1 Mở đầu 47

7.7.2 Công thức Euler 48

7.7.3 Định lý Kuratowski 51

7.8 TÔ MÀU ĐỒ THỊ 52

7.8.1 Mở đầu 52

7.8.2 Những ứng dụng của bài toán tô màu đồ thị 54

7.8.3 Thuật toán tô màu đồ thị đơn 55

Chương 8 CÂY 56

8.1 MỞ ĐẦU 56

8.1.1 Cây như là các mô hình 58

8.1.2 Những tính chất của cây 59

8.2 CÁC ỨNG DỤNG CỦA CÂY 61

8.2.1 Mở đầu 61

8.2.2 Cây tìm kiếm nhị phân 61

8.2.3 Cây quyết định 62

8.2.4 Các mã tiền tố 63

8.3 CÁC PHƯƠNG PHÁP DUYỆT CÂY 64

8.3.2 Hệ địa chỉ phổ dụng 64

8.3.3 Các phương pháp duyệt cây 64

8.3.4 Các ký pháp trung tố, tiền tố và hậu tố 66

8.4 CÂY KHUNG 67

8.4.1 Mở đầu 67

8.4.2 Những thuật toán xây dựng cây khung 68

8.4.3 Kỹ thuật quay lui 70

8.5 CÂY KHUNG NHỎ NHẤT 72

8.5.1 Mở đầu 72

8.5.2 Thuật toán tìm cây khung nhỏ nhất 72

BÀI TẬP 83

Chương 7: Đồ thị 83

Chương 8: CÂY 89

TÀI LIỆU THAM KHẢO 92

3

Chương 7 LÝ THUYẾT ĐỒ THỊ

Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ 18 bởi nhà toán học Thụy Sĩ tên là Leonard Euler Ông đã dùng dồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng

Đồ thị được dùng để giải quyết nhiều bài toán khác nhau Ví dụ dùng đồ thị để xác định xem

có thực hiện được một mạch điện trên một bảng điện phẳng không Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cầu trúc khác nhau nhờ đồ thị Chúng ta cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông Chúng ta cũng có thể dùng đồ thị để lập lịch thi và phân chia kênh cho các đài truyền hình

7.1 MỞ ĐẦU

Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó Người ta thường

ký hiệu đồ thị G bằng = (V,E) , trong đó V là tập hợp các đỉnh (Vertex), E là tập hợp các cạnh (Edge) Người ta phân loại đồ thị theo các đặc tính và số cạnh nối các cặp đỉnh của đồ thị

chính nó Do vậy mạng này có thể mô hình bằng một một đơn đồ thị, bao gồm các đỉnh biểu

diễn các máy tính và các cạnh vô hướng biễu diễn các đường điện thoại nối hai đỉnh phân biệt và không có hai cạnh nối cùng một cặp đỉnh

Định nghĩa 1 Một đơn đồ thị G = (V,E) gồm một tập không 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 cạnh, đó là các cặp không thứ tự của các đỉnh phân biệt

Đôi khi có nhiều đường điện thoại giữa các máy tính trong mạng Đó là khi có sự truyền thông với cường độ cao giữa các máy tính Mạng với nhiều đường điện thoại được biểu diễn trong hình sau Đơn đồ thị không thể mô hình các mạng như thế này được Thay vào đó người

ta dùng đa đồ thị Đó là đồ thị gồm các đỉnh và các cạnh vô hướng, nhưng có thể có nhiều

cạnh nối mỗi cặp đỉnh Đơn đồ thị là một trường hợp riêng của đa đồ thị Ta không thể dùng một cặp đỉnh để xác định một cạnh trong đa đồ thị

Định nghĩa 2 Một đa đồ thị G = (V,E) gồm một tập đỉnh V và một tập cạnh E và một

hàm f từ E tới { {u,v} | u,v V, uv} Các cạnh e1 và e2 được gọi là song song hay cạnh bội nếu f(e1) = f(e2)

Một mạng máy tính có thể có đường điện thoại từ một máy tới chính nó (đường nội bộ) Ta

không thể dùng da đồ thị để mô hình các mạng như thế được vì các đa đồ thị không chứa các

khuyên Khi đó ta dùng một loại đồ thị tổng quát hơn là giả đồ thị

Định nghĩa 3 Một giả đồ thị G = (V,E) gồm một tập đỉnh V và một tập cạnh E và một

hàm f từ E tới { {u,v} | u,v V, uv} Một cạnh được gọi là một khuyên nếu f(e) = {u}

Hình 7.2 Đa đồ thị

Có thể thấy rằng các cạnh bội trong một giả đồ thị gắn liền với cùng một cặp đỉnh Tuy nhiên

ta nói rằng {u,v} là một cạnh của đồ thị G = (V,E) nếu có ít nhất một cạnh e sao cho f(e)

= {u,v} Ta sẽ không phân biệt cạnh e và tập {u,v} tương ứng với nó trừ khi đặc tính của các cạnh bội là quan trọng

Hình 7.3 Giả đồ thị

Tóm lại, giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể chứa các khuyên và các

cạnh bội Đa đồ thị là loại đồ thị vô hướng có thể chứa cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại đồ thị vô hướng không chứa cạnh bội hoặc các khuyên

Các đường điện thoại trong một mạng máy tính có thể hoạt động chỉ theo một chiều Thí dụ máy chủ ở New York có thể chỉ nhận dữ liệu từ các máy khác mà không thể gửi dữ liệu đi Khi đó các đường điện thoại hai chiều được biểu diễn bằng một cặp cạnh có chiều ngược nhau

Hình 8.4 Đơn đồ thị có hướng (có thể có khuyên nhưng không có cạnh bội cùng chiều)

có nhiều các cạnh có hướng từ một đỉnh tới một đỉnh khác (có thể tới chính nó)

Định nghĩa 5 Một đa đồ thị có hướng G = (V,E) gồm một tập đỉnh V và một tập cạnh E

và một hàm f từ E tới { (u,v) | u,v V, uv} Các cạnh e1 và e2 được gọi là song song hay cạnh bội nếu f(e1) = f(e2).(Trong định nghĩa này (u,v) là các cặp có thứ tự)

Có thể thấy rằng các cạnh bội trong một đa đồ thị có hướng gắn liền với cùng một cặp đỉnh Tuy nhiên ta nói rằng (u,v) là một cạnh của đồ thị G = (V,E) nếu có ít nhất một cạnh e sao cho f(e) = (u,v) Ta sẽ không phân biệt cạnh e và cặp đỉnh có thứ tự (u,v) tương ứng với nó trừ khi đặc tính của các cạnh bội là quan trọng

Loại đồ thị Cạnh Có cạnh bội không? Có khuyên không? Đơn đồ thị

Có

Không Không

Có

Có

Có

Định nghĩa 2 Bậc của một đỉnh trong đồ thị vô hướng 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ó Người ta ký hiệu bậc của đỉnh là deg(v)

Đỉnh cô lập là đỉnh không nối với bất kỳ đỉnh nào

(Định lý này đúng cả khi đồ thị có cạnh bội hoặc các khuyên)

Định lý 1 chỉ ra rằng tổng các bậc của tất cả các đỉnh của một đồ thị vô hướng là một số chẵn

Sự kiện đơn giản này có rất nhiều hệ quả hay, một trong số đó là Định lý 2

deg(v)

vì deg(v) là chẵn với mọi vV1, nên tổng đầu tiên là một số chẵn Suy ra tổng thứ hai cũng

là một số chẵn Tổng thứ hai có các thành phần đều là số lẻ, nên để tổng là số chẵn thì số thành phần phải là một số chẵn

Định nghĩa 3 Khi (u,v) là cạnh của đồ thị có hướng G, thì u được gọi là nối tới v, và v được gọi là được nối từ u Đỉnh u được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của

cạnh (u,v) Đỉnh đầu và đỉnh cuối của khuyên là trùng nhau

Vì các cạnh của đồ thị có hướng là các cặp có thứ tự, nên định nghĩa bậc của đỉnh cần phải tinh hơn để phản ánh được số các cạnh nhận đỉnh này là đỉnh đầu ra (ra khỏi đỉnh này) và số các cạnh nhận đỉnh này là đỉnh cuối (đi vào đỉnh này)

Định nghĩa 4 Trong đồ thị có hướng, bậc- vào của đỉnh v ký hiệu là deg-(v) là số các cạnh

có đỉnh cuối là v Bậc- ra của đỉnh v ký hiệu là deg+(v) là số các cạnh có đỉnh đầu là v (Như vậy một khuyên tại một đỉnh sẽ góp thêm 1 đơn vị vào bậc vào và 1 đơn vị vào bậc ra của đỉnh này)

7

Ví dụ 3

Vì mỗi cạnh (hay còn gọi là cung) có một đỉnh đầu và một đỉnh cuối nên tổng các bậc vào và tổng các bậc ra của tất cả các đỉnh trong một đồ thị có hướng là như nhau và bằng số cạnh của nó Đó chính là nội dung của định lý sau

Định nghĩa 5 Đồ thị vô hướng G = (V,E)

được gọi là đồ thị đầy đủ, nếu mỗi cặp đỉnh

đều có cạnh nối giữa chúng

Hình 8.5 Đồ thị vô hướng đầy đủ

Đồ thị có hướng G = (V,E) được gọi

là đồ thị đầy đủ, nếu mỗi cặp đỉnh đều

có cung nối giữa chúng (chiều của cung

có thể tùy ý)

Hình 8.6 Đồ thị có hướng đầy đủ

7.2.3 Những đồ thị đơn đặc biệt

Bây giờ chúng ta sẽ xét một vài lớp đồ thị đơn thường gặp trong các ứng dụng

Ví dụ 4 Đồ thị đầy đủ Đồ thị đầy đủ n đỉnh, ký hiệu là Kn là một đơn đồ thị chứa đúng một cạnh nối mỗi cặp đỉnh phân biệt



Hình 7.7 Đơn đồ thị vô hướng đầy đủ

Ví dụ 5 Chu trình (vòng) Chu trình , ký hiệu là Cn , n 3, là một đơn đồ thị có n đỉnh

v1,v2, , vn và các cạnh là {v1,v2}, {v2,v3}, , {vn-1,vn},{vn,v1}

Định nghĩa 5 Một đồ thị đơn G đƣợc gọi là đồ thị phân đôi nếu tập các đỉnh V có thể phân

làm hai tập con không rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh của V1 với một đỉnh của V2

Hình 7.11 Đồ thị phân đôi

Định nghĩa 6 Một đồ thị đơn Km,n đƣợc gọi là đồ thị phân đôi đầy đủ nếu tập các đỉnh V

có thể phân làm hai tập con không rỗng, rời nhau V1 có m đỉnh và V2 có n đỉnh sao cho

có một cạnh giữa 2 đỉnh nếu và chỉ nếu một đỉnh thuộc V1 và đỉnh thứ hai thuộc V2

Ví dụ 11 Các đồ thị sau là các đồ thị phân đôi đầy đủ

9

Hình 7.12 Đồ thị phân đôi đầy đủ

7.2.5 Một vài ứng dụng của các đồ thị đặc biệt

Bây giờ chúng ta sẽ chỉ ra cách dùng các loại đồ thị đặc biệt trong các mô hình truyền dữ liệu

Cuối cùng, một số mạng cục bộ dùng cấu trúc hỗn hợp của hai cấu trúc trên Các thông báo đƣợc truyền vòng quanh theo vòng tròn hoặc có thể qua thiết bị trung tâm Sự dƣ thừa này có thể làm cho mạng đáng tin cậy hơn.Mạng cục bộ với sự dƣ thừa này có thể mô hình hóa bằng

Cho tới gần đây, các máy tính chỉ thực hiện được các chương trình có một phép toán tại một thời điểm Do đó các thuật toán để giải các bài toán được thiết kế để thực hiện một bước tại

mỗi thời điểm Đó là cá thuật toán nối tiếp (Phần lớn các thuật toán mô tả ở đây là các thuật

toán nối tiếp) Tuy nhiên, nhiều bài toán với số lượng tính toán rất lớn như bài toán mô phỏng thời tiết, tạo hình trong y học, hay phân tích mật mã, không thể giải được trong một khoảng thời gian hợp lý nếu dùng thuật toán nối tiếp ngay cả khi dùng các siêu máy tính Ngoài ra, do những giới hạn về mặt vật lý đối với tốc độ thực hiện các phép toán cơ sở, nên thường gặp các bài toán không thể giải trong trong khoảng thời gian hợp lý bằng các thuật toán nối tiếp Khi

xử lý song song, người ta dùng các máy tính có nhiều bộ xử lý riêng biệt, mỗi bộ xử lý có bộ

nhớ riêng, nhờ đó có thể khắc phục được những hạn chế của các máy nối tiếp Các thuật toán song song phân chia bài toán chính thành một số bài toán con sao cho có thể giải đồng thời được Do vậy bằng các thuật toán song song và nhờ việc sử dụng các máy tính có bộ đa xử lý người ta hy vọng có thể giải nhanh các bài toán phức tạp Trong thuật toán song song có một dãy các chỉ thị theo dõi việc thực hiện thuật toán, gửi các bài toán con tới các bộ xử lý khác nhau, chuyển các thông tin vào, thông tin ra tới các bộ xử lý thích hợp

Khi dùng xử lý song song, mỗi bộ xử lý có thể cần các thông tin ra của các bộ xử lý khác Do

đó chúng cần phải được kết nối với nhau Người ta có thể dùng loại đồ thị thích hợp để biểu diễn mạng kết nối các bộ xử lý trong một máy tính có nhiều bộ xử lý Bây giờ chúng ta sẽ mô

tả các kiểu mạng kết nối thường dùng nhất cho các máy xử lý song song Kiểu mạng kết nối thường dùng để thực hiện một thuật toán song song cụ thể phụ thuộc vào những yêu cầu đối với việc trao đổi dữ liệu giữa các bộ xử lý, phụ thuộc vào tốc độ mong muốn, và tất nhiên vào phần cứng hiện có

Mạng kết nối các bộ xử lý đơn giản nhất và cũng đắt nhất có các liên kết hai chiều giữa mỗi cặp bộ xử lý Các mạng này có thể mô hình bằng Kn, đồ thị đầy đủ n đỉnh, trong đó n là

số bộ xử lý Tuy nhiên, với các mạng liên kết này cũng có những vấn đề hết sức nghiêm túc đặt ra, chẳng hạn, số kết nối quá nhiều Thực ra, số các kết nối cần phải có giới hạn Khi có nhiều bộ xử lý thì mỗi bộ không thể nối trực tiếp với tất cả các bộ xử lý khác Ví dụ nếu ta có

64 bộ xử lý thì có C(64,2) = 2016 kết nối, mỗi bộ xử lý nối trực tiếp với 63 bộ xử lý khác Mặt khác, hình như cách đơn giản nhất để kết nối n bộ xử lý với nhau là sắp xếp chúng như

một bảng một chiều hay mảng một chiều

Mỗi bộ xử lý Pi, khác với

P1 và Pn được nối với các bộ xử lý cạnh nó là Pi-1 và Pi+1 bằng các đường hai chiều P1 được nối với P2 và Pn được nối với Pn-1 Nhược điểm của phương pháp kết nối này là nhiều khi cần có rất nhiều các kết nối trung gian để các bộ xử lý trao đổi thông tin với nhau

11

Mạng kiểu lưới hay mảng hai chiều rất hay được dùng cho các mạng liên kết Trong một

mạng như thế, số các bộ xử lý là một số chính phương, n = m2

Mạng kiểu lưới cũng có một số hạn chế

số liên kết cho mỗi bộ xử lý Sự truyền

thông giữa một số cặp bộ xử lý đòi hỏi

O( n) = O(m) các kết nối trung gian

Có lẽ mạng kết nối quan trọng nhất là

mạng kiểu siêu khối Hình 8.14 Mạng kiểu lưới (hai chiều) Với các mạng loại này số các bộ xử lý là lũy thừa của 2, n = 2m

Mỗi bộ xử lý có liên kết 2 chiều với m bộ xử lý khác Bộ xử lý Pi nối với bộ xử lý có chỉ số biểu diễn bằng dãy nhị phân khác với dãy nhị phân biểu diễn i tại đúng một bit Mạng kiểu siêu khối cân bằng số các kết nối trực tiếp của mỗi bộ xử lý và số các kết nối gián tiếp sao cho các bộ xử lý có thể truyền thông được Nhiều máy tính đã chế tạo theo mạng kiểu siêu khối và nhiều thuật toán đã được thiết kế để sử dụng mạng kiểu siêu khối Đồ thị Qn chính là biểu diễn của mạng loại này

Đôi khi hai đồ thị có dạng đúng như nhau, theo nghĩa là có một phép tương ứng 1-1 giữa các

đỉnh của chúng mà vẫn bảo tồn các cạnh Trong trường hợp đó ta nói rằng hai đồ thị là đẳng

cấu Việc xác định xem hai đồ thị có là đẳng cấu không là một bài toán quan trọng của lý

thuyết đồ thị

7.3.2 Biểu diễn đồ thị bằng danh sách liền kề

Một cách biểu diễn đồ thị không có cạnh bội là liệt kê tất cả các cạnh của đồ thị Nói cách

khác để biểu diễn đồ thị không có cạnh bội ta dùng danh sách liền kề Danh sách này chỉ rõ

các đỉnh nối với mỗi đỉnh của đồ thị

Giả sử G = (V,E) là một đồ thị đơn trong đó |V|=n và các đỉnh được liệt kê một cách tùy ý

v1,v2, ,vn Ma trận liền kề A (hay AG) của G ứng với danh sách các đỉnh này là ma trận logic cấp nxn có phần tử ở hàng i cột j bằng 1 nếu vi và vj liền kề nhau (tức là có cạnh nối chúng) và bằng 0 nếu chúng không được nối với nhau Nói cách khác ma trận liền kề của

đò thị là ma trận A = [aij] trong đó

aij =

Lưu ý là ma trận liền kề của một đồ thị phụ thuộc vào thứ tự liệt kê các đỉnh Vì vậy có tới n!

ma trận liền kề khác nhau của một đồ thị n đỉnh vì có n! cách sắp xếp các đỉnh

Ma trận liền kề của một đồ thị đơn là đối xứng, tức là aij = aji Hơn thế nữa, vì đồ thị đơn không có khuyên nên aii = 0 với i =1,2,3, ,n

Ví dụ 3 Dùng ma trận liền kề biểu diễn đồ thị trên hình sau:

1

001

1

010

1

111

0

Ma trận kề cũng có thể dùng để biểu diễn đồ thị vô hướng có khuyên và có cạnh bội (đồ thị có khuyên được gọi là giả đồ thị, nhưng nhiều khi người ta cũng gọi một cách đơn giản là đồ thị) Khi có cạnh bội ma trận liền kề không còn là ma trận không-một nữa, vì phần tử ở vị trí (i,j)

của ma trận này bằng số cạnh bội nối đỉnh u i và đỉnh u j Khuyên tại đỉnh ui được coi là cạnh nối đỉnh ui với chính nó và được tính là một cạnh Tất cả các đồ thị vô hướng, kể cả đa

đồ thị và giả đồ thị đều có ma trận liền kề đối xứng

1 nếu {vi,vj} là một cạnh của G

0 nếu không có cạnh nối đỉnh vi với đỉnh vj

u1

u4 u3

u2

2

21

1

0

11

0

3

20

3

0

Ma trận liền kề của đồ thị có hướng:

Ma trận liền kề của đồ thị có hướng không có tính đối xứng

Cũng có thể dùng ma trận kề biểu diễn đa đồ thị có hướng Ma trận khi đó không phải là ma trận không-một khi có cạnh bội cùng hướng nối hai đỉnh Trong ma trận liền kề của đa đồ thị

có hướng, a ij bằng số các cung đi từ đỉnh v i đến đỉnh v j

Ma trận trọng số

Trong rất nhiều ứng dụng khác nhau của lý thuyết đồ thị, mỗi cạnh e =(u,v) của nó được gán bởi một số c(e) = c(u,v) gọi là trọng số của cạnh e Đồ thị trong trường hợp như vậy gọi là

đồ thị trọng số Trong trường hợp đó, ma trận kề của đồ thị được thay bởi ma trận trọng số c=

c[i,j], i, j= 1, 2, , n c[i,j] = c(i,j) nếu (i, j) E, c[i,j] =  nếu (i, j) E Trong đó,  nhận

các giá trị: 0, , - tuỳ theo từng tình huống cụ thể của thuật toán

7.3.4 Ma trận liên thuộc

Các ma trận liên thuộc cũng có thể được dùng để biễu diễn các cạnh bội và khuyên Các cạnh bội được biểu diễn trong ma trận liên thuộc bằng cách dùng các cột có các phần tử giống hệt nhau vì các cạnh này được nối với cùng một cặp các đỉnh

G = (V,E) V = {v1, v2, , vn} E = {e1, e2, , em}

Ma trận liên thuộc của đồ thị G là M = [mij]

trong đó mij =1 nếu cạnh ej liên thuộc với đỉnh vi và = 0 nếu cạnh ej không liên thuộc với đỉnh vi

Định nghĩa 1 Các đồ thị đơn G1 =(V1,E1) và G2 =(V2,E2) là đẳng cấu nếu có hàm song ánh

f từ V1 lên V2 sao cho các đỉnh a và b là liền kề trong G1 nếu và chỉ nếu f(a) và f(b)

là liền kề trong G2 với mọi a và b trong V1 Hàm f như thế được gọi là một đẳng cấu

Nói cách khác khi hai đơn đồ thị là đẳng cấu, sẽ tồn tại một phép tương ứng một-một giữa các đỉnh của đồ thị bảo toàn quan hệ liền kề

Ví dụ 8 Hãy chỉ ra rằng các đồ thị G = (V,E) và H = (W,F) trên hình 8 là đẳng cấu

G

H Giải Đặt f với f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2 Ta thấy f là phép tương ứng một

- một hay là một song ánh từ G đến H Hơn nữa ta có thể thấy rằng phép tương ứng này bảo toàn quan hệ liền kề

Thông thường việc xác định xem hai đồ thị có là đẳng cấu hay không là rất khó khăn Có tới n! phép tương ứng một-một giữa hai đồ thị có n đỉnh Thử mỗi phép tương ứng xem nó có bảo toàn tính liền kề hay không là không thực tế, nhất là khi n đủ lớn

Tuy nhiên thường người ta chứng tỏ hai đơn dồ thị là không đẳng cấu bằng cách chỉ ra chúng không có chung một tính chất mà các đơn đồ thị đẳng cấu cần phải có Tính chất như thế gọi

là một bất biến đối với phép đẳng cấu của các đơn đồ thị Chẳng hạn, các đơn đồ thị có cùng

15

Đường đi độ dài n từ u tới v, với n là một số nguyên dương, trong một đồ thị vô hướng là một dãy các cạnh e1,e2, ,en của đồ thị sao cho f(e1) = {x0,x1}, f(e2) = {x1,x2}, , f(en)= {xn-

1,xn}, với x0 = u và xn = v Khi đồ thị là đơn ta ký hiệu đường đi này bằng dãy các đỉnh x0,

x1, , xn (vì danh sách các đỉnh này xác định duy nhất đường đi) Đườ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, tức là u = v Đường đi hoặc chu trình khi

đó gọi là đi qua các đỉnh x1,x2, ,xn-1 Đường đi hoặc chu trình được gọi là đơn nếu nó không

chứa một cạnh quá một lần

Một đường đi được gọi là đường đi sơ cấp nếu nó đi qua các đỉnh đúng một lần, trừ đỉnh đầu và đỉnh cuối Đường đi sơ cấp có đỉnh đầu và đỉnh cuối trùng nhau được gọi là chu trình

sơ cấp

Khi không cần phân biệt các cạnh bội ta sẽ ký hiệu đường đi e1,e2, ,en trong đó f(ei) = {x

i-1,xi} với i = 1,2, ,n bằng dãy các đỉnh x0, x1, ,en Ký hiệu này xác định đường đi theo các đỉnh mà nó đi qua

Ví dụ 1

Trong đồ thị đơn trên hình bên a,d,c,f,e

là đường đi đơn độ dài 4 vì {a,d}, {d,c},

{c,f} và {f,e} đều là các cạnh Tuy vậy

d, e, c, a không là đường đi vì {e,c} không

là cạnh của đồ thị Còn b,c,f,e,b là một chu

trình độ dài 4 vì {b,c}, {c,f}, {f,e} và {e,b} là các cạnh và đường đi này bắt đầu và kết thúc tại b Đường đi a,b,e,d,a,b độ dài 5 không là đường đi đơn vì nó chứa cạnh {a,b} hai lần

Đường đi và chu trình trong đồ thị có hướng cũng đã được đưa vào từ chương 6 Bây giờ ta định nghĩa đường đi như vậy cho đồ thị có hướng

đường đi) Đườ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, tức

là u = v Đường đi hoặc chu trình khi đó gọi là đi qua các đỉnh x1,x2, ,xn-1

Đường đi hoặc chu trình được gọi là đơn

nếu nó không chứa một cạnh quá một lần

(nhưng có thể chứa một đỉnh quá một lần

thí dụ: a,b,c,d,b,e,a là một chu trình đơn, mặc dầu chứa đỉnh b 2 lần Tương tự

a,b,c,d,b,e là một đường đi đơn)

Khi không cần phân biệt các cạnh bội ta sẽ ký hiệu đường đi e1,e2, ,en trong đó f(ei) = {x

i-1,xi} với i = 1,2, ,n bằng dãy các đỉnh x0, x1, ,xn Ký hiệu này xác định đường đi theo các đỉnh mà nó đi qua

7.4.3 Tính liên thông trong đồ thị vô hướng

Khi nào một cặp máy tính trong một mạng máy tính có thể trao đổi thông tin với nhau, nếu các thông tin có thể gửi qua một hay nhiều máy trung gian? Nếu mạng máy tính được biểu diễn bằng một đồ thị trong đó mỗi máy được biểu thị bằng một đỉnh còn mỗi đường truyền thông được biểu diễn bằng một cạnh, thì câu hỏi trên có dạng: có phải luôn tồn tại một đường

đi giữa hai đỉnh trong một đồ thị không?

Định nghĩa 3

Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa hai điểm bất kỳ của đồ thị

Như vậy, hai máy tính bất kỳ trong mạng có thể truyền thông được với nhau nếu và chỉ nếu

đồ thị của mạng này là liên thông

Ví dụ 2 Đồ thị G trên hình bên là liên thông

Còn đồ thị H thì không

Định lý 1 Giữa mọi cặp đỉnh phân biệt của

một đồ thị vô hướng liên thông luôn luôn có

Chứng minh

Giả sử có một đường đi giữa hai đỉnh phân biệt u, v của đồ thị liên thông G Vì G liên thông nên có một đường đi giữa u và v Gọi x0,x1, ,xn với x0 = u , xn = v, và là đường đi ngắn nhất giữa u và v Ta sẽ chứng minh đây là đường đi đơn Thật vậy, giả sử đường đi này không phải là đường đi đơn, khi đó có một đỉnh xi lặp lại, tức là tồn tại 0 i < j  n sao cho xi = xj

(Chú ý: trong đường đi đơn vẫn có thể có đỉnh

được lặp lại Ví dụ như đường đi a,b,c,d,b,e

là đường đi đơn Tuy nhiên đường đi không đơn

là điều kiện đủ để có đỉnh lặp lại, vì nếu có cạnh lặp lại thì có đỉnh lặp lại nhưng ngược lại thì chưa chắc)

Điều này có nghĩa là giữa u và v có

đường đi ngắn hơn là x0,x1, ,xi-1 ,xj, ,xn,

mâu thuẫn với giả thiết của ta

Vậy đường đi ngắn nhất phải là đường đi đơn

Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp các đồ thị con này không có đỉnh chung Các đồ thị con liên thông rời nhau như vậy được gọi là các

thành phần liên thông của đồ thị đang xét

Ví dụ ở hình trên đây đồ thị H có hai thành phần liên thông

Đôi khi việc xóa đi một đỉnh và tất cả các cạnh liên thuộc với nó sẽ tạo ra một đồ thị con có

nhiều thành phần liên thông hơn đồ thị ban đầu Các đỉnh như thế được gọi là các đỉnh cắt hay các điểm khớp Việc xóa một đỉnh cắt khỏi đồ thị liên thông sẽ tạo ra một đồ thị con

không liên thông

17

Một cạnh mà khi bỏ nó đi sẽ được đồ thị con có nhiều thành phần liên thông hơn so với đồ thị

ban đầu thì cạnh đó được gọi là cạnh cắt hay cầu

Ví dụ 4 Tìm các đỉnh và cạnh cắt

trong đồ thị sau:

Giải Đỉnh cắt của G là b,c và e

Các cạnh cắt là {a,b} và {c,e}

7.4.4 Tính liên thông trong đồ thị có hướng

Có hai khái niệm về tính liên thông trong đồ thị có hướng tùy theo chúng ta có quan tâm đến hướng của chúng hay không

Định nghĩa 4 Đồ thị có hướng được gọi là liên thông mạnh nếu có đường đi từ a tới b và

từ b tới a với mọi đỉnh a và b bất kỳ của đồ thị

Định nghĩa 5 Đồ thị có hướng được gọi là liên thông yếu nếu có đường đi giữa hai đỉnh bất

kỳ của đồ thị vô hướng nền (Như vậy đồ thị liên thông mạnh thì cũng liên thông yếu)

Vậy đồ thị có hướng là liên thông yếu nếu và chỉ nếu luôn tồn tại đường đi giữa hai đỉnh nếu

ta không quan tâm đến hướng của các cạnh Chú ý rằng trong đồ thị liên thông yếu thì có thể không có đường đi giữa a và b và không có đường đi từ b đến a với 2 đỉnh a, b nào

Đồ thị liên thông không có bất kỳ chu trình nào được gọi là một cây, một nhóm cây trong

đó không có 2 cây nào được nối với nhau được gọi là một rừng Rừng bao trùm của một đồ

thị là rừng và là đồ thị con của đồ thị đó và chứa tất cả các nút của đồ thị; rừng gồm các cây

T1, T2, ,Tm trong đó cây Ti chứa tất cả các nút liên thông với nút gốc của nó trong đồ thị

Nếu rừng bao trùm chỉ gồm một cây thì cây đó được gọi là Cây bao trùm của đồ thị đó

Hình 7.15 Đồ thị và cây bao trùm

Như vậy nếu ta thêm một cạnh bất kỳ vào cây bao trùm thì sẽ có một chu trình vì đã sẵn có một đường đi nối 2 đỉnh của cạnh thêm vào Chúng ta có thể thấy rằng cây có V đỉnh thì có chính xác V-1 cạnh Nếu một đồ thị có V đỉnh mà có ít hơn V-1 cạnh thì không liên thông, nếu đồ thị có nhiều hơn V-1 cạnh thì phải có một chu trình Ký hiệu V là số đỉnh của đồ thị Nếu tất cả các cặp đỉnh đều có đường nối thì tổng số cạnh là V(V-1)/2 Ta gọi đồ thị như vậy

là đồ thị đầy đủ Đồ thị có số cạnh nhỏ hơn VlogV được gọi là đồ thị thưa Đồ thị mà hầu hết các đỉnh đều được nối với nhau được gọi là đồ thị dày

7.4.5 Đường đi và sự đẳng cấu

Có một số cách dùng đường đi và chu trình để xác định xem hai đồ thị có đẳng cấu hay không Chẳng hạn sự tồn tại chu trình đơn với độ dài đặc biệt là một bất biến rất có ích để chỉ

ra hai đồ thị là không đẳng cấu Thêm vào đó, đường đi có thể dùng để xây dựng các ánh xạ

có khả năng là các phép đẳng cấu

Một bất biến đẳng cấu rất có ích đối với các đơn đồ thị là sự tồn tại chu trình đơn với độ dài k

lớn hơn 2 Ví dụ 6 minh họa cách dùng bất biến này để chứng tỏ hai đồ thị là không đẳng

số cạnh, bậc của các đỉnh của hai

đồ thị là như nhau Tuy nhiên H có

trong khi đó tất cả các chu trình của G đều có độ dài 4

Vì sự tồn tại chu trình đơn độ dài 3 là một bất biến đối với phép đẳng cấu nên các đồ thị G

v5

v2 v1

7.4.6 Đếm đường đi giữa các đỉnh

Số đường đi giữa hai đỉnh của đồ thị có thể xác định được khi sử dụng ma trận kề

Định lý 2 Cho G là một đồ thị với ma trận liền kề A theo thứ tự các đỉnh v1,v2, ,vn (với các cạnh vô hướng hoặc có hướng hay là cạnh bội, hoặc có thể có khuyên) Số các đường đi khác nhau độ dài r từ vi đến vj trong đó r là một số nguyên dương, bằng giá trị của phần

tử (i,j) của ma trận Ar

Chứng minh Giả sử A là ma trận liền kề của đồ thị G với cách sắp xếp các đỉnh theo thứ

tự v1,v2, ,vn Theo định nghĩa thì phần tử aij tại vị trí (i,j) của ma trận A chính là số đường đi độ dài 1 từ đỉnh vi đến đỉnh vj

Vậy với r = 1 định lý đúng

Giả sử định lý đúng với r = k, tức là phần tử (i,j) của ma trận Ak

là số các đường đi khác nhau có độ dài k từ đỉnh vi đến đỉnh vj Vì Ak+1 = AkA nên phần tử (i,j) của Ak+1

Ví dụ 8 Có bao nhiêu đường đi độ dài 4 từ u1 tới u4 trong đồ thị đơn G trên hình sau:

0

100

1

100

1

011

0880

0880

8008

nên có đúng 8 đường đi độ dài 4 từ u1 đến u4 Kiểm tra trực

tiếp trên đồ thị ta được 8 đường đi độ dài 4 từ u1 đến u4 là:

u1

u2

ra phương pháp để "viếng thăm" tất cả các nút của đồ thị một cách có hệ thống Mục đích cuối cùng của chúng ta dĩ nhiên không chỉ là liệt kê tên hay nội dung của các đỉnh, vì nếu chỉ như vậy thì trong cách cài đặt chúng ta đã gán các chỉ số 1, ,n cho các đỉnh và như vậy ta chỉ cần lần lượt đi từ đỉnh 1 đến đỉnh n là thăm được hết tất cả các đỉnh Ta phải đi qua các đỉnh và các cạnh của đồ thị một cách có hệ thống để thực hiện một thuật toán nào đó, thí

dụ tìm các thành phần liên thông hay rừng bao trùm của đồ thị Có 2 phương pháp duyệt đồ thị là duyệt đồ thị theo độ sâu và theo bề rộng

a Duyệt đồ thị theo độ sâu (Depth - first traverse)

Tư tưởng của phương pháp này được thực hiện như sau:

Khi đang ở đỉnh v trước hết ta thăm đỉnh đó, sau đó thăm từng đỉnh kề theo độ sâu Nghĩa

là giả sử đỉnh A có các đỉnh kề là B,C, (tức là có cạnh nối giữa chúng với A), giả sử sau khi thăm A ta đi đến đỉnh B và thăm đỉnh B, nếu B có đỉnh kề thì ta tiếp tục đi sâu xuống thăm đỉnh kề nào đó của B và cứ như vậy, chỉ khi đã thăm hết các đỉnh kề của B theo độ sâu thì ta mới trở lại thăm nút C theo độ sâu Quá trình trên dừng lại khi ta không thể đến thăm một đỉnh kề nào nữa Bây giờ nếu còn đỉnh chưa được thăm thì ta chọn một đỉnh để thăm và tiếp tục quá trình trên

Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm

n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong

mảng chuaxet[] có giá trị FALSE Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng có giá trị TRUE Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE

Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với v mỗi đỉnh đúng

một lần Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:

21

{

for (i=1; i n ; i++)

chuaxet[i] := TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/

for (i=1; i n ; i++)

if (chuaxet[i] )

DFS( i);

}

Ví dụ 9 áp dụng thuật toán tìm kiếm theo chiều sâu với đồ thị trong hình sau:

Đỉnh bắt đầu duyệt Các đỉnh đã duyệt Các đỉnh chưa duyệt

Hãy mô tả thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 2, với lưu ý là khi

có nhiều đỉnh cùng khả năng lựa chọn thì ưu tiên chọn đỉnh có chỉ số nhỏ hơn

Lời giải

Ta sẽ dùng mảng CX[i], i=1,2,3,4,5 để đánh dấu tình trạng của đỉnh i, nếu đỉnh i chưa xét thì CX[i]=1, nếu xét rồi thì CX[i]=0, mảng P[i] để đánh dấu đỉnh đứng trước đỉnh

i trong quá trình duyệt

Bước 0 Bước khởi tạo Ban đầu ta đặt các phần tử của mảng CX[] đều bằng 1, còn các phần

tử của P[] đều bằng -1, tức là không có đỉnh nào đứng trước đỉnh i

CX = (1,1,1,1,1) , P = (-1,-1,-1,-1,-1) Ta dùng mảng KQ[] để lưu kết quả phép duyệt Ban đầu mảng KQ[] chưa có phần tử nào

Bước 4 Đỉnh 5 có các đỉnh kề là 1 và 2, nhưng cả hai đều đã duyệt ta quay về đỉnh đứng

trước nó, là đỉnh 1 Đỉnh 1 có các đỉnh kề là 2 và 5 đều đã duyệt, do đó ta lại phải

Bằng cách trên đây ta có thể lần lượt duyệt các thành phần liên thông của một đồ thị Ban đầu

ta chọn một đỉnh bất kỳ để duyệt (thông thường ta chọn đỉnh 1) Sau khi kết thúc duyệt theo

độ sâu từ đỉnh này ta nhận được thành phần liên thông thứ nhất của đồ thị Ta chọn tiếp một đỉnh chưa xét có chỉ số nhỏ nhất chưa duyệt và lại thực hiện duyệt theo chiều sâu xuất phát từ

23

đều được duyệt

b Duyệt đồ thị theo bề rộng (Breadth - first traverse)

Phương pháp này được thực hiện như sau:

Khi đang ở đỉnh A trước hết ta thăm đỉnh đó, sau đó ta tiếp tục thăm các đỉnh kề của A, thí dụ các đỉnh B, C, Khi đã thăm hết các đỉnh kề của đỉnh A thì ta quay lại thăm các đỉnh

kề của B, hết đỉnh kề của B ta thăm đến đỉnh kề của C và cứ như thế Như vậy đỉnh kề nào được thăm trước thì các đỉnh con của nó cũng được thăm trước Quá trình trên dừng lại khi ta không thể đến thăm một đỉnh kề nào nữa Bây giờ nếu còn đỉnh chưa được thăm thì ta chọn một đỉnh để thăm và tiếp tục quá trình trên Ta thấy cách duyệt đồ thị theo bề rộng giống với cách duyệt cây theo tầng

c So sánh hai phương pháp duyệt đồ thị

Ta lưu ý rằng cả hai cách duyệt cây nói trên đều không cho kết quả duy nhất, vì nó phụ thuộc vào việc chọn đỉnh xuất phát và thứ tự thăm các đỉnh kề của mỗi đỉnh

Cả 2 cách duyệt đều cho ta rừng bao trùm của đồ thị, trong đó mỗi cây của rừng là một thành phần liên thông Rừng bao trùm theo chiều sâu chứa các cây hẹp và cao, rừng bao trùm theo chiều rộng chứa các cây rộng và ngắn

Hình 7.16 Đồ thị và ma trận kề Với đồ thị ở hình 8.16 , phép duyệt theo chiều sâu cho ta thứ tự các nút là 1 - 2 - 4 - 3, còn theo chiều rộng ta có thứ tự các nút được duyệt là 1 - 2 - 3 - 4

Chúng ta có thể dùng đệ quy hoặc cấu trúc stack để duyệt đồ thị theo chiều sâu Còn với phương pháp duyệt theo bề rộng thì một cấu trúc hàng đợi sẽ thích hợp hơn

d Cài đặt các thuật toán duyệt đồ thị trên máy tính:

Dưới đây là văn bản chương trình.đã sử dụng thủ tục đệ qui để duyệt Trong đó các hàm :

void Init(int G[][MAX], int *n): dùng để đọc dữ liệu là từ tệp DFS.IN là biểu diễn của

đồ thị dưới dạng ma trận kề A là ma trận vuông lưu trữ biểu diễn của đồ thị

void DFS(int G[][MAX], int n, int v, int chuaxet[]): là thuật toán duyệt theo chiều sâu

1 0 1 1 0

2 1 0 0 1

3 1 0 0 0

4 0 1 0 0

với đồ thị G gồm n đỉnh và đỉnh bắt đầu duyệt là v

void Init(int G[][MAX], int *n){

printf("\n So dinh do thi:%d",*n);

printf("\n Ma tran ke cua do thi:");

} void DFS(int G[][MAX], int n, int v, int chuaxet[]){

int u;

printf("%3d",v);chuaxet[v]=FALSE;

for(u=1; u<=n; u++){

if(G[v][u]==1 && chuaxet[u])

DFS(G,n, u, chuaxet);

} }

void main(void){

Sau đây là đoạn chương trình sử dụng Stack để duyệt đồ thị theo chiều sâu:

void Dtraverse(kmatran a, kvecto &chuaxet, int k, int n)

{Stack<int> S(20);int i,h;

7.5 ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON

7.5.1 Đường đi và chu trình EULER

Thành phố Konigsberg thuộc Phổ (bây giờ gọi là Kaliningrad thuộc Cộng hòa Nga), được chia thành bốn vùng bằng các nhánh sông Pregel Các vùng này gồm hai vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa hai nhánh của sông Pregel Vào thế kỷ thứ 18 người ta

đã xây bẩy chiếc cầu nối các vùng này với nhau Hình 7.17 vẽ các vùng và các cầu qua sông

D

C

A

B

Hình 7.17 Đảo Kneiphof trên sông Pregel và 7 vhiếc cầu Vào chủ nhật, người dân ở đây thường đi bộ dọc theo các phố Họ tự hỏi không biết có thể xuất phát tại một điểm nào đó trong thành phố, đi qua tất cả các cầu, mỗi chiếc cầu không đi qua nhiều hơn một lần, rồi lại trở về điểm xuất phát được không

Nhà toán học Thụy sĩ, Leonard Euler,

đã giải bài toán này Lời giải của ông

công bố năm 1736, có thể là một ứng

dụng đầu tiên của lý thuyết đồ thị

Euler đã nghiên cứu bài toán này,

mô hình hóa nó bằng một đa đồ thị, bốn

vùng được biểu diễn bằng bốn đỉnh, các cầu là các cạnh, như ở hình trên

Bài toán tìm đường đi qua tất cả các cầu mỗi cầu đi qua không quá một lần có thể được phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong đa đồ thị chứa tất cả các cạnh?

a.Định nghĩa 1 Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler

Đường đi Euler trong G là đường đi đơn chứa mọi cạnh của G

Các ví dụ sau minh họa khái niệm chu trình và đường đi Euler

Ví dụ 1 Trong các đồ thị sau đây đồ thị nào có chu trình Euler? Nếu không thì liệu

nó có đường đi Euler không?

f 

Giải Đồ thị G1 có chu trình Euler, thí dụ a,e,c,d,e,b,a Cả hai đồ thị G2 và G3 đều không

có chu trình Euler Tuy nhiên G3 có đường đi Euler, cụ thể là a,c,d,e,b,d,a,b

Một vài ghi chú về đường đi và chu trình Euler:

 Chu trình Euler là một đường đi Euler nhưng ngược lại thì chưa chắc đã đúng (ví dụ trên

đồ thị G3 thì a,c,d,e,b,d,a,b là đường Euler, nhưng không phải là chu trình Euler)

27

 Chu trình Euler có thể đi qua một đỉnh hai lần (ví dụ chu trình a,e,c,d,e,b,a trên đồ thị

G1) và có thể không đi qua một số đỉnh nào đó nếu các đỉnh này là các đỉnh cô lập, tức là

các đỉnh có bậc bằng 0 (ví dụ đỉnh f trên đồ thị G1)

 Chu trình Euler chỉ liên quan đến các cạnh của đồ thị, vì vậy ta có thể thêm một số bất kỳ các đỉnh có bậc 0 (đỉnh cô lập) vào đồ thị G thì chu trình Euler của G vẫn không thay đổi

b Các điều kiện cần và đủ cho chu trình và đường đi Euler

Định lý sau đây cho ta điều kiện cần và đủ để một đa đồ thị có chu trình Euler:

Định lý 1 Một đa đồ thị không có điểm cô lập có chu trình Euler nếu và chỉ nếu đồ thị là

liên thông và mỗi đỉnh của nó đều có bậc chẵn

Chứng minh

Điều kiện cần: Điều kiện liên thông khá hiển nhiên Giả sử đồ thị liên thông G có chu trình

Euler Chúng ta sẽ chỉ ra là tất cả các đỉnh của nó có bậc chẵn Thật vậy giả sử chu trình Euler là a = x0, x1, , xn= a Khi xuất phát từ a, chu trình góp 1 vào bậc của a, sau đó trên đường đi chu trình khi tới một đỉnh thì góp thêm 1, và khi ra khỏi đỉnh lại góp thêm 1, nghĩa

là mỗi lần đi qua một đỉnh chu trình lại góp thêm 2 vào bậc của các đỉnh Khi trở về đỉnh a chu trình thêm 1 vào bậc của a Như vậy chu trình đã cộng vào bậc của mỗi đỉnh một số chẵn Vì chu trình đi qua tất cả các cạnh đúng một lần, do đó mỗi cạnh đã được tính thành 2 bậc (khuyên được tính là 2 bậc), góp vào các đỉnh nối chúng Nghĩa là bằng cách tính bậc của các đỉnh thông qua chu trình, ta đã tính hết bậc của các đỉnh và của đồ thị

Như vậy nếu đồ thị có chu trình Euler thì bậc của tất cả các đỉnh phải là số chẵn (như vậy giả thiết liên thông cho điều kiện cần là không cần thiết, vì ta có thể xem các đỉnh treo có bậc 0 cũng là các số chẵn)

{x1,x2}, ,{xn-1,xn} càng dài càng tốt, sao cho x0, x1, , xn lập thành một chu trình Ví dụ ở

đồ thi G trên đây ta chọn các cạnh {a,f}, {f,c}, {c,b}, {b,a}

Điều này luôn luôn làm được, vì bậc của mỗi đỉnh là một số chẵn Xuất phát từ đỉnh a, nếu trên đường chưa gặp đỉnh a mà là một đỉnh nào đó thì đường đi dùng một đường để vào,

và do bậc của đỉnh là chẵn nên còn một cạnh nữa để ra khỏi đỉnh này Vì chỉ có hữu hạn điểm nên nhiều nhất là nó đi qua n-1 đỉnh còn lại để trở về a Chu trình này có thể chứa tất cả các cạnh hoặc không

Nếu tất cả các cạnh đều đã được đi qua thì chu trình là chu trình Euler và thuật toán tìm chu trình Euler kết thúc

Nếu chu trình này chưa phải là chu trình Euler thì ta thực hiện bước tiếp theo như sau:

Giả sử đồ thị ban đầu là G = (V,E) Chu trình C1 cũng là một đồ thị và C1=(V1,E1) Ta xóa khỏi đồ thị những cạnh đã có trong chu trình C1 , tức là V1 Trong số các đỉnh thuộc E1 ta xóa những đỉnh không kề với số cạnh còn lại (V2 = V \ V1) Ví dụ như trường hợp trên đây thì sau khi xóa ta được đồ thị H Đồ thị H có đỉnh c thuộc tập E1, nhưng là đỉnh kề của các cạnh còn lại nên được giữ lại Vì G là liên thông nên đỉnh chung như thế này luôn luôn tồn tại

và có ít nhất là một Trong trường hợp tổng quát ta gọi một đỉnh chung là w Ta thấy rằng mỗi đỉnh của H có bậc chẵn, (vì tất cả các đỉnh của G có bậc chẵn, và với mỗi đỉnh ta xóa đi từng cặp liên thuộc với nó để tạo ra H) Lưu ý rằng H có thể là không liên thông? Bắt đầu

từ w ta xây dựng chu trình C2 bằng cách chọn càng nhiều cạnh càng tốt như đã làm với G Chẳng hạn ở hình trên là c,d,e,c Tiếp theo ta tạo một chu trình trong G bằng cách ghép C1

và C2 (điều này làm được vì w là đỉnh chung của hai chu trình) Thực hiện điều này trên đồ thị ở hình trên ta được chu trình a,f,c,d,e,c,b,a

Tiếo tục quá trình này cho tới khi tất cả các đỉnh được sử dụng (Quá trình này phải kết thúc vì chỉ có một số hữu hạn các cạnh trong đồ thị) Và như vậy ta đã xây dựng được chu trình Euler

và điều kiện đủ được chứng minh

Đối với đồ thị có hướng ta có định lý sau:

Định lý 1' Một đa đồ thị có hướng không có đỉnh cô lập tồn tại chu trình Euler nếu và chỉ

nếu đồ thị là liên thông yếu đồng thời bậc-vào và bậc-ra của mỗi đỉnh là bằng nhau

c.Thuật toán tìm chu trình Euler

Bài toán: Cho đồ thị G = (V,E) Hãy tìm chu trình Euler của đồ thị G nếu có

Thuật toán:

 Bước 1: Kiểm tra xem đồ thị có liên thông hay không Nếu G là liên thông thì chuyển sang bước 2, ngược lại thì thông báo là chúng ta chỉ xét đồ thị liên thông và dừng thuật toán (Vì có thể thấy rằng nếu đồ thị có một thành phần liên thông còn phần còn lại là các điểm cô lập thì vẫn có thể có chu trình Euler, vì chu trình Euler chỉ quan tâm đến việc đi qua các cạnh mà không quan tâm đến việc đi qua các đỉnh)

 Bước 2: Kiểm tra xem tất cả các đỉnh trong G đều có bậc chẵn không Nếu tất cả các đỉnh đều có bậc là chẵn thì chuyển sang bước tiếp theo Nếu không thì dừng lại và kết luận rằng đồ thị đã cho không có chu trình Euler

Bước 3: Xây dựng thuật toán tìm chu trình Euler đơn trong G sao cho tất cả các cạnh của G đều có chu trình đơn đi qua và chỉ đi qua một lần bằng cách sau:

1 Tạo mảng CT để ghi đường đi và một Stack để xếp các đỉnh sẽ xét Đầu tiên xếp một đỉnh u nào đó của đồ thị vào Stack, thí dụ đỉnh v1

2 Xét đỉnh v nằm trên cùng của Stack và thực hiện:

 Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào CT

29

 Nếu v là liên thông với đỉnh x thì đưa x vào ngăn xếp sau đó xóa cạnh (v,x);

3 Quay lại bước 2 cho tới khi ngăn xếp rỗng thì dừng Kết quả đường đi Euler được chứa trong CE theo thứ tự ngược lại

Trong các phần tiếp theo để đơn giản, ta giả thiết các đỉnh của đồ thị là các số nguyên và được đánh số từ 1 đến n (Với giả thiết đồ thị có n đỉnh)

Lưu ý rằng ma trận kề của một đa đồ thị vô hướng không nhất thiết là ma trận 0-1 Phần tử

aij của ma trận kề nhận giá trị là một số nguyên không âm bất kỳ m là số cạnh nối 2 đỉnh i

và j

Để xác định chu trình Euler của một đồ thị vô hướng, trước hết ta cần kiểm tra xem đồ thị có liên thông không, sau đó nếu đồ thị liên thông thì kiểm tra tiếp xem bậc của các đỉnh có chẵn không Nếu những điều kiện này thỏa mãn thì bắt đầu xây dựng chu trình Euler Ta cũng lưu

ý là trong khi xây dựng chu trình Euler, khi có nhiều đỉnh cùng khả năng lựa chọn thì ưu tiên chọn đỉnh có chỉ số nhỏ hơn

Quá trình xây dựng chu trình Euler được thực hiện như sau:

Khởi tạo một Stack S chứa các phần tử là các số nguyên Giả sử tác vụ đưa phần tử k vào Stack là S.push(k), lấy phần tử ở đỉnh ra là S.pop(), xem phần tử ở đỉnh Stack là S.viewtop(), hàm S.empty() cho giá trị true nếu Stack rỗng, cho giá trị false nếu Stack không rỗng

Bước 0: Khởi tạo một Stack S Ban đầu Stack rỗng, không có phần tử nào Khởi tạo một mảng CE để chứa các đỉnh tạo nên chu trình Euler

Bước 1: Chọn một đỉnh k bất kỳ để đưa vào Stack

Bước 2: Xem phần tử h ở đỉnh Stack

 Nếu đỉnh h có đỉnh kề (tức là trong các phần tử ahi , i=1,2, ,n có phần tử khác 0) thì chọn đỉnh kề có chỉ số nhỏ nhất để đưa vào Stack, ví dụ là đỉnh r, đồng thời giảm các giá trị ahr và arh xuống một giá trị Điều này có nghĩa là xóa bớt một cạnh trong số các cạnh nối đỉnh h và đỉnh r

 Nếu đỉnh h là cô lập, tức là ahi = 0 với  i  {1,2, ,n} thì đưa h vào mảng CE

Bước 3: Nếu Stack rỗng thì kết thúc thuật toán, nếu không thì quay lại bước 2

Ví dụ Cho đa đồ thị vô hướng G = (V,E) với V = {1,2,3,4} được biểu diễn bởi ma trận kề

4 0 1 1 0

Hãy xây dựng một chu trình Euler cho đồ thị này nếu có thể

Lời giải Tính liên thông và bậc các đỉnh đều chẵn dễ dàng kiểm tra được

Ta xây dựng chu trình Euler xuất phát từ đỉnh 1 như sau:

Từ ma trận kề ta thấy

a12 = a21 = 2, a23=a32=3, a24 = a42 = 1, a34=a43=1

Các phần tử khác của ma trận kề bằng 0, do đó trong các bước tiếp theo các phần tử này vẫn bằng 0 nên ta không xét đến Ta có thể hệ thống kết quả các bước trong bảng sau:

int GetMatran(kmatran a,int &n);

void PutMatran(kmatran a,int n, FILE* f);

void SetEqual(kmatran a, kmatran b, int n);

int LienThong(kmatran a, int n);

int BacChan(kmatran a,int n);

void CTEuler(kmatran a, int n, kvecto CT, int &nCT);

#include "STACK_H.CPP"

#include "ATRRLIB.CPP"

//====================================================

void main()

{// a la matran ke, d la ma tran danh sach ke,

// dnum[i] la so dinh ke cua dinh i

int LienThong(kmatran a,int n)

{Stack<int> S(20);int i,h;kvecto chuaxet;

void CTEuler(kmatran a, int n, kvecto CT, int &nCT)

{Stack<int> S(20);kmatran B;int i,j,h,t;

SetEqual(B,a,n);//Dat b=a de khoi phuc lai gia tri sau nay S.push(1);//Dua dinh bat ky vao Stack, o day ta chon dinh 1 nCT=0;//Ban dau chu trinh chua co phan tu nao

{S.push(i);a[h][i] ;a[i][h] ;}//Loai canh (i,h) khoi do thi

//====================================================

Định lý 2

Đa đồ thị liên thông có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu nó có đùng hai đỉnh bậc lẻ

Chứng minh Trước tiên, ta giả sử đồ thị đã cho có đường đi Euler từ a đến b nhưng không

có chu trình Euler Cạnh đầu tiên góp 1 vào deg(a) Sau đó mỗi lần đường đi trở lại và đi qua đỉnh a lại góp 2 đơn vị cho deg(a) Do vậy a là một đỉnh bậc lẻ Cạnh cuối cùng của đường đi góp 1 cho deg(b) và mỗi lần đi qua b nó cũng tăng thêm 2 cho deg(b) Vì thế bậc của b là lẻ Các đỉnh trung gian đều có bậc chẵn vì mỗi lần đường đi tới rồi lại rời nó nên tăng 2 đơn vị cho bậc của nó Vậy đồ thị đã cho có đúng 2 đỉnh bậc lẻ

Bây giờ ta giả sử ngược lại, đồ thị có đúng 2 đỉnh bậc lẻ, chẳng hạn a và b Ta xét đồ thị rộng hơn tạo nên bằng cách thêm một cạnh nối a với b vào đồ thị xuất phát Khi đó bậc của

đồ thị mới này đều là số chẵn Theo định lý 1, nó có chu trình Euler Xóa cạnh mới thêm vào

ta được đường đi Euler của đồ thị xuất phát

Đối với đồ thị có hướng ta có định lý sau:

Định lý 2' Một đa đồ thị có hướng không có đỉnh cô lập tồn tại đường đi Euler nhưng không

tồn tại chu trình Euler nếu và chỉ nếu đồ thị là liên thông yếu đồng thời có 2 đỉnh, một đỉnh có bậc-vào lớn hơn bậc-ra một đơn vị, đỉnh kia có bậc-ra lớn hơn bậc-vào một đơn vị, tất cả các đỉnh còn lại có bậc-vào bằng bậc-ra

Ví dụ 4 Đồ thị sau đây có đường đi Euler không?

Giải G có đúng 2 dỉnh bậc lẻ là b và d Do đó nó

đường đi Euler nhận b và d là các điểm đầu mút

Một trong các đường đi Euler là d, a, b, c, d, b

Như ta thấy, đa đồ thị biểu diễn các cầu ở Konigsberg có 4 đỉnh bậc lẻ Theo định lý 2 không có đường đi Euler trong đồ thị này Vì vậy không thể có hành trình như bài toán đặt

ra

7.5.2 Đường đi và chu trình Hamilton

Đường đi và chu trình Euler chỉ liên quan đến các cạnh của đồ thị Tuy nhiên câu hỏi tương tự

có thể đặt ra đối với các đỉnh Thí dụ trong một mạng lưới giao thông ta lại quan tâm đến việc xuất phát từ một thành phố, liệu ta có thể đến thăm tất cả các thành phố khác mỗi thành phố thăm đúng một lần và cuối cùng trở lại thành phố xuất phát?

35

Cho đồ thị G = (V,E) Đường đi R được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần Chu trình C được gọi là chu trình Hamilton nếu nó xuất phát từ một đỉnh v nào đó, đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần rồi trở lại điểm

v Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửa Hamilton Trong các ví dụ sau chúng ta sẽ thấy là đồ thị Hamilton là nửa Hamilton nhưng ngược lại không luôn luôn đúng

Những thuật ngữ này xuất phát từ trò chơi đố vui do William Rowan Hamilton, nhà toán học người Ailen, nghĩ ra năm 1857 Giả sử ta có một khối 12 mặt, mỗi mặt là một hình ngũ giác đều Mỗi đỉnh trong 20 đỉnh của khối này được đặt bằng tên của một thành phố Hãy tìm một đường xuất phát từ một thàh phố, đi dọc theo các cạnh của khối, ghe thăm mỗi một trong 19 thành phố còn lại đúng một lần, cuối cùng trở về thành phố ban đầu

Ví dụ 5 Đồ thị nào trong các đồ thị đơn trên hình sau có chu trình Hamilton? Nếu không, có

đường đi Hamilton không?

Giải G1 có chu trình Hamilton a, b, c, d, e, a Không có chu trình Hamilton trong G2 (vì

bất cứ chu trình nào chứa mọi đỉnh cũng phải chứa cạnh {a,b} hai lần) Nhưng G2 có đường đi Hamilton a, b, c, d G3 không có cả chu trình Hamilton lẫn đường đi Hamilton,

vì bất kỳ đường đi nào chứa mọi đỉnh cũng phải chứa một trong các cạnh {a,b}, {d,c} và {e,f} quá một lần

Ví dụ 6 Hãy chỉ ra rằng không một đồ thị nào trên hình sau có chu trình Hamilton

Giải Không có chu trình Hamilton trong đồ thị G vì G có đỉnh bậc 1, đó là đỉnh e

Trong đồ thị H bậc của các đỉnh a, b, d, và e đều bằng 2 nên mọi cạnh liên thuộc với các đỉnh này phải thuộc chu trình Hamilton nào đó Dễ thấy rằng không tồn tại chu trình Hamilton trong H vì nếu ngược lại thì chu trình đó phải chứa cả 4 cạnh liên thuộc với c, điều này không thể xẩy ra

Định lý 3 Giả sử G là một đơn đồ thị liên thông với n đỉnh trong đó n3 Khi đó G có chu trình Hamilton nếu bậc của mỗi đỉnh không nhỏ hơn n/2

Định lý 4 Giả sử G = (V,E) là đồ thị có hướng đầy đủ Khi đó trong đồ thị G tồn tại

đường Hamilton

Chứng minh Giả sử tập đỉnh của đồ thị G là v1, v2, , vn Giả sử  = x1,x2, ,xk là một đường đi sơ cấp trong G Để đơn giản ta chỉ viết các đỉnh mà không có các cạnh như định nghĩa Nếu đường đi này là đường đi Hamilton thì thuật toán kết thúc Còn nếu đây chưa phải là đường đi Hamilton thì ta sẽ bổ sung dần các đỉnh còn lại để được một đưòng đi Hamilton theo nguyên tắc sau đây:

Giả sử x V mà x không nằm trên đường sơ cấp  Các trường hợp sau đây có thể xẩy ra

do tính đầy đủ (có cung nối 2 đỉnh bất kỳ):

 Nếu có cung nối từ x đến x1 thì x được bổ sung vào đầu  và nó có dạng

x2 thì phải có cung từ x2 đến x Nếu có cung từ x đến x3 thì ta chèn x vào giữa x2 và

x3, Cứ như vậy, cùng lắm là đến bước thứ k-1 ta có cung từ xk-1 đến x Lúc này đã có cung từ x đến xk nên ta chèn x vào giữa xk-1 và xk

7.6 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT

7.6.1 Mở đầu

Nhiều bài toán có thể mô hình hóa 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ụ ta cần mô

hình một hệ thống đường hàng không Trong mô hình cơ sở trước đây, mỗi thành phố đượ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 thành phố thì ta cần gán cho mỗi cạnh của

đồ thị cơ sở một con số tương ứng với khoảng cách giữa hai thành phố tương ứng Nếu quan tâm đến thời gian của mỗi chuyến bay thì ta lại gán các thời lượng này cho mỗi cạnh của đồ thị cơ sở Nếu trong bài toán đang xét ta quan tâm đến tiền vé của mỗi chuyến bay thì ta lại gán giá vé như trọng số cho mỗi cạnh

Đồ thị có trọng số cũng có thể được dùng để lập mô hình các mạng máy tính Chi phí truyền thông (chẳng hạn tiền thuê bao đường điện thoại hàng tháng), thời gian đáp ứng của các máy tính qua các đường truyền thông này, hoặc là khoảng cách giữa các máy tính, tất cả đều có thể được nghiên cứu bằng cách dùng một đồ thị có trọng số

Trong các ứng dụng chúng ta gặp nhiều loại bài toán liên quan đến đồ thị có trọng số Chẳng

hạn xác định đường đi ngắn nhất nối giữa hai đỉnh trong mạng, trong đó ta coi độ dài của

đường đi trong đồ thị là tổng các trọng số ứng với các cạnh của đường đi này (Chú ý: trong

37

đồ thị không trọng số, đường đi được hiểu là số cạnh có trên đường đi Trong trường hợp này

ta cũng có thể xem trọng số của mỗi cạnh là 1, và việc tìm đường đi ngắn nhất tương đương với việc tìm đường đi có ít cạnh nhất Một cách tự nhiên, nếu 2 đỉnh không có đường đi thì ta nên gán cho khoảng cách giữa chúng là , có nghĩa là muôn trùng xa cách, chứ ta không thể gán cho khoảng cách giữa chúng là 0 được) Dĩ nhiên bài toán tìm đường đi ngắn nhất giữa hai đỉnh a và b chỉ có nghĩa khi thực sự có đường đi giữa a và b Vậy ở đây ta sẽ giả thiết

đồ thị đang khảo sát là đơn đồ thị liên thông

7.6.2 Thuật toán Dijkstra xác định các đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại

Có một số thuật toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị Có lẽ thuật toán

tự nhiên nhất là ta tính tất cả các con đường có thể có từ đỉnh u đến đỉnh v, sau đó ta chọn đường đi có độ dài bé nhất tuy nhiên khi số đỉnh lớn thì việc liệt kê tất cả các con đường là việc làm khó có thể thực hiện Có một số thuật toán khả thi hơn đã được đề xuất

Giả sử ta xét đồ thị vô hướng G = (V,E) , trong đó tập hợp các cạnh được cho bởi V = {v0,

v1, , vn} Ta ký hiệu trọng số của cạnh giữa hai đỉnh vi và vj là [vi,vj] hoặc wij, đây là khoảng cách trực tiếp giữa 2 đỉnh không thông qua đỉnh trung gian Rõ ràng đường đi trực tiếp từ một đỉnh đến chính nó phải được xem là bằng 0 vì nó đã ở chính nó và đường đi trực tiếp từ một đỉnh tới một đỉnh khác mà không có cạnh nối chúng không thể xem là một số hữu hạn, nghĩa là phải xem đường đi đó là vô cùng lớn Vậy ta đặt wii = 0 và wij = 

Có lẽ ý tưởng đầu tiên nảy sinh khi ta gặp bài toán tìm đường đi ngắn nhất giữa hai đỉnh là liệt kê tất cả các đường đi có thể có giữa hai đỉnh này và chọn trong đó đường đi có độ dài ngắn nhất Tuy nhiên ta sẽ gặp phải một số trở ngại khi có quá nhiều đỉnh trong đồ thị Thật vậy ta phải liệt kê tất cả các đường đi độ dài 1, tức là đường đi trực tiếp, độ dài 2, độ dài 3, ,độ dài n-1 (Giả thiết rằng đồ thị có n đỉnh) Số các đường đi cần xét có thể như sau:

Rõ ràng đây là bài toán có độ phức tạp n!, nói chung không thể giải được với n lớn

Có một số thuật toán khả thi hơn đã được đề xuất Chúng ta sẽ tìm hiểu ở đây thuật toán do Dijkstra, nhà toán học người Hà lan, đề xuất năm 1959 Phiên bản mà ta sẽ trình bày sẽ được giả thiết là đồ thị đơn có hướng, các trọng số dương

Giả sử ta xét đồ thị có hướng G = (V,E) , trong đó tập hợp các cạnh được cho bởi V = {v0,

v1, , vn} Ta ký hiệu trọng số của cung giữa hai đỉnh vi và vj là [vi,vj] hoặc wij, đây là khoảng cách trực tiếp giữa 2 đỉnh không thông qua đỉnh trung gian Rõ ràng đường đi trực tiếp từ một đỉnh đến chính nó phải được xem là bằng 0 vì nó đã ở chính nó và đường đi trực

tiếp từ một đỉnh tới một đỉnh khác mà không có cạnh nối chúng không thể xem là một số hữu hạn, nghĩa là phải xem đường đi đó là vô cùng lớn Vậy ta đặt wii = 0 và wij =  nếu không

có cạnh nối hai đỉnh vi và vj

Những ý tưởng dẫn đến thuật toán Dijkstra

Giả sử ta cần tìm đường đi ngắn nhất từ đỉnh a đến đỉnh b Thay vì tìm chỉ một khoảng cách bé nhất từ a đến b, ta tìm một số khoảng cách bé nhất từ a đến các đỉnh khác trong đó

có b Nghĩa là lời giải của ta rộng hơn nhiều so với mục tiêu đặt ra Điều này nhìn qua có vẻ như là sự lãng phí Nhưng trong thực tế, cách làm này vẫn còn hiệu quả hơn nhiều so với cách liệt kê tất cả các con đường từ a đến b

Ta ký hiệu (u,v) là đường đi ngắn nhất từ đỉnh u đến đỉnh v và D(u,v) là độ dài đường đi này Trong trường hợp đỉnh a cố định, ta ký hiệu đơn giản là (x) và D(x) để ký hiệu đường

đi ngắn nhất từ a đến x và độ dài của nó

Ta sẽ sắp xếp tập các đỉnh {v1,v2, ,vn} thành dãy x0, x1, , xn-1 thỏa mãn tính chất sau đây: D(x0)  D(x1)  D(xk)   D(xn-1) (8.1)

Ta sẽ xây dựng dần tập Sk  V trong đó

Sk = {x0, x1, , xk }

Như ta sẽ thấy, việc xác định đường đi ngắn nhất giữa đỉnh a và b là việc không thể thực hiện được ngay bằng một số phép toán đơn giản Tuy nhiên nếu chúng ta lần lượt xác định các xi để thỏa mãn (8.1) thì công việc lại dễ dàng hơn Lý do là vì tập Sk có thể được xác định không mấy khó khăn nếu dựa vào Sk-1 Mà S0 là tập xuất phát lại có thể xác định được ngay, đó chính là phần tử a

Rõ ràng trong tập V thì phần tử có khoảng cách ngắn nhất đến a là chính nó, khoảng cách này như ta đã giả thiết ở trên, là bằng 0 Vậy S0 = {a }

Sau đó tập S sẽ được bổ sung dần từng phần tử xi và sẽ dừng lại khi gặp phần tử b, tức là dừng lại ngay khi b được đưa vào tập hợp Sk

Như chúng ta sẽ thấy trong ví dụ sau, đường đi ngắn nhất từ a đến b nói chung không chứa tất cả các đỉnh x1, x2, ,xk = b mà chỉ và chỉ chứa các đỉnh thuộc tập hợp này Nếu một đường

đi là ngắn nhất thì mọi phần của nó cũng là ngắn nhất Điều này có nghĩa là nếu có 2 đỉnh u

và v nằm trên đường đi ngắn nhất từ a đến b và u đứng trước v thì phần đoạn đường

từ u đến v của đường đi ngắn nhất (a,b) là đường đi ngắn nhất từ u đến v Vì vậy nếu

cố định đỉnh xuất phát và dùng một P(x) để chỉ nút đứng trước đỉnh x trong đường đi ngắn nhất từ a đến x thì từ một đỉnh x bất kỳ ta có thể lần ngược lại để chỉ ra đường đi ngắn nhất

Phương pháp chúng ta sử dụng được gọi là phương pháp "tham lam" (greedy) Thay vì chỉ tìm đường đi ngắn nhất từ a đến b ta lại tìm đường đi ngắn nhất từ a đến tất cả các đỉnh có khoảng cách ngắn nhất đến a nhỏ hơn khoảng cách ngắn nhất từ a đến b

Trước hết chúng ta xét một ví dụ cụ thể để xem thuật toán Dijkstra được thực hiện như thế nào

39

Giả sử ta có đồ thị sau:

Giả sử ta cần tìm đường đi ngắn nhất từ đỉnh A đến đỉnh H

Tập S0 ban đầu chỉ gồm một đỉnh A Đỉnh x1 tiếp theo được chọn là đỉnh B, rồi đến đỉnh

C, đỉnh D, sau đó là đỉnh E, đỉnh F, G, H Vậy dãy các đỉnh được xác định là:

A,B,C,D,E,F,G,H

Như ta thấy, dãy các đỉnh này không nhất thiết tạo thành đường đi Nhưng đường đi ngắn nhất

từ A đến H phải có các đỉnh trong là các đỉnh thuộc tập Sk

Sau đây chúng ta sẽ khảo sát một số tính chất của các tập Sk và dựa vào các tính chất đó để đưa ra thuật toán xây dựng tập này

Bước 0: Như ta đã thấy, ban đầu ta có S0 = {a }

Bước 1: Tiếp theo ta sẽ chọn x1 sao cho khoảng cách ngắn nhất từ nó đến a là bé nhất so

với các đỉnh khác Ta thấy rằng đường đi ngắn nhất từ a đến x1 phải là đường đi trực tiếp Vì giả sử lại có một đỉnh trong u trên đường đi này, ví dụ đường đi là (a,u,x1) thì ta thấy rằng khoảng cách từ a đến u còn bé hơn là khoảng cách bé nhất từ a đến x1, nghĩa là x1 không phải là phần tử có khoảng cách đến a là bé nhất như đã giả thiết Vậy độ dài sử dụng để tìm x1 chính là khoảng cách trực tiếp

từ đỉnh a đến các đỉnh còn lại Đỉnh x1 được chọn nếu khoảng cách trực tiếp từ a đến nó là bé nhất Đặt S0 = {a}, D0(y) = w(a,y), ta thấy rằng D(a) = D0(a) = 0 Theo yêu cầu đặt ra thì x1 được chọn phải thỏa mãn:

D(x1) = min{D(y) | y V \ S0} (8.2)

Tuy nhiên như ta đã thấy, tiêu chuẩn (8.2) tương đương với tiêu chuẩn

D0(x1) = min{w(a,y) | y V \ S0}= min{D0(y) | y V \ S0} (8.3)

Sau bước này, đường đi ngắn nhất từ a đến x1 đã được xác định Đó là đường đi (a,x1) và khoảng cách ngắn nhất D(x1) cũng được xác định là D(x1) = w(a,x1) Để ghi lại đường đi ngắn nhất, ta dùng mảng P[i] để chỉ đỉnh đứng trước i trong đường đi ngắn nhất từ a đến đỉnh i Theo cảm giác, ta cần một mảng hai chiều để lưu lại đường đi cho mỗi đỉnh Tuy nhiên như ta sẽ thấy, do tính chất đặc biệt của đường đi ngắn nhất, ta chỉ cần dùng mảng một chiều Như vậy ta có P[x1] = a

Bước 2: Đặt S1 = {a,x1} Bây giờ ta sẽ xác định đỉnh x2 V\ S1 sao cho D(x2) là bé nhất

trong tập các đỉnh còn lại Nghĩa là

D(x2) = min{D(y) | y V \ S1} (8.4)

Có thể thấy rằng đường đi ngắn nhất từ đỉnh a đến x2 hoặc là trực tiếp, hoặc là chỉ qua x1 Thật vậy, giả sử đường đi ngắn nhất từ a đến x2 lại đi qua một đỉnh u nào đó , tức là a, ,u, ,x2 thì rõ ràng đường đi từ a đến u trên con đường này ngắn hơn đường từ a đến x2, nghĩa là đáng lẽ ra u phải được chọn chứ không phải là x2

Trong tập các đỉnh thuộc V\S1 ta định nghĩa độ dài đặc biệt từ a đến một đỉnh y là:

D1(y) = min(w(a,y), w(a,x1)+w(x1,y)) (8.5)

Với định nghĩa này, ta cần xác định x2 sao cho

D1(x2) = min{D1(y) | y V \ S1} (8.6)

Ta chứng minh rằng nếu x2 thỏa (8.6) thì cũng thỏa (8.4) và D(x2) = D1(x2) Thật vậy giả sử x2 thỏa (8.6) nhưng không thỏa (8.4) Khi đó tồn tại x  x2 và thỏa mãn (8.4) Như trên đã chỉ ra, đườngđi ngắn nhất từ a đến x không thể đi qua một đỉnh khác ngoài đỉnh x1, vì nếu đi qua một đỉnh u nào đó thì chính đỉnh u mới là được chọn Do đó đường đi ngắn nhất từ a đến x D(x) là giá trị nhỏ hơn trong hai giá trị w(a,y) và w(a,x1)+w(x1,y), tức là

D(x) = min(w(a,x), w(a,x1)+w(x1,x))

Nhưng theo (8.5) thì

D(x)  D1(x2)  D(x2)

Điều này mâu thuẫn với điều đã giả thiết

Bước 3: Đặt S2 = {a,x1,x2} Tiếp theo ta sẽ xác định đỉnh x3 sao cho D(x3) là bé nhất trong

tập các đỉnh còn lại Nghĩa là

D(x3) = min{D(y) | y V \ S2} (8.7)

Ta thấy rằng đường đi ngắn nhất từ a đến x3 không thể chứa đỉnh trung gian z V\S2, mà chỉ có thể chứa các đỉnh thuộc tập S2, vì nếu điều này xảy ra thì z được chọn đưa vào tập S2 (để tạo thành S3) chứ không phải là x3 Ta thấy rằng đường

đi ngắn nhất (x3) có thể chứa x2 hoặc không Nếu nó không chứa x2 thì đây chính là đường đi đặc biệt tại bước trước từ a đến x3, hay là D1(x3) Còn nếu nó đi qua x2 thì chính là đường đi đặc biệt từ a đến x2, rồi đi trực tiếp từ x2 đến x3(mặc dầu từ x2 đến x3 có thể có đường ngắn hơn đường trực tiếp, nhưng như ta thấy, đường đi này không có đỉnh trung gian ngoài S2 Vậy khoảng cách D(x3) là

D(x3) = min(D1(x3),D1(x2)+w(x2,x3))