Bài 11. Khái niệm đồ thị

TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

Sau bài học này em sẽ:

Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần.

Em hãy giải bài toán trên:

Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?

1. Khái niệm đồ thị

Hoạt động 1. Tìm hiểu khái niệm đồ thị

a) Khái niệm đồ thị

Đồ thị G = (V, E) là tập hợp hữu hạn các đỉnh V và tập hợp các cạnh E nối các đỉnh.

Có rất nhiều mô hình đồ thị trong thực tế (Hình 11.2).

a) Cấu trúc tinh thể liên kết ion của muối ăn

c) Mạng Internet kết nối máy tính toàn cầu

Đồ thị được mô tả bằng cách vẽ các nút để mô tả các đỉnh và các đường nối giữa các đỉnh để mô tả các cạnh của đồ thị. Ví dụ một số đồ thị như Hình 11.3.

Mô hình thành phố Königsberg được mô phỏng lại để dễ quan sát hơn, với các vùng đất được kí hiệu là A, B, C, D và các cây cầu đóng vai trò các cạnh nối. Những mô hình đồ thị được biểu diễn như vậy. Như vậy, bài toán 7 cây cầu có thể phát biểu lại như sau: Cho mô hình đồ thị như Hình 11.4b, tìm đường đi qua tất cả các cạnh, mỗi cạnh đi qua đúng một lần.

b) Đồ thị vô hướng và đồ thị có hướng

Đồ thị vô hướng có các cạnh nối không phân biệt hướng, có thể đi được hai chiều, các cạnh được biểu diễn bằng các đoạn thẳng (Hình 11.5a). Đồ thị có hướng có mũi tên chỉ hướng trên các cạnh, chỉ đi theo hướng có mũi tên.

c) Đơn đồ thị

Nếu đồ thị có cạnh e = (v, v), tức là xuất phát và kết thúc tại một đỉnh, thì được gọi là có khuyên (Hình 11.6a). Nếu giữa hai đỉnh u, v có nhiều hơn một cạnh nối thì được gọi là có cạnh song song (Hình 11.6b, c).

b) Cạnh song song. Hình 11.6. Khuyên và cạnh song song trong đồ thị

Đồ thị G = (V, E) được gọi là đơn đồ thị nếu đồ thị không có khuyên và không có cạnh song song. Với đơn đồ thị, giữa hai đỉnh bất kì của đồ thị có nhiều nhất một cạnh nối. Trong phạm vi cuốn sách này, chúng ta chỉ xét các đơn đồ thị.

Ví dụ đồ thị vô hướng (Hình 11.5a) được biểu diễn trong Python như sau:

Trong Python, chúng ta sẽ sử dụng kiểu dữ liệu list để mô tả V và E. Mỗi cạnh là một cặp hai chỉ số mô tả cặp đỉnh tương ứng. Nếu đồ thị vô hướng thì sử dụng tập hợp để mô tả cạnh. Nếu đồ thị có hướng thì dùng list hoặc tuple để mô tả cạnh có hướng giữa hai đỉnh.

Đồ thị G = (V, E) là tập hợp các đỉnh V nối với nhau, kí hiệu là G = (V, E). Có hai loại đồ thị là đồ thị vô hướng và đồ thị có hướng (các cạnh có hướng chỉ đi theo chiều mũi tên).

2. Một số khái niệm liên quan đến đồ thị

Hoạt động 2

Đọc, trao đổi và thảo luận các khái niệm, định nghĩa liên quan đến đồ thị, thực hiện các yêu cầu sau:

Cho đơn đồ thị G = (V, E), có thể vô hướng hoặc có hướng.

Nếu từ đỉnh u có cạnh nối đến đỉnh v thì chúng ta nói v là đỉnh kề của u. Nếu G là vô hướng thì nếu v là đỉnh kề của u thì u cũng là đỉnh kề của v. Nếu cạnh e từ u đến v thì chúng ta sẽ kí hiệu e: u → v hay v → u.

Bậc (degree) của đỉnh u, kí hiệu deg(u), là số lượng các đỉnh kề với u.

Nếu G là đồ thị có hướng chúng ta sẽ có các định nghĩa sau:

