⑴ 數學圖論中有哪些典型模型
偶圖模型
凡涉及兩類事物間的聯系（即只考慮兩類事物間的聯系，而不考慮同類事物間的聯系），均可抽象成偶圖模型。作圖時，將兩類事物分成兩行或者兩列。這類模型通常被包含在後續的模型中，但因許多現實問題可抽象成該模型，所以單列出來討論。
(1) 倉庫與銷售間
M：點代表倉庫或銷售點，連線代表倉庫與銷售店間的關聯
(2) 上課安排問題
Q：學校有6位教師將開設6門課程。六位教師的代號是Xi（i=1,2,3,4,5,6)，六門課程代號是Yi （i=1,2,3,4,5,6)。已知，教師X1能夠勝任課程Y2和Y3；教師X2能夠勝任課程Y4和Y5；教師X3能夠勝任課程Y2；教師X4能夠勝任課程Y6和Y3；教師Y5能夠勝任課程Y1和Y6；教師X6能夠勝任課程Y5和Y6。
M：點表示教師或者課程，連線表示當且僅當該教師能勝任該課程
2.2 最短路模型
凡涉及到最小狀態轉換問題，均可轉化為最短路模型。點表示允許的狀態，連線表示狀態的轉換（可逆與不可逆分別對應於無向圖、有向圖）。
(1) 最短航線
M：點表示城市，連線表示當且僅當兩城市有直達航線，並在該線上註明兩城市的距離，即權值
A：問題轉化為求兩點間的最短路徑
(2) 狀態轉換
Q：某兩人有一隻8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升。求最少的操作次數能均分酒。
M：設x1,x2,x3分別表示8,5,3升酒壺中的酒量，則
點表示組合(x1,x2,x3) ,連線表示當且僅當可通過倒酒的方式相互變換
A：問題轉化為在該圖中求點(8,0,0)到點(4,4,0)的一條最短路
(3) 狼羊菜渡河
Q：在一河岸有狼，羊和捲心菜。擺渡人要將它們渡過河去，由於船太小，每次只能載一樣東西。由於狼羊，羊捲心菜不能單獨相處。問擺渡人至少要多少次才能將其渡過河？
M：但是以下組合不能允許出現：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。岸上只能允許出現10種組合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。
點表示可允許的組合，連線當且僅當兩種情況可用載人(或加一物)的渡船相互轉變。
A：問題轉化為求由頂點「人狼羊菜」到頂點「空」的一條最短路。
2.3 最小生成樹模型
道路鋪設
Q：道路鋪設，使得任意兩個地方均可達，並且費用最小
M：點表示工廠(假設是工廠)，任意兩點連線，並標出鋪設需要的費用
A：問題轉化為求該圖的最小生成樹
2.4 歐拉圖模型
通俗地講，G是歐拉圖當且僅當G存在經過每條邊恰好一次，並且回到起始點的跡。
(1) 哥尼斯堡七橋問題
Q：能否從一點出發，走遍7座橋，且通過每座橋恰好一次，最後仍回到起始地點
M：點表示陸地，連線表示橋
A：問題轉化為G是否存在E圖
(2) 中國郵遞員問題
Q：郵遞員必須走過他投遞范圍內的每一條街道至少一次，選擇一條盡可能短的路線
M：點表示路口，連線表示當且僅當兩路口有直達街道
A：若G是E圖，通過Fleury演算法構造Euler環游，即為所求。否則，按一定規則添加重復邊，再用Fleury演算法構造Euler環游。
2.5 哈密爾頓圈模型
(1) 旅行售貨員問題——TSP
一售貨員要到若干城市去售貨，每座城市只經歷一次，問如何安排行走路線，使其行走的總路程最短。
例子：
Q：一電腦代理商要從她所在城市出發，乘飛機去六個城市，然後回到出發點，如果要求每個城市只經歷一次，能否辦到？給出行走方案。
M：點表示城市，連線表示兩城市有直達航線
A：該圖是否存在H圈
(2) 圓桌會議座位安排
Q：若幹人圍圓周開會，每個人會不同的語言，如何安排座位，使得每個人能夠和他身邊的交流
M：點表示人，連線表示當且僅當兩個人能交流，即至少會同一種語言。(可能你一下子想到的偶圖模型，的確該問題可以抽象成偶圖模型，但很難轉化為圖論問題)
A：給出該圖的一個H圈
2.6 匹配模型
(1) 旅遊座位安排
Q：有一個旅行團要組織一批人去旅遊，其中一些人是朋友他們要乘坐公共汽車去，而車上的位子是成對的。因此為了讓大家旅途更愉快，旅行團負責人需要將成對的朋友安排在一起。給出一種安排方案。
M：點表示旅行團的人，連線表示當且僅當兩人是朋友
A：求該圖的最大匹配
(2) 研究生找工作
Q：學生能找到理想工作嗎？
M：點表示研究生或者工作，連線表示當且僅當學生申請了該工作
A：問題轉化為求飽和每個頂點的一個匹配，即完美匹配
(3) 最優分派問題
M：點表示工作或者人員，構造完全偶圖，邊的權值表示該工人做此份工作的效率
A：問題轉化為求該圖的最優匹配
2.7 平面圖模型
平面模型可以這樣理解，交通網路，使得不交叉，且無需修高架橋、隧道（這里的隧道顯然跟山洞不同）
(1) 電路板設計問題
Q: 連接電路元件間的導線間不能交叉。否則，當絕緣層破損時，會出現短路故障。
M；點表示電路元器件，連線表示元器件間的連接
A；該圖是否可平面
(2) 景區空調管道的設計
M：點表示景區，連線表示當且僅當兩景點間要鋪設空調管道
A：能否把上圖畫在平面上，使得邊不會相互交叉？
(3) 3間房子和3種設施問題
Q：要求把3種公用設施(煤氣，水和電)分別用煤氣管道、水管和電線連接到3間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？
M：點表示公用設施或者房子，連線表示該類公用設施連接到該房子
A：抽象出來的圖是否可平面嵌入
2.8 著色模型
點著色問題對應於頂點集合的一種劃分方式，對應於分類問題。邊著色對應於邊集合的一種劃分方式，也對應於分類問題。區分點著色模型和邊著色模型，主要在於抽象出來的模型，是相鄰的頂點還是相鄰的邊不能著同一種顏色。
(1) 點著色模型
① 考試時間安排
Q：使得學生們不會有相互沖突的考試，最小安排數
M：點表示待考的課程，連線表示至少有一個學生同時選擇這兩門課
A：問題轉化為求該圖的點色數(把互不沖突的課程、考試安排在同一個時間段完成)
② 課程安排問題
Q: 學生選擇課程中，使得學生選課不會發生沖突，如何制訂一張課時數盡可能小少的課表
M：點表示課程，連線表示當且僅當有某個學生同時選了這兩門課程
A：問題轉化為求該圖的點色數
③ 交通燈的相位設置問題
Q：為了(最終)讓所有的車輛都能夠安全通過路口，對於交通燈來說，所需要的相位的最小數是多少
M：點表示車道，連線當且僅當兩個車道上的車不能同時安全地進入路口
A：問題轉化為求該圖的點色數
(2)邊著色模型
① 排課表問題
Q：設有m位教師，n個班級，其中教師xi要給班級yj上pij節課。求如何在最少節次排完所有課。
M：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi與yj間連pij條邊，得偶圖G=(X, Y)。
A：問題轉化為求該圖的邊著色數
(2) 比賽安排問題
Q：最少天完成比賽
M：點表示參賽人，連線當且僅當兩人有比賽
A:問題轉化為求一種最優邊著色，即用最少色數進行正常邊著色
2.9 覆蓋模型
覆蓋模型，對應於控制問題，通俗地講點覆蓋對應於用最少的點來控制所有邊(即任一邊至少有一個頂點在點獨立集中)，邊覆蓋對應於用最少的邊控制所有的點。均對應於控制問題。
(1) 哨站設計
Q：城市設置哨崗，使得哨兵能監管所有街道的最少哨崗數
M：點表示交叉口，連線表示存在直達街道
A：問題轉化為求該圖的點覆蓋
2.10 強連通性定向圖模型
(1) 城市交通網設計問題
Q：一座城市為某種需要，要把所有街道改為單行道，使得人們在任意兩個位置都可以相互到達。如何設計單行道方向
M：頂點表示街道交叉口，連線當且僅當存在直達街道
A：問題等價於在模型圖中給出其強連通定向
(2) 競賽圖
M：循環比賽的結果可以用所謂的「競賽圖」來表示。u隊戰勝了v隊，則由點u向v畫一條有向邊。顯然，「競賽圖」是完全圖的一種定向圖。
⑵ 急求c++fleury演算法歐拉迴路代碼
1#include <stdio.h>
2#include <string.h>
3
4
5struct stack
6{int top , node[210];} f; //頂點的堆棧
7
8int a[201][201]; //圖的鄰接矩陣
9
10int n;
11
12void dfs(int x) //圖的深度優先遍歷
13{
14int i;
15
16f.top ++; f.node[f.top] = x;
17
18for (i = 1; i <= n; i ++)
19
20 if (a[i][x] > 0)
21 {
22 a[i][x] = 0; a[x][i] = 0; //刪除此邊
23
24 dfs(i);
25
26 break;
27 }
28}
29
30void Euler(int x) //歐拉路演算法
31{
32int i , b;
33
34f.top = 0; f.node[f.top] = x; //入棧
35
36while (f.top >= 0)
37{
38 b = 0;
39
40 for (i = 1; i <= n; i ++)
41 if (a[f.node[f.top]][i] > 0)
42 {b = 1; break;}
43
44 if (b == 0) //如果沒有點可以擴展，輸出並出棧
45 {
46 printf("%d " , f.node[f.top]);
47
48 f.top --;
49 }
50 else {f.top --; dfs(f.node[f.top+1]);} //如果有，就DFS
51 }
52}
53
54int main()
55{
56
57int m , s , t , num , i , j , start;
58
59 //input
60
61 scanf("%d %d" , &n , &m); //n頂點數 m邊數
62
63 memset(a , 0 , sizeof(a));
64
65 for (i = 0; i < m; i ++)
66 {
67 scanf("%d %d" , &s , &t);
68 a[s][t] = 1; a[t][s] = 1;
69 }
70
71
72 //判斷是否存在歐拉迴路
73
74 s = 0; start = 1;
75
76 for (i = 1; i <= n; i ++)
77 {
78 num = 0;
79
80 for (j = 1; j <= n; j ++)
81 num += a[i][j];
82
83 if (num % 2 == 1)
84{start = i; s ++;}
85 }
86
87 if ((s == 0) || (s == 2))
88Euler(start);
89 else printf("No Euler path\n");
90
91 getchar(); getchar();
92 return 0;
93}
94