edge-contraction

You are currently browsing articles tagged edge-contraction.

Đây là bài thứ 3 trong loạt bài về cây khung nhỏ nhất. Mình khuyến khích bạn đọc xem lại bài thuật toán Kruskal và thuật toán Prim Todo: link. Một số tính chất của cây khung mình không nhắc lại ở đây nữa.

Thuật toán Borůvka có lẽ là một trong số những thuật toán có "tuổi đời" khá lớn trong các thuật toán mà mình blog. Thuật toán được phát triển bởi [1] Otakar Borůvka năm 1926. Trọng tâm của thuật toán này là phép co cạnh (edge contraction), một trong ba phép phổ biến (xóa cạnh, xóa đỉnh và co cạnh) hay áp dụng trong lý thuyết đồ thị.

Phép co cạnh (edge contraction): Gọi $e = (u,v)$ là một cạnh của đồ thị $G(V,E)$. Đồ thị thu được bởi phép co cạnh $e$, kí hiệu là $G/e$, là đồ thị thu được sau khi: (i)gộp hai đỉnh $u,v$ thành một đỉnh mới $x$ (giữ nguyên các cạnh khác) và (ii) xóa cạnh lặp (loop) tạo thành sau phép gộp và (iii) giữ lại duy nhất một cạnh trong số các cạnh song song.

 

Hình dưới đây minh họa một phép co cạnh. Hình (3) là đồ thị thu được sau khi co cạnh màu đỏ trong hình (1)
contrection-example
Phép co một cạnh còn có thể được mở rộng ra một tập cạnh. Gọi $X = \{e_1,e_2,\ldots, e_k\}$ là một tập $k$ cạnh. Đồ thị $G$ thu được sau phép co tập cạnh $X$, kí hiệu là $G/X$, là đồ thị thu được sau $k$ lần liên tục co lần lượt các cạnh trong $X$ (thứ tự cạnh nào được co trước, co sau không quan trọng).

Hình dưới đây minh họa một phép co một tập cạnh. Hình (3) là đồ thị thu được sau khi co tập cạnh màu đỏ trong hình (1)
contract-edge-set
Phép co cạnh thì có liên quan gì đến cây khung? Thực ra hai thuật toán Kruskal và Prim mà chúng ta tìm hiểu ở hai bài trước đều có thể được nhìn dưới góc độ phép co cạnh. Lấy thuật toán Kruskal làm ví dụ. Thuật toán Kruskal ban đầu sắp xếp các cạnh theo thứ tự tăng dần của trọng số, sau đó xét từng cạnh theo thứ tự đã sắp xếp và thêm cạnh vào rừng (kết quả trung gian là một rừng (forest) chứ không phải cây) hiện tại. Nếu thêm cạnh đó vào mà không tạo ra chu trình của rừng hiện tại thì ta thêm. Nếu không, ta xét cạnh tiếp theo. Mình khuyến khích bạn đọc xem lại ví dụ trong bài trước todo: link. Nhìn dưới góc độ của phép co cạnh, ta sẽ thực hiện thuật toán Kruskal bằng một câu như sau:

Kruskal: Tìm cạnh có trọng số nhỏ nhất và co.

Ví dụ thực hiện ý tưởng trên cho đồ thị được minh họa trong hình dưới đây. Chú ý khi co cạnh với đồ thị có trọng số, ta sẽ giữ lại cạnh có trọng số nhỏ nhất trong số các cạnh song song. Thứ tự các cạnh được co màu đỏ cũng chính là thứ tự các cạnh được thêm vào cây khung trong thuật toán Kruskal.

kruskal-contraction-example

Thuật toán Borůvka có ý tưởng tương tự như trên. Để phát biểu thuật toán, ta sẽ cần thêm khái niệm cạnh an toàn (safe edge):