Bậc ra (out degree) của đỉnh u, kí hiệu deg+(u), là số lượng các đỉnh kề với u.

Bậc vào (in degree) của đỉnh u, kí hiệu deg-(u), là số các đỉnh có cạnh nối đến u.

Đường đi (path) từ đỉnh s đến đỉnh t là dãy các cạnh kề nhau nối từ đỉnh s đến đỉnh t và thoả mãn điều kiện: tồn tại dãy các đỉnh kề nhau và khác nhau từng đôi một V1, V2, ..., Vk sao cho ei là cạnh nối đỉnh Vi-1 đến Vi (i = 1, 2, ..., k), V0 = s, và Vk = t.

V1, V2, ..., Vk khác nhau từng đôi một, do đó các cạnh e1, e2, ..., ek cũng khác nhau từng đôi một. Trong trường hợp đỉnh V0 trùng với đỉnh Vk thì dãy các cạnh kề nhau e1, e2, ..., ek ở trên là chu trình (cycle).

Lưu ý: Ma trận kề được định nghĩa cho cả đồ thị vô hướng và có hướng. Nếu G là đồ thị vô hướng thì ma trận kề là đối xứng.

Danh sách kề (Adjacency List) của đồ thị G, kí hiệu là Adj, là tập hợp danh sách đỉnh kề của các đỉnh của G.

Với đồ thị vô hướng trong Hình 11.10a, ta có ma trận kề và danh sách kề như Hình 11.10b và Hình 11.10c.

Một số khái niệm, định nghĩa quan trọng liên quan đến đồ thị bao gồm: bậc của các đỉnh, đường đi từ một đỉnh đến đỉnh khác, ma trận kề và danh sách kề. Tất cả các khái niệm này được định nghĩa cho cả hai kiểu đồ thị vô hướng và có hướng.

3. Biểu diễn đồ thị

Hoạt động 3. Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính

Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.

Cho đồ thị G = (V, E). Ta cần biểu diễn dữ liệu đồ thị G trên máy tính như thế nào? Bộ dữ liệu của đồ thị được cho bởi dãy các đỉnh V và dãy các cạnh E. Các đỉnh của đồ thị được đánh số từ 0 đến n - 1, ta có dãy các đỉnh V như sau:

Mỗi cạnh là một cặp hai đỉnh hoặc hai chỉ số tương ứng của hai đỉnh. Nếu G là đồ thị vô hướng thì cạnh là hai chiều; nếu G là đồ thị có hướng thì mỗi cạnh là cặp có thứ tự các đỉnh hoặc chỉ số của các đỉnh. Khi đó ta có dãy các cạnh E như sau:

Ma trận kề A và danh sách kề Adj đã được định nghĩa trong mục 2.

Mỗi cạnh có dạng e = (Vi, Vj) hoặc e = (i, j).

Với đồ thị ở Hình 11.12a ta có n = 5 và V được xác định như sau:

Với hai đồ thị trong Hình 11.12, E được định nghĩa như sau:

Đỉnh	Danh sách kề
0	1 2 3
1	0 2 4
2
3
4	1 2

Đỉnh	Danh sách kề
0	3
1	0 2 4
2	0 4
3	0 2
4	<rỗng?

Có nhiều cách thể hiện dữ liệu Adj trên kiểu dữ liệu danh sách liên kết (Linked List). Theo cách này, Adj là dãy các phần tử, phần tử thứ i, Adj[i] là một Linked List các phần tử là đỉnh kề với đỉnh thứ i của đồ thị.

Cách thứ hai, sử dụng list trong Python: Theo cách này thì danh sách kề Adj của các đồ thị ở Hình 11.12 tương ứng như Hình 11.15.

a) b) Hình 11.15. Danh sách kề của các đồ thị ở Hình 11.12

Để biểu diễn dữ liệu đồ thị trong máy tính, người ta thường sử dụng Ma trận kề hoặc Danh sách kề. Ma trận kề là mảng hai chiều. Danh sách kề thường được biểu diễn bằng danh sách liên kết. Trong Python, ma trận kề và danh sách kề là các danh sách (kiểu list).

Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau:

LUYỆN TẬP

VẬN DỤNG