本帖總結一些經典的圖論問題，通過MATLAB如何計算答案。近期在復習考研，以此來鞏固一下相關知識——雖然考研肯定不能用MATLAB代碼哈哈，不過在實際應用中解決問題還是很不錯的，比C++易上手得多~

---

????????圖論中的圖（Graph）是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事 物間具有這種系。

1.有向圖：弧是頂點的有序對，通過grapi（s,t）函數繪制。s和t分別是兩個邊兩端的點集

? ?無向圖：邊是頂點的無序對，通過digrapi（s,t)函數繪制。

%?函數graph(s,t)：可在 s?和 t?中的對應節點之間創建邊，并生成一個圖
s=[1 1 2 2 2 4 4 3 3 5];
t=[2 3 3 4 5 3 5 5 6 6];
%s和t為端點的集合
G1=graph(s,t);
plot(G1)
%繪制無向圖
G2=digraph(s,t);
%繪制有向圖
plot(G2)

?2.領接矩陣

無向圖的領接矩陣必須是對稱的，意義為兩端點間相互建立聯系；而有向圖則僅需要從頭到尾處建立連接即可（列向為起點，行向為終點）

?

如上圖，對于一個相同的鄰接矩陣，畫出的有向圖與無向圖形狀差距在于邊數——對于對稱的鄰接矩陣，其畫為有向圖后兩節點之間必定各有兩條邊。?

A1=[1,0,1,1,1,0;0,0,0,0,1,1;1,0,0,1,0,1;1,0,1,0,0,0;1,1,0,0,0,0;0,1,1,0,0,0;];
G1=graph(A1);
%plot(G1)
G2=digraph(A1);
plot(G2)

3.增加與刪除

• addedge：添加新邊
• rmedge：刪除邊
• addnode：添加節點
• rmnode：刪除指定節點
• numegdes：邊的數量
• numnodes：節點的數量

此處演示一下增加節點的效果：

s3=[7,7,7,3,3,1,6];
t3=[3,1,6,1,6,6,6];
G3=graph(s3,t3);
G3=G3.addnode(3);
G3=G3.addedge(2,4);plot(G3)

?

4.添加權重and命名結點

s=[1 1  2 3 3  5 6 7 5 2];
t=[2 4  7 4 6  8 7 8 6 8];
weights=[13 19 25 17 11 10  92 29 9 3 ];
names={'H' 'Y' '+' '&' 'J' 'S' 'L' '32'};
G=graph(s,t,weights,names);
plot(G,'EdgeLabel',weights)

（至于一些修改圖片樣式的操作，本貼暫不更新，后期抽空會出繪圖專題~）