Cạnh an toàn (safe edge): Một cạnh được gọi là an toàn nếu nó là cạnh có trọng số nhỏ nhất trong số các cạnh của một trong hai đầu mút.

 
Chú ý cụm từ một trong hai đầu mút. Ví dụ cạnh màu đỏ trong (1) là cạnh an toàn ứng với đỉnh $d$ nhưng không phải là cạnh an toán ứng với đỉnh $c$. Các cạnh màu đỏ trong (2) là tập các cạnh an toàn.
safe-edge-example

Để việc mô tả thuật toán trở nên đơn giản, ta sẽ giả thiết:

Giả thiết: Không có hai cạnh nào của đồ thị đầu vào $G(V,E)$ có cùng trọng số.

 

Ta sẽ sử dụng giả thiết này để chứng minh tính đúng đắn của thuật toán Borůvka. Cuối bài ta sẽ thảo luận phương pháp để loại bỏ giả thiết này. Thuật toán Borůvka có thể được mô tả đơn giản bằng một câu sau:

Borůvka: Tìm, thêm vào cây khung và co tất cả các cạnh an toàn cho đến khi đồ thị chỉ còn một đỉnh.

Ví dụ với đồ thị hình dưới đây, thuật toán Borůvka chỉ cần 3 bước để tìm ra cây khung (là tập các cạnh màu đỏ bị co).

boruvka-ex

Giả mã:

Borůvka($G(V,E),w$)
    $T \leftarrow \emptyset$
    while $V \not = 1$
        $X \leftarrow$ set of safe edges
        $T \leftarrow T \cup X$
        $G \leftarrow G/X$
    return $T$

 

Thực thi giả mã trên khá phức tạp. Trước khi đi vào chi tiết, chúng ta thử phân tích tính đúng đắn và thời gian thực hiện của thuật toán.

Chứng minh tính đúng đắn: Ta sẽ chứng minh tập các cạnh trả về $T$ ở cuối thuật toán là cây khung nhỏ nhất. Dễ thấy $T$ phải là liên thông vì $G/T$ cuối cùng chỉ là một đỉnh.

Để chứng minh $T$ là một cây, ta sẽ chứng minh tập các cạnh an toàn $X$ mà ta đưa vào tập $T$ trong mỗi bước không chứa chu trình. Thật vậy, giả sử $ C = \{u_0,u_1,\ldots,u_k \}$ là một chu trình của $X$. Theo định nghĩa của cạnh an toàn, ta có $w(uu_1) $ < $\max(w(u_1u_2),w(u_0u_k))$. Không mất tính tổng quát, ta giả sử $w(u_0u_1) $ < $w(u_1u_2)$. Do $u_1u_2$ là cạnh an toàn và $w(u_0u_1) $ < $w(u_1u_2)$, ta suy ra $w(u_1u_2)$ < $w(u_2u_3)$. Lập luận tương tự, ta có:

$w(u_0u_1) $ < $w(u_1u_2)$ < $ \ldots $< $w(u_{k-1}u_k)$ < $w(u_ku_0)$ < $w(u_0u_1)$

Đó là điều không thể xảy ra. Như vậy $T$ phải là một cây.

Để chứng minh $T$ có trọng số nhỏ nhất, ta dựa vào nhận xét: cạnh $e = (u,v)$ là an toàn khi và chỉ khi nó là cạnh nhỏ nhất của ít nhất một trong 2 lát cắt $(\{u\}, V\setminus \{u\}), (\{v\}, V\setminus \{v\})$. Theo tính chất (số 6 tại bài trước) của cây khung nhỏ nhất, cạnh an toàn phải nằm trong cây khung nhỏ nhất. Do đó, tập cạnh an toàn mà ta thực hiện co tại mỗi bước phải nằm trong cây khung nhỏ nhất của đồ thị tại bước đó. Điều này đã đủ để kết luận tập cạnh an toàn sẽ nằm trong cây khung nhỏ nhất của $G$? Thực ra là chưa. Chúng ta cần thêm một tính chất nữa đó là: nếu $T$ là cây khung nhỏ nhất của $G$ thì $T/X$ là cây khung nhỏ nhất của $G/X$. Chứng minh tính chất này không khó và coi như bài tập cho bạn đọc.

