1736年歐拉解決了哥尼斯堡七橋問題。他在這一具體問題的基礎上進一步研究，最終找到了一個簡便的原則可以鑒別一個圖(多重圖)能否一筆畫成。

本文中，筆者使用布爾矩陣來存儲一個無向圖，并結合集合論中“傳遞閉包”的概念給出了一種歐拉圖的判定方法。

本文旨在給初學者提供一種可行解，第一次發文，筆者技藝不精，若文章中有錯誤之處，還望各位同仁能夠海涵，希望與大家共同進步。

---

一些概念的解釋：

包含圖的所有頂點和所有邊的閉跡成為歐拉閉跡。

存在一條歐拉閉跡的圖成為歐拉圖。

若$R$是集合$X$上的一個二元關系，則$X$上的所有包含$R$的傳遞關系的交稱為$R$的傳遞閉包，用$R{}^{+}$表示。即：$$R{}^{+}=\underset{R?R\text{’}}{?}R\text{’}\left(\text{其}\text{中}R\text{’}\text{傳}\text{遞}\right)$$亦即$R{}^{+}$是包含$R$的傳遞關系中最小的那個。

Warshall算法是1962年由Warshall提出的一種計算關系傳遞閉包的十分有效的算法，將在下文詳細說明。

注：本文中說的圖都是指無向圖

---

歐拉圖的判斷

在王義和編著的《離散數學引論》(第三版)中，給出了一個圖$G$是歐拉圖的充要條件：

圖$G$是一個歐拉圖當且僅當$G$是連通的且每個頂點的度都是偶數。

因此，歐拉圖的判斷可分為兩步：先判斷圖是否連通，再依次檢查每一個頂點的度是否為偶數即可。

---

布爾矩陣與無向圖

在集合論中，我們曾經使用布爾矩陣來存儲一個二元關系。一個無向圖也可看做非空頂點集$V$上的一個反自反且對稱的二元關系，因此也可使用布爾矩陣來存儲一個無向圖。

---

連通圖與傳遞閉包

圖$G$是一個連通圖，當且僅當圖中任兩個不同頂點間至少有一條路連接。

設圖$G=(U,V)$是一個連通圖，$R?V\times V$是圖$G$對應的二元關系，$R{}^{+}$是關系$R$的傳遞閉包。對$?u,v\in V$，
如果$u,v$鄰接，則$(u,v),(v,u)\in R,$ 又$R?R^{+}$ 從而$(u,v),(v,u)\in R{}^{+}$；
如果$u,v$不鄰接，由于$G$ 是連通圖，$u,v$之間必存在一條路$$u,u{}_1,u{}_2,......,u{}_n,v$$
那么序對$(u,u_1),(u_1,u_2),......,(u_n,v)\in R$，而$R^{+}$又是包含$R$的最小傳遞關系，因此$(u,v)\in R^{+}$，由對稱性，$(v,u)\in R^{+}$。
而對于圖$G$中某點$u$自身，$u$不可能是孤立點，因此一定有某點$v$與之鄰接，因此$(u,v),(v,u)\in R$，從而$(u,u)\in R^{+}$。

由此我們可以得出結論：一個連通圖自身對應的二元關系 $R$ 的傳遞閉包$R^{+}$ 包含了頂點集$V$上的所有二元序對。這在$R^{+}$的布爾矩陣中表現為：所有位置上的值均為1，沒有出現0的位置。如果$R^{+}$某一個位置上的值為0，那么說明這個位置對應的兩個頂點之間必無路連接。

因此，判斷一個圖是否是無向圖，只需求出它的傳遞閉包，再遍歷所有位置看是否有0即可。

下面的問題就只剩下，如何求解傳遞閉包？

---

Warshall算法

在王義和編著的《離散數學引論》(第三版)中，給出了傳遞閉包$R^{+}$的一個計算公式：

設$X$為$n$元集，$R$為$X$上的二元關系，則$$R{}^{+}=\underset{i=1}{\overset{n}{?}}R{}^i。$$

在此基礎上，Warshall提出了一種傳遞閉包的算法，在《離散數學引論》中也給出了其形式化描述：
(由矩陣$B$計算其傳遞閉包$B^{+}$)

1.$A\leftarrow B;$
2.$k\leftarrow 1;$
3.$i\leftarrow 1;$
4.如果$a_{ik}=1$，則對$j=1,2,...,n$ 做 $a_{ij}\leftarrow a_{ij}\vee a_{kj};$
5.$i\leftarrow i+1$，$if\text{??}i\le n\text{??}then\text{??}goto\text{??}4；$
6.$k\leftarrow k+1$，$if\text{??}k\le n\text{??}then\text{??}goto\text{??}3\text{??}else\text{??}\text{停};$
這個算法結束時，$A$中就是矩陣$B^{+}$中的全部元素。

---

程序代碼

對一個圖$G$，在程序中只需利用Warshall算法求出它的傳遞閉包，再檢查所有位置中是否有0即可判斷這個圖的連通性。如果是連通圖，在此基礎上再檢查每一個頂點的度的奇偶性即可判斷這個圖是否是歐拉圖。

需要注意的是，存儲無向圖時，布爾矩陣應該表示為一個對稱的、主對角線上全是0的矩陣。

最后在此附上沒有使用C99特性的C語言代碼：

/*程序功能：輸入圖G，判斷G是否是歐拉圖 *程序輸入：第1行包括兩個整數N和M，分別表示圖G中的頂點個數和邊的個數(N<100) * 接下來的M行中每行包括兩個整數,表示鄰接的兩個點的序號 *程序輸出：如果G是歐拉圖，則輸出Yes，否則輸出No */#include <stdio.h> #define MAX_SIZE 100//華沙算法判斷圖是否連通，連通返回1，否則返回0 //傳入參數為待判定的圖的布爾矩陣和矩陣的大小 int isConnected(int graph[MAX_SIZE][MAX_SIZE], int n) {int i, j, k;int a[MAX_SIZE][MAX_SIZE];//先拷貝矩陣graph到a中，防止后續操作修改原矩陣for (i = 0; i < n; i++){for (j = 0; j < n; j++){a[i][j] = graph[i][j];}}//華沙算法求傳遞閉包，結果放在矩陣a中for (k = 0; k < n; k++){for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (a[i][k]){a[i][j] = a[i][j] || a[k][j];}//a[i][j] = a[i][j] || (a[i][k] && a[k][j]);}}}//連通圖對應關系的傳遞閉包應該全1for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (a[i][j] == 0){return 0;}}}return 1; }int main() {int N, M;int i, j;int Graph[MAX_SIZE][MAX_SIZE] = {0};int v1, v2; //臨時存儲兩個頂點序號int deg[MAX_SIZE] = {0}; //存儲每個頂點的度printf("Input the number of dots and edges:\n");scanf("%d%d", &N, &M);printf("Input the edges:\n");for (i = 0; i < M; i++){scanf("%d%d", &v1, &v2);Graph[v1-1][v2-1] = Graph[v2-1][v1-1] = 1;}//先判斷圖G是否連通if (!isConnected(Graph, N)){printf("No\n");return 0;}//再判斷圖G中每個頂點的度是否均為偶數for (i = 0; i < N; i++){for (j = 0; j < N; j++){deg[i] += Graph[i][j];}if (deg[i] % 2 == 1) //如果有度為奇數的點直接輸出No{printf("No\n");return 0;}}printf("Yes\n");return 0; }

參考文獻：王義和《離散數學引論》(第三版)

總結

以上是生活随笔為你收集整理的基于Warshall算法的连通图及欧拉图判定方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。