Chương 1: Cơ sở lý thuyết và các vấn đề liên quan 1. Đồ thị Trước khi tìm hiểu về lý thuyết đồ thị, chúng ta cùng xét một ví dụ về một mạng xã hội nhỏ [7] sau: Hình 1.1: Mạng xã hội Mỗi ô màu xanh biểu diễn cho một người dùng trong mạng xã hội, giữa hai người có một đường liên kết với nhau có nghĩa là họ biết nhau. Ngược lại, nếu không có đường liên kết này thì họ không biết nhau. Mối liên hệ “biết nhau” trong đồ thị này là hai chiều.
Ví dụ: An biết Thanh thì Thanh sẽ biết An. Một mạng xã hội như thế này là ví dụ cơ bản về đồ thị. Tên người chính là các đỉnh, và mỗi đường liên kết giữa hai người chính là các cạnh. Chúng ta thường biểu diễn sự liên kết giữa hai đỉnh u và v bởi cặp (u, v).
Bởi vì quan hệ “biết nhau” ở đây là quan hệ hai chiều, nên đây là ví dụ của đồ thị vô hướng. Trong đồ thị vô hướng, cạnh (u, v) tương tự như cạnh (v, u). Trong đồ thị có hướng, quan hệ “biết nhau” không còn là hai chiều nữa, một người A biết người B nhưng chưa chắc người B đã biết người A. Trong đồ thị vô hướng, một cạnh nối giữa hai đỉnh thì cạnh này gọi là liên thuộc đến hai đỉnh đó.
Chúng ta gọi các đỉnh liên kết với nhau bằng một cạnh là các đỉnh liền kề hoặc hàng xóm của nhau. Số lượng cạnh liên thuộc của một đỉnh là bậc của đỉnh đó. Nhìn trên đồ thị, An và Sơn sẽ không biết nhau. Giả sử rằng Sơn muốn làm quen với An.
Có cách nào để Sơn làm quen với An không? Nhìn trên đồ thị ta thấy, Sơn biết Hạnh và Hạnh lại biết Linh, cuối cùng Linh biết An. Vậy Sơn có thể thông qua Hạnh và Linh để làm quen với An. Thực ra, đây là một đường đi trong đồ thị, đường đi đi từ điểm đầu Sơn đến điểm cuối An. Không có đường đi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 ngắn hơn giữa Sơn và An mà phải đi qua ít nhất hai người.
Đường đi giữa hai đỉnh như thế này được gọi là đường đi ngắn nhất. Chúng ta đánh dấu đường đi ngắn nhất này như Hình 1.2: Đường đi trong mạng xã hội Khi đường đi xuất phát từ một đỉnh và quay lại chính nó, chúng ta gọi đó là một chu trình. Mạng xã hội bao gồm rất nhiều chu trình. Ví dụ từ An, Bình tới Cường, Linh rồi cuối cùng quay lại An.
Thực ra, có chu trình ngắn hơn đó là từ An qua Bình tới Linh rồi quay lại An.3: Chu trình trong mạng xã hội Có những lúc, chúng ta thêm các trọng số vào các cạnh. Ví dụ, trong mạng xã hội, chúng ta có thể sử dụng một trọng số để xác định mức độ biết nhau giữa hai người. Một ví dụ cụ thể khác về đồ thị chính là bản đồ đường đi. Giả sử tất cả đều là đường hai chiều, thì bản đồ đường đi này cũng là một đồ thị vô hướng, với các thành phố (địa điểm) là đỉnh, các đường đi là cạnh, giá trị trọng số chính là số biểu diễn khoảng cách giữa các thành phố.4 mô tả khoảng cách giữa một số tỉnh thành phía Bắc nước Việt Nam.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4: Bản đồ khoảng cách một số tỉnh thành phía Bắc Cách thức đơn giản biểu diễn trọng số là ta viết thêm một số thực lên cạnh của đồ thị. Khi đó, đồ thị có các cạnh có trọng số như thế này được gọi là đồ thị có trọng số. Trong trường hợp bản đồ đường đi, nếu chúng ta muốn tìm đường đi ngắn nhất giữa các vị trí, chúng ta phải tìm kiếm đường đi qua các vị trí trung gian sao cho tổng trọng số là nhỏ nhất. Đây chính là bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
Ví dụ ở bản đồ Hình 1.4, đường đi ngắn nhất từ Hà Nội tới Hạ Long, sẽ qua Hải Dương, Hải Phòng. Tổng cộng đoạn đường đi này có chiều dài 163km. Mối quan hệ giữa hai đỉnh không phải lúc nào cũng là hai chiều. Lấy ví dụ, trong bản đồ đường đi, chúng ta có thể gặp đường đi một chiều.
Để biểu diễn sự có hướng này, các cạnh được thêm dấu mũi tên ở cuối và đồ thị này được gọi là đồ thị có hướng.5 mô tả một mạng xã hội có hướng. Mũi tên có hướng chỉ từ An sang Linh có nghĩa là An biết Linh, nhưng ngược lại Linh không biết An. Dễ nhận thấy, đồ thị ở Hình 1.5 không có chu trình, khi đó đồ thị được gọi là có hướng không chu trình.5: Mạng xã hội có hướng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Chúng ta có thể sử dụng các thuật ngữ khác trong đồ thị có hướng. Ví dụ, một cạnh có hướng sẽ ra ở một đỉnh và vào một đỉnh khác.
Nếu cạnh đó ra ở đỉnh u và vào một đỉnh v, sẽ được kí hiệu là (u, v), và thứ tự này sẽ cho ta biết hướng đi từ đỉnh nào đến nào. Tổng số cạnh ra của một đỉnh gọi là bậc ra, tổng số cạnh vào của một đỉnh gọi là bậc vào. Như chúng ta thấy, đồ thị có rất nhiều ứng dụng trong biểu diễn các sự vật, mối quan hệ giữa các sự vật đó trong thế giới thực. Phần tiếp theo, luận văn sẽ trình bày một số lý thuyết nền tảng về đồ thị.
Giới thiệu đồ thị Đồ thị (G), kí hiệu là G = (V, E) bao gồm một tập các đỉnh (V) và tập các cạnh (E). Trong đó mỗi cạnh E nối giữa hai đỉnh thuộc tập các đỉnh (V) và được kí hiệu là E = (u, v) (Đỉnh u nối đỉnh v). Ví dụ về đồ thị được đưa ra ở Hình 1.6: Đồ thị Đồ thị được phân loại dựa vào đặc điểm của các cạnh như sau: Đơn đồ thị vô hướng Đơn đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V được gọi là cạnh [1]. Đa đồ thị vô hướng Đa đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh [1]. Thực tế, mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó. Giả đồ thị vô hướng Giả đồ thị vô hướng G = (V, E) bao gồm V là một tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u, u) [1].
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Từ đó, với tính chất có hướng của đồ thị được định nghĩa như sau: Đơn đồ thị có hướng Đơn đồ thị có hướng G = (V, E) bao gồm V là một tập các đỉnh, và E là tập các cặp có thứ tự gồm hai phần tử của V được gọi là cung. Đa đồ thị có hướng Đa đồ thị có hướng G = (V, E) bao gồm V là tập đỉnh, E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V được gọi là các cung. Hai cung e1 và e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh. Một số thuật ngữ cơ bản Bậc của đỉnh Hai đỉnh u và v của đồ thị vô hướng G = (V, E) được gọi là kề nhau nếu (u, v) là cạnh thuộc đồ thị G.
Nếu e = (u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là đỉnh đầu mút của cạnh e. 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ó. Đỉnh v gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg(v) = 0. Ví dụ: đồ thị vô hướng G = (V, E) ở Hình 1.
+ Bậc của các đỉnh: deg(1)=3; deg(2)=4, deg(3)=2, deg(4)=2, deg(5)=1, deg(6)=0. + Đỉnh 5 là đỉnh treo. + Đỉnh 6 là đỉnh cô lập. Trong đồ thị có hướng, bậc của đỉnh v được chia ra thành bậc trong (Incoming Nodes) và bậc ngoài (Outgoing Nodes).
Bậc trong của đỉnh v là số lượng các cạnh được nối tới đỉnh v, kí hiệu là deg+(v). Bậc ngoài của đỉnh v là số lượng các cạnh được nối từ đỉnh v, kí hiệu là deg-(v). Đường đi và chu trình, đồ thị liên thông Trong đồ thị vô hướng, đườ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 x0, 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 dãy 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 [1]. 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à chúng ta phải chú ý đến hướng trên các cung [1]. Đồ 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ó. Biểu diễn đồ thị Trong phần này, luận văn sẽ giới thiệu bốn cấu trúc dữ liệu chính dùng để biểu diễn một đồ thị.
Trong mỗi cấu trúc, phần biểu diễn các đỉnh được giữ nguyên, tuy nhiên phần biểu diễn các cạnh lại hoàn toàn khác nhau.7 được sử dụng cho toàn bộ ví dụ trong mục 1.7: Đồ thị có hướng Danh sách cạnh (Edge list) Trong biểu diễn đồ thị theo danh sách các cạnh, tất cả các cạnh e thuộc E đều được lưu dưới dạng hai phần tử (vi, vj) trong danh sách lưu trữ.