Do đó, đầu ra $T$ là cây khung nhỏ nhất của đồ thị.


Lemma 1: Độ phức tạp của thuật toán Borůvka là $O(F(n,m) \log_2 n)$ trong đó $F(n,m)$ là thời gian thực thi một bước lặp của vòng lặp while.

 
Chứng minh: Mỗi lần ta co một tập cạnh $X$ trong mỗi bước lặp, số đỉnh của đồ thị giảm đi ít nhất một nửa. Số đỉnh giảm đúng một nửa khi và chỉ khi $X$ là một cặp ghép hoàn hảo (perfect matching). Do đó, sau $\lceil \log_2 n \rceil$ bước lặp, số đỉnh của đồ thị chỉ còn lại 1. Lúc này vòng lặp while kết thúc.


Nhiệm vụ còn lại của chúng ta là thực thi đoạn code trong vòng lặp while. Nếu chúng ta thực hiện được trong thời gian $O(m+n)$ thì, theo Lemma 1, chúng ta sẽ thu được thuật toán $O((m+n)\log_2(n))$.

Thực thi thuật toán Borůvka

Thực thi phép co cạnh

Trước hết chúng ta sẽ nghiên cứu xem làm thế nào để thực thi phép co cạnh. Có 2 cách thực thi thường được dùng:

  1. Thực thi tường minh (explicit contraction): Ta sẽ thực sự thực hiện phép co cạnh. Cụ thể, khi co cạnh $uv$, ta sẽ: (i) gộp danh sách kề của $v$ vào danh sách kề của $u$, (ii) xóa nút $v$ khỏi danh sách kề của $u$, và (iii) với mỗi đỉnh $w$ sao cho cả hai $u,v$ đều là hàng xóm của $w$, ta sẽ xóa cạnh $wv$ sau khi gộp $u,v$.
  2. Thực thi hàm ẩn (implicit contraction): Ta sẽ không thực sự thực hiện phép co cạnh, i.e, ta sẽ không thay đổi đồ thị đầu vào mà sử dụng cấu trúc tập hợp để biểu diễn đỉnh của đồ thị sau khi co. Cụ thể, khi co cạnh $uv$, ta sẽ tạo ra một tập hợp $S_{uv} = \{u,v\}$ để "đánh dấu" $u,v$ đã được co lại với nhau, và tập các định kề của $u,v$ ta sẽ coi như tập các đỉnh kề của $S_{uv}$. Như vậy, sau một loạt phép co cạnh, ta sẽ biểu diễn mỗi "đỉnh" của đồ thị mới bằng một tập hợp. Khi co một cạnh, ta sẽ "hợp" hai tập hợp lại với nhau. Khi duyệt cạnh $xy$, ta sẽ phải kiểm tra xem $x$ và $y$ có nằm trong cùng một tập hợp hay không, và nếu không thì hai "đỉnh" (lúc này là 2 tập hợp) chứa $x,y$ sẽ là hai đỉnh khác nhau trong đồ thị mới. Các thao tác này gợi lại cho chúng ta cấu trúc tập hợp rời nhau (disjoint set data structure), i.e, cấu trúc Union-Find. Trong thực tế người ta sử dụng Union-Find để thực thi co cạnh kiểu này (thuật toán Kruskal là một ví dụ).

Cách đầu tiên thì thường ít được dùng vì nó liên quan đến việc sửa đổi đồ thì và chúng ta cũng có thể "cảm nhận" thấy co cạnh theo cách đầu tiên "thực sự" phức tạp và có thể mất thời gian lên tới $O(n)$ cho mỗi thao tác co cạnh. Mặc dù ta có thể mở rộng cách đầu tiên ra để co một tập cạnh với thời gian $O(n+m)$, thực hiện co thực sự vẫn là một thao tác tốn kém. Lợi thế của cách thực thi này là kích thước của đồ thị thực sự giảm sau mỗi phép co. Điều này có ý nghĩa về mặt lý thuyết, như Eisner [3] đã chỉ ra (trang 19), độ phức tạp của thuật toán Borůvka với thực thi co cạnh thực sự là $O(m(1 + \log_2 \frac{n^2}{m}))$. Thuật toán này thực sự nhanh hơn các thực thi của Kruskal và Prim mà chúng ta đã tìm hiểu trong blog này.

