實驗要求：
1.給定一非負整數序列（例如：(4,2,2,2,2)），
2.判斷此非負整數序列是否是可圖化的，是否是可簡單圖化的，
3.如果是可簡單圖化的，根據Havel定理程序求出對應的簡單圖，并輸出此簡單圖的相鄰矩陣（默認第i行對應頂點vi），
4.判斷此簡單圖是否是連通的，
5.如果是連通圖，判斷此圖是否是歐拉圖，如果是歐拉圖，請輸出一條歐拉回路（輸出形式如：v2->v1->v5->v3->v4->v5->v2），
--------------------------------------------分割線------------------------------------------------
對于整數序列的定義，這里運用了struct來進行運算，方便后續代碼實作
struct k
{
int len;//該點的度數
int num;//該點的編號
int d;//該點的度數，保存不動，方便運算結束后將度數恢復
}a[10000];
可圖化的判斷：所有頂點的度數和為偶數，
for (int i = 1; i <= n; i++)
{
cin >> s;
int t = s;
while (s < 0|| s !=t)
{
cout << "不能輸入負數,小數" << endl;
cin >> s;
}
a[i].len = s;
a[i].num = i;
a[i].d = a[i].len;
sum += a[i].len;
}
if (sum % 2 != 0)
{
cout << "該序列不可圖化" << endl;
return 0;
}
可簡單圖化判斷：Havel定理
Havel定理描述
給定一個非負整數序列{d1,d2,…dn}，若存在一個無向圖使得圖中各點的度與此序列一一對應，則稱此序列可圖化，進一步，若圖為簡單圖，則稱此序列可簡單圖化，（頂點的度是指與該頂點相鈴的頂點數）
可圖化的判定比較簡單：d1+d2+…dn=0(mod2)，關于具體圖的構造，我們可以簡單地把奇數度的點配對，剩下的全部搞成自環，
可簡單圖化的判定，有一個Havel定理，是說: 我們把序列排成不增序，即d1>=d2>=…>=dn，則d可簡單圖化當且僅當d’=(d2-1, d3-1, … d(d1+1)-1, d(d1+2), d(d1+3), … dn)可簡單圖化，
原文鏈接：https://blog.csdn.net/qq_35033987/article/details/78889683）
例如：（4 4 2 2 2 2）可簡單圖化——>（3 1 1 1 2）可簡單圖化——>
（3 2 1 1 1）可簡單圖化——>（1 0 0 1）可簡單圖化——>（1 1 0 0）可簡單圖化——>（0 0 0 0）可簡單圖化
（0 0 0 0）顯然可簡單圖化，故（4 4 2 2 2 2）可簡單圖化
代碼見下：
bool cmp(k x, k y)
{
return x.len > y.len;
}
bool book = 1;//判斷是否可簡單圖化;
int t = n;//t為當前序列元素不為零的個數
for (int i = 1; i <= t; i++)
{
sort(a + i, a + n + 1, cmp);//快排
if (a[i].len == 0)
break;
if (a[i].len > t - i)//若最大元素大于剩余元素個數，即會出現負數
{
book = 0;
break;
}
for (int j = 1; j <= a[i].len; j++)//模擬Havel
{
a[i + j].len--;
c[a[i].num][a[i + j].num] = 1;//c[i][j]=1——>i與j有邊
c[a[i + j].num][a[i].num] = 1;
if (a[i + j].len == 0)
t--;
}
}
if (book == 0)
{
cout << "不可簡單圖化" << endl;
return 0;
}
cout << "可簡單圖化" << endl;
輸出簡單圖相鄰矩陣：直接將 c[n][n] 輸出
cout << " " ;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
}
cout << endl;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
for (int j = 1; j <= n ; j++)
{
if (c[i][j] == 1)
cout << "1 ";
else
cout << "0 ";
}
cout << endl;
}
判斷圖是否連通：暴力dfs遍歷
void tomako(int x)
{
p[x] = 1;//p[x]=1 ——> x遍歷過
for (int i = 1; i <= n; i++)
{
if (p[i] == 1)
continue;
if (c[x][i] == 1)
tomako(i);
}
}
tomako(1);
bool book1 = 1;//可否簡單圖化標簽
for (int i = 1; i <= n; i++)
{
if (p[i] == 0)
{
book1 = 0;
break;
}
}
if (book1 == 0)
{
cout << "不連通" << endl;
return 0;
}
cout << "連通" << endl;
歐拉圖定義：
歐拉圖是指通過圖（ 無向圖 或 有向圖 ）中所有邊且每邊僅通過一次通路，相應的回路稱為歐拉回路，. 具有 歐拉回路 的圖稱為歐拉圖（Euler Graph）
**
無向圖G是歐拉圖的充分必要條件是G 是連通圖并且沒有奇數度頂點
**
證明：
平凡圖顯然成立
必要性：圖G是歐拉圖，證明G中沒有奇數度節點
G是歐拉圖 ——> G中存在歐拉回路 ——>歐拉回路中每個點每出現在歐拉回路的序列中就必定會獲得兩個度 ——>歐拉序列中的所有的點必然都是偶數度的節點 ——>不存在奇數度的節點
充分性：
G中沒有奇數度的節點，證明G是歐拉圖——數學歸納法
假設邊數是m
1.m=1，沒有奇數度節點——該邊只能是一個環——G是歐拉圖
2.假設m<=k成立，現在證明m=k+1成立
G連通且沒有奇數度頂點——G中必然存在圈——刪去圈上的所有的邊——假設獲得了s個連通分量，每個連通分量有最多k條邊，并且都是偶數度的節點（圈上的邊每條給頂點貢獻兩個度）——根據上述的歸納假設每個連通分量都是一個歐拉圖——我們現在將圈復原——必然存在一條歐拉回路連接了所有的節點并回到原點（這潭訓路的主路就是剛才刪去的圈，每次進入連通分量的時候，遍歷連通分量的歐拉回路在出來繼續走圈）
(原文鏈接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384)
故一個無向圖為歐拉圖——>無奇數頂點
代碼如下：
for (int i = 1; i <= n; i++)
{
if (a[i].d % 2 == 1)//奇度
{
book2 = 0;
break;
}
}
if (book2 == 0)
{
cout << "不是歐拉圖" << endl;
return 0;
}
尋找歐拉回路：
有兩種方法：Fleury演算法， 逐步插入回路法
這里使用逐步插入回路法
1.逐步插入回路法
根據我們上面的證明，我們其實已經得到了一種求解歐拉回路的演算法，那就是我們找到了一個圈，我們從圈開始，每次找到一個連通分量就進入走完連通分量的回路，知道我們的主路的圈全部走完，那么我們的走過的序列就是一個歐拉回路
即尋找與當前頂點相關聯的頂點，洗掉兩點之間的邊，更新主頂點為關聯的點，
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
}
若走到盡頭（x的度數為零），將x添加進陣列，回溯回上個頂點，判斷是否有路可走，
完整代碼如下：
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
sum1++;
ol[sum1] = a[x].num;//ol[i]為歐拉回路第i個元素的編號
}
該代碼可能不太容易理解，可以舉個例子畫圖一步一步跟著代碼實作來理解
舉例：
本圖是一個無向圖
1——2
| |
| |
3——
| |
| |
4————5
如上所示，邊為（1,3）（1,2）（2,3）（3,4）（3,5）（4,5）
我們從1開始深搜(隨機的，別的情況也會出現，這里模擬最容易看清本質的搜索程序)
1——>2——>3——>1
這時候我們會發現回到原點了，但是顯然我們并沒并且1走到了死胡同里，演算法除了問題嗎？
并不是，我們接著看
DFS搜索到1，這時候并沒有出邊開始執行add操作，我們將1節點加入最后的歐拉回路序列
函式遞回回溯，3這時有多余的出邊指向4，繼續遞回至頂點4
1——>2——>3——>4——>5——>3
又回到了頂點3這時候，頂點3也沒有多余的出邊，add 3
1——>2——>3——>4——>5
函式回溯至頂點5，頂點5沒有多余的出邊，add 5
1——>2——>3——>4
函式回溯至頂點4,4沒有多余的出邊，add 4
1——>2——>3 add 3
1——>2 add 2
1 add 1
最終結果1 3 5 4 3 2 1 為歐拉回路
通過上面的模擬我們已經可以發現了這個逐步插入回路法的DFS的實作的精髓了
實際上我們第一次搜索會起點的時候，就是找到了一個圈，然后我們函式回溯找每個節點是否還有多余的出邊，有多余的出邊就從這個入口節點我們就繼續遞回下去（進入一個連通分量），直到回傳到入口節點，直到入口節點沒有多余的出邊的時候我們這時開始回溯一次回溯連通分量，將連通分量加入結果序列直到將整個圈上的所有的頂點都回溯完之后，回傳最開始的起點，歐拉回路查找完畢
（該例子解題程序參考其他文章，原文鏈接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384）
完整代碼：
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
sum1++;
ol[sum1] = a[x].num;//ol[i]為歐拉回路第i個元素的編號
}
for (int i = 1; i < sum1; i++)
cout<<"v"<< ol[i]<<"->";
cout << "v" << ol[sum1];
最后放出全部代碼
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct k
{
int len;
int num;
int d;
}a[10000];
int ol[10000];//歐拉回路
int c[100][100];//c[i][j]=1——>i與j有邊
int n, sum = 0,sum1=0;
bool book2 = 1;
int p[10000] = {};
bool cmp(k x, k y)
{
return x.len > y.len;
}
void tomako(int x)
{
p[x] = 1;//p[x]=1 ——> x遍歷過
for (int i = 1; i <= n; i++)
{
if (p[i] == 1)
continue;
if (c[x][i] == 1)
tomako(i);
}
}
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
sum1++;
ol[sum1] = a[x].num;//ol[i]為歐拉回路第i個元素的編號
}
int main()
{
cin >> n;
double s;
for (int i = 1; i <= n; i++)
{
cin >> s;
int t = s;
while (s < 0|| s !=t)
{
cout << "不能輸入負數,小數" << endl;
cin >> s;
}
a[i].len = s;
a[i].num = i;
a[i].d = a[i].len;
sum += a[i].len;
}
if (sum % 2 != 0)
{
cout << "該序列不可圖化" << endl;
return 0;
}
bool book = 1;//判斷是否可簡單圖化;
int t = n;//t為當前序列元素不為零的個數
for (int i = 1; i <= t; i++)
{
sort(a + i, a + n + 1, cmp);//快排
if (a[i].len == 0)
break;
if (a[i].len > t - i)//若最大元素大于剩余元素個數，即會出現負數
{
book = 0;
break;
}
for (int j = 1; j <= a[i].len; j++)//模擬Havel
{
a[i + j].len--;
c[a[i].num][a[i + j].num] = 1;//c[i][j]=1——>i與j有邊
c[a[i + j].num][a[i].num] = 1;
if (a[i + j].len == 0)
t--;
}
}
if (book == 0)
{
cout << "不可簡單圖化" << endl;
return 0;
}
cout << "可簡單圖化" << endl;
cout << " " ;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
}
cout << endl;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
for (int j = 1; j <= n ; j++)
{
if (c[i][j] == 1)
cout << "1 ";
else
cout << "0 ";
}
cout << endl;
}
tomako(1);
bool book1 = 1;
for (int i = 1; i <= n; i++)
{
if (p[i] == 0)
{
book1 = 0;
break;
}
}
if (book1 == 0)
{
cout << "不連通" << endl;
return 0;
}
cout << "連通" << endl;
for (int i = 1; i <= n; i++)
{
if (a[i].d % 2 == 1)//奇度
book2 = 0;
}
if (book2 == 0)
{
cout << "不是歐拉圖" << endl;
return 0;
}
tomako1(1);
for (int i = 1; i < sum1; i++)
cout<<"v"<< ol[i]<<"->";
cout << "v" << ol[sum1];
return 0;
}
以及幾個有用的樣例：
輸入 1
8
2 2 2 2 4 4 4 4
輸出 1
輸入 2
5
4 2 2 2 2
輸出 2
歐拉回路答案不唯一，需自己驗證
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/385892.html
標籤：其他