06 - Cây khung của đồ thị

Giới thiệu

Cây khung của một đồ thị vô hướng G(V, E) liên thông là một đồ thị con T(V', E') với V' = V và |E'| = |V-1|, E' ⊂ E. Hay nói cách khác, cây T là một đồ thị con vô hướng, liên thông và không có chu trình của G.

Đồ thị G và một số cây khung của nó

Nguồn ảnh: SGK chuyên Tin 1, Hồ Sỹ Đàm

Cây khung nhỏ nhất của đồ thị (Minimum Spanning Tree)

Khi một đồ thị vô hướng có trọng số, các cây khung của nó sẽ có trọng lượng, trọng lượng được định nghĩa là tổng trọng số của các cạnh trên cây. Bài toán chúng ta quan tâm ở đây là cây khung có trọng lượng nhỏ nhất.

Ví dụ đồ thị G ở trên có 3 cây khung, trong đó có hai cây khung có trọng lượng 20, đây cũng là trọng lượng nhỏ nhất, vì ta không thể tìm ra cây khung nào có trọng lượng nhỏ hơn 20 của G.

Một số tính chất của cây khung

Số đỉnh của cây khung và đồ thị là bằng nhau
Số cạnh của cây khung đúng bằng |V| - 1
Cây khung là liên thông
Cây khung không có chu trình
Có nhiều cây khung cho cùng một đồ thị
Trọng lượng của cây là tổng trọng số các cạnh trên cây
Cây khung nhỏ nhất là cây khung có trọng lượng nhỏ nhất trong số các cây khung
Có thể có nhiều hơn một cây khung nhỏ nhất của đồ thị.

Các ứng dụng của cây khung nhỏ nhất

Cây khung có nhiều ứng dụng trong khoa học máy tính cũng như trong thực tế như phân tích các quan hệ trong mạng xã hội, thiết kế mạng máy tính, xây dựng cây phát sinh gen để nghiên cứu quá trình tiến hóa, xác định vùng màu và sắc độ tương tự xong xử lý ảnh, ...

Do tính ứng dụng rộng rãi, có nhiều thuật toán xác định cây khung cũng như cây khung nhỏ nhất của đồ thị. Trong phạm vi chuyên mục này, chúng ta tìm hiểu hai thuật toán phổ biến: Krusal và Prime

Tài liệu tham khảo

Competitive Programming 3, 4, Steven Halim
Giude to Competitive Programming, Antti Laaksonen
SGK chuyên Tin 1, Hồ Sỹ Đàm
GeeksforGeeks
VNOI
CP-Algorithm
Wikipedia

Thuật toán Krusal

Thuật toán Krusal thực hiện theo ý tưởng tham lam qua các bước chính sau:

Bước 1. Sắp xếp các cạnh tăng dần theo trọng số

Bước 2. Chọn cạnh nhỏ nhất. Kiểm tra xem nó có tạo thành chu trình với cây đang có, nếu chưa thì đưa vào cây, ngược lại bỏ qua.

Bước 3. Lặp lại bước 2 cho đến khi đủ |V| - 1 cạnh trong cây.

Tại bước 2, chúng ta sẽ thấy rằng cần thực hiện việc kiểm tra xem cạnh này có tạo thành chu trình và việc thêm nó vào cây đang có vẫn có thể thực hiện được bằng thuật toán DFS thông thường. Tuy nhiên, để hiệu quả hơn về mặt thời gian chúng ta nên tìm hiểu qua cấu trúc Disjoin Set Union. Các bạn thể tham khảo tại CP-Algorithm.

Mã giả thuật toán có thể viết như sau:

algorithm Kruskal(G) is

F:= ∅

for each v in G.V do

MAKE-SET(v)

for each {u, v} in G.E ordered by weight({u, v}), increasing do

if FIND-SET(u) ≠ FIND-SET(v) then

F := F ∪ { {u, v} }

UNION(FIND-SET(u), FIND-SET(v))

return F

Nguồn: Wikipedia