Với cách thứ hai, co một cạnh tương ứng với gọi thao tác Union$(x,y)$ và thao tác kiểm tra xem $x,y$ có thuộc cùng một tập hay không tương ứng với Find$(x,y)$. Cấu trúc này có thể được thực thi kiểu danh sách hoặc bằng cây (các bạn xem lại bài cấu trúc Union-Find). Trong thuật toán Borůvka, chúng ta sẽ không thực sự thực hiện Union-Find giống như thuật toán Kruskal mà thực hiện sử dụng mảng nhãn (chi tiết xem tại dưới đây), vì cách thực thi này đơn giản hơn mà có cùng (thậm chí tốt hơn) thời gian tiệm cận. Một vấn đề nữa là ta không thực sự xóa cạnh/đỉnh khỏi đồ thị, do đó, sau khi co cạnh, kích thước của đồ thị không thay đổi. Ta cần phải chú ý điều này khi phân tích các thuật toán với phép co cạnh hàm ẩn.

Chi tiết thực thi

Ở đây ta có hai đồ thị: đồ thị gốc và đồ thị thu được sau khi đã co một (tập) cạnh. Ta sẽ gọi đỉnh và cạnh của đồ thị co (tại bước hiện tại của thuật toán) lần lượt là đỉnh cocạnh co. Đỉnh co thực chất là một tập hợp các đỉnh còn cạnh co thực chất là cạnh của đồ thị với trọng số nhỏ nhất trong số các cạnh song song giữa hai đỉnh co. Sự nhập nhằng giữa 2 đồ thị này có thể làm thuật toán hơi khó hiểu một chút và mình sẽ cố gắng viết rõ ràng nhất có thể. Mọi câu hỏi xin để lại ở phần comment.

Ta sẽ dùng một mảng nhãn $L[1,2,\ldots,n]$ để biểu diễn các đỉnh sau khi đã thực hiện co cạnh. Cụ thể, $L[v] = x$ nếu $v$ thuộc đỉnh co $x$ trong đồ thị co. Ban đầu, ta khởi tạo $L[v] = v$. Ta sẽ sử dụng thêm một biến $count$ để đếm số đỉnh trong đồ thị hiện tại sau khi đã co. Nhãn của các đỉnh sẽ có giá trị từ $1$ tới $count$. Ta sẽ không biểu diễn đồ thị co một cách trực tiếp, mà sẽ thao tác với nó thông qua nhãn của các đỉnh của đồ thị gốc. Ta sẽ lần lượt thực thi từng dọng trong vòng lặp while của thuật toán Borůvka ở trên.

Tìm cách cạnh an toàn

Để tìm các cạnh an toàn, ta sẽ duyệt qua tất cả các cạnh của đồ thị co bằng cách duyệt qua các cạnh của đồ thị gốc $G(V,E)$. Với mỗi đỉnh co $x$, ta sẽ lưu một số $d[x]$ và một cạnh (của đồ thị gốc) $M[x]$ trong đó, $d[x] = \alpha$ nếu cạnh co nhỏ nhất kề với $x$ mà ta phát hiện tại bước duyệt cạnh hiện tại có trọng số $\alpha$, và $M[x] = uv$ nếu $uv$ là cạnh của đồ thị gốc tương ứng với cạnh co nhỏ nhất kề với $x$ đó. Khi duyệt cạnh $uv$, ta sẽ:

  1. Kiểm tra $L[u]$ và $L[v]$. Nếu $L[u] = L[v]$, ta duyệt cạnh tiếp theo (vì $u,v$ thuộc cùng một đỉnh co). Nếu không, ta thực hiên bước 2
  2. Nếu $w(u,v)$ < $d[L[u]]$, ta cập nhật $d[L[u]] = w(u,v)$ và $M[L[u]] = uv$. Nếu $w(u,v)$ < $d[L[v]]$, ta cập nhật $d[L[v]] = w(u,v)$ và $M[L[uv]] = uv$. Sau đó, ta duyệt cạnh tiếp theo.

Mảng cạnh $M$ chính là các cạnh an toàn của đồ thị co. Chú ý là có thể $M[x] = M[y]$ với hai đỉnh co $x,y$ khác nhau. Do đó, trước khi trả lại M, ta sẽ xóa các cạnh trùng lặp.
Dễ thấy thao tác này có thể thực hiện trong thời gian $O(m+n)$. Giả mã:

FindSafeEdges($G(V,E),w, L[1,\ldots,n], count$)
    $d[1,\ldots, count] \leftarrow +\infty$
    $M[1,2,\ldots,count] \leftarrow \emptyset $
    for each $u \in V$
        for each neighbor $v$ of $u$
        if $L[u] \not= L[v]$
            if $w(u,v)$ < $d[L[u]]$
                $d[L[u]] \leftarrow w(uv)$
                $M[L[u]] \leftarrow uv$
    for $i \leftarrow 1$ to $count$         $\ll$ remove duplicates in $M \gg$
        $uv \leftarrow M[i]$
        if $M[L[u]] = M[L[v]]$
            $M[L[u]] \leftarrow \emptyset$
    return $M$

 
Code C:

#define INFTY 100000000
#define TRUE 1
#define FALSE 0

#define min(x,y) (((x) &lt; (y)) ? (x) : (y))
#define max(x,y) (((x) &lt; (y)) ? (y) : (x))

// we use linked lists to represent adjacency lists
// each arc u-&gt;v with weight w(u-&gt;v) is represented by a node with data field v and weight w in the adacency list of u
typedef struct vlist{
int v;		// the head of the directed edge
int w;		// the original weight of the directed edge
struct vlist *next;
}vlist;

vlist **G;	// G[i] is the adjacency list of vertex i
int n;		// the number of vertices of the graph
int m;		// the number of edges of the graph

typedef struct edge{
int u;
int v;
int w;		// the weight of an edge
} edge;

int *L;
int count;

edge *find_safe_edges(int count){
int d[count];
int i = 0;
for(; i &lt; count; i++)d[i] = INFTY;
edge *M  = (edge *)malloc(count*sizeof(edge));
int u, v;
for( u = 0; u &lt; n; u++){
vlist *runner = G[u];
while(runner != NULL){
v = runner-&gt;v;
if(L[u] != L[v]){
if(d[L[u]] &gt; runner-&gt;w){
d[L[u]] = runner-&gt;w;
M[L[u]] = new_edge(u,v,runner-&gt;w);
}
}
runner = runner-&gt;next;
}
}
for(i = 0; i &lt; count; i++){
u = M[i].u;
v = M[i].v;
if(is_edge_equal(M[L[u]], M[L[v]])){
M[L[u]].u = -1;
M[L[u]].v = -1;
M[L[u]].w = -1;// the empty edge
}
}
return M;

}
edge new_edge(int u, int v, int w){
edge e;
e.u = u;
e.v = v;
e.w = w;
return e;
}

// check whether two edges are the same
int is_edge_equal(edge a, edge b){
return ((min(a.u,a.v) == min(b.u, b.v))&amp;&amp;(max(a.u, a.v) == max(b.u, b.v)));
}

Đưa các cạnh an toàn vào rừng hiện tại

Ta sẽ biểu diễn rừng trung gian bằng danh sách kề. Do đó, để đưa mỗi cạnh vào rừng hiện tại, ta chỉ việc xét mỗi cạnh trong tập $M$ và cập nhật danh sách kề.

AddToForest($T,M[1,\ldots, count], count$)
    for $i \leftarrow 1 $ to $count$
        if $M[i] \not= \emptyset$
            $uv \leftarrow M[i]$
            add $u$ to the adjacency list of $v$ in $T$
            add $v$ to the adjacency list of $u$ in $T$
    return $T$

 

Code C:

vlist **T;	// the adjacency list representation of the minimum spanning tree
void add_to_forest(edge *X, int count){
int i;
int u,v,w;
for(i = 0; i &lt; count; i++){
if(X[i].u != -1){	// X[i] is non-empty
u = X[i].u;
v = X[i].v;
w = X[i].w;
// append v to the head of the adjacency list of u
vlist* vnodev = (vlist *)malloc(sizeof(vlist));
vnodev-&gt;v = v;
vnodev-&gt;w = w;
vnodev-&gt;next = T[u];
T[u] = vnodev;

// append u to the head of the adjacency list of v
vlist* vnodeu = (vlist *)malloc(sizeof(vlist));
vnodeu-&gt;v = u;
vnodeu-&gt;w = w;
vnodeu-&gt;next = T[v];
T[v] = vnodeu;
}
}
}

Co cạnh và cập nhật biến $count$

Co tập cạnh thực chất là cập nhật lại nhãn của các đỉnh. Để cập nhật lại nhãn ta duyệt $T$ (dùng BFS hay DFS) để gán cho đỉnh của mỗi thành phần liên thông của $T$ một nhãn. Cuối cùng ta cập nhật lại biến $count$, là số thành phần liên thông của $T$. Thao tác này có thể thực hiện trong thời gian $O(n)$.

EdgeContraction($G(V,E), T, L[1,\ldots], count$)
    $L[1,\ldots, count] \leftarrow 0$
    $\ell \leftarrow 1$
    for each $u \in V$
        if $L[u] = 0$
            DFSUpdate($T,u,\ell$)
            $\ell \leftarrow \ell + 1$
    $count \leftarrow \ell-1$

 

DFSUpdate($T,u,\ell$)
    for each neighbor $v$ of $u$ in $T$
        if $L[v] = 0$
            $L[v] \leftarrow \ell$
            DFSUpdate($T,v,\ell$)

 
Code C:

void edge_contraction(){
memset(L, -1, n*sizeof(int));
int ell = 0;
int u;
for( u = 0 ; u &lt; n; u++){
if(L[u] == -1){
dfs_update(u, ell);
ell++;
}
}
count  = ell;
}

void dfs_update(int u, int ell){
vlist *runner  = T[u];
int v;
while(runner != NULL){
v = runner-&gt;v;
if(L[v] == -1){
L[v] = ell;
dfs_update(v, ell);
}
runner = runner-&gt;next;
}
}

Thuật toán đây đủ

Như vậy ta đã thực thi được vòng lặp while một cách trọn vẹn. Việc còn lại là chúng ta ghép mọi thứ lại với nhau.

BorůvkaImplicitContraction($G(V,E),w$)
    $T \leftarrow \emptyset$
    $L[1,2,\ldots,n] \leftarrow \{1,2,\ldots,n\}$
    $count \leftarrow n$
    while $count \not = 1$
        $X \leftarrow$ FindSafeEdges ($G(V,E),w, L[1,\ldots,n], count$)
        AddToForest ($T, X ,count$)
        EdgeContraction ($G, T, L[1,\ldots,n],count$)
    return $T$

 

void Boruvka(){
T = (vlist **)malloc(n*sizeof(vlist*));
int i = 0;
for(; i &lt; n; i++)T[i] = NULL;
L = (int *) malloc(n*sizeof(int));
for(i = 0; i &lt; n; i++)L[i] = i;
count = n;
edge *X;
while(count != 1){
X = find_safe_edges(count);
add_to_forest(X, count);
edge_contraction();
//		printf("count = %d\n", count);
}
}

Dễ thấy, trong thực thi ở trên, mỗi thủ tục con mất thời gian $O(m + n)$. Ta có:

Theorem 1: Ta có thể thực thi thuật toán Borůvka trong thời gian $O((n + m)\log_2(n))$.

 

Remark 1: Trong thuật toán Borůvka là mỗi vòng lặp, ta có thể thực hiện co tập các cạnh an toàn cùng một lúc. Do đó, ta có thể dễ dàng song song hóa thuật toán Borůvka.

Remark 2: Nếu biểu diễn rừng trung gian $T$ bằng danh sách cạnh, bước thêm cạnh vào rừng đơn giản chỉ là thêm phần tử vào một danh sách. Tuy nhiên, khi đó ta không thể dùng BFS hay DFS để gán lại nhãn trong bước co tập cạnh (DFS và BFS với biểu diễn d.s cạnh mất thời gian bình phương). Mặc dù vậy, ta có cách khác để gán lại nhãn trong thời gian $O(m+n)$. Mình không trình bày phương pháp này ở đây vì nó chỉ là vấn đề kĩ thuật và có khi làm phức tạp thêm bài toán. Chi tiết cụ thể coi như bài tập cho bạn đọc.

Đồ thị có trọng số không duy nhất

Phần này ta sẽ thảo luận phương pháp để loại bỏ giả thiết trọng số duy nhất ở trên. Tại sao ta cần các cạnh có trọng số duy nhất? Xét đồ thị tam giác, với 3 cạnh bằng nhau dưới đây.
triangle-ex

Theo định nghĩa của cạnh an toàn, bất kì cạnh nào cũng có thể là cạnh an toàn tương ứng với các đỉnh đầu mút. Do đó, bước tìm cạnh an toàn có thể trả về tập cạnh là cả 3 cạnh này. Hay nói cách khác, tập $X$ trong giả mã có thể chứa chu trình, và khi thêm $X$ vào $T$, $T$ không còn là một cây nữa. May mắn là trường hợp này chỉ xảy ra khi đồ thị có một chu trình mà tất cả các cạnh trong chu trình bằng nhau ( bạn có thể chứng minh?). Đây cũng là chìa khóa để chúng ta giải quyết trường hợp cạnh của đồ thị có trọng số không duy nhất.

Ta sẽ định nghĩa một cạnh $xy$ có trọng số "nhỏ hơn" một cạnh $uv$ nếu một trong ba trường hợp sau xảy ra.

  1. $w(xy)$ < $w(uv)$
  2. $w(xy) = w(uv)$ và $\min(x,y)$ < $\min(u,v)$
  3. $w(xy) = w(uv)$ và $\min(x,y) = \min(u,v)$ và $\max(x,y)$ < $\max(u,v)$

Ta kí hiệu "nhỏ hơn" là $\prec$. Với định nghĩa như vậy, áp dụng vào đồ thị tam giác trên ta sẽ có thứ tự:

$w(a,b) \prec w(a,c) \prec w(b,c)$

Giả mã:

IsSmaller($x,y,u,v,w$)
    if $w(xy) $ < $w(uv)$
        return True
    if $w(uv) $ < $w(xy)$
        return False
    if $\min(x,y) $ < $\min(u,v)$
        return True
    if $\min(u,v) $ < $\min(x,y)$
        return False
    if $\max(x,y) $ < $\max(u,v)$
        return True
    return False

 

Như vậy, không có bất kì hai cạnh nào có cùng trọng số theo thứ tự mới này, và do đó, ta đã biến trọng số của đồ thị đầu vào thành duy nhất. Trong code đầy đủ được attach dưới đây, ta sẽ sử dụng ý tưởng này để giải thuật đúng với cả trường hợp đồ thị trọng số không duy nhất.

Code đầy đủ: Boruvka-mst.
Tham khảo

[1] Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech) 15: 153–154.
[2] Jeff Erickson. Lecture Notes on Minimum Spanning Tree. UIUC, 2014.
[3] Jason Eisner. State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, University of Pennsylvania, 1997.
[4] Uri Zwick. Lecture Notes on Minimum Spanning Tree. Tel Aviv University, 2013.

Tags: , , ,