本帖總結(jié)一些經(jīng)典的圖論問(wèn)題，通過(guò)MATLAB如何計(jì)算答案。近期在復(fù)習(xí)考研，以此來(lái)鞏固一下相關(guān)知識(shí)——雖然考研肯定不能用MATLAB代碼哈哈，不過(guò)在實(shí)際應(yīng)用中解決問(wèn)題還是很不錯(cuò)的，比C++易上手得多~

---

????????圖論中的圖（Graph）是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事 物間具有這種系。

1.有向圖：弧是頂點(diǎn)的有序?qū)?#xff0c;通過(guò)grapi（s,t）函數(shù)繪制。s和t分別是兩個(gè)邊兩端的點(diǎn)集

? ?無(wú)向圖：邊是頂點(diǎn)的無(wú)序?qū)?#xff0c;通過(guò)digrapi（s,t)函數(shù)繪制。

%?函數(shù)graph(s,t)：可在 s?和 t?中的對(duì)應(yīng)節(jié)點(diǎn)之間創(chuàng)建邊，并生成一個(gè)圖
s=[1 1 2 2 2 4 4 3 3 5];
t=[2 3 3 4 5 3 5 5 6 6];
%s和t為端點(diǎn)的集合
G1=graph(s,t);
plot(G1)
%繪制無(wú)向圖
G2=digraph(s,t);
%繪制有向圖
plot(G2)

?2.領(lǐng)接矩陣

無(wú)向圖的領(lǐng)接矩陣必須是對(duì)稱的，意義為兩端點(diǎn)間相互建立聯(lián)系；而有向圖則僅需要從頭到尾處建立連接即可（列向?yàn)槠瘘c(diǎn)，行向?yàn)榻K點(diǎn)）

?

如上圖，對(duì)于一個(gè)相同的鄰接矩陣，畫(huà)出的有向圖與無(wú)向圖形狀差距在于邊數(shù)——對(duì)于對(duì)稱的鄰接矩陣，其畫(huà)為有向圖后兩節(jié)點(diǎn)之間必定各有兩條邊。?

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：添加節(jié)點(diǎn)
• rmnode：刪除指定節(jié)點(diǎn)
• numegdes：邊的數(shù)量
• numnodes：節(jié)點(diǎn)的數(shù)量

此處演示一下增加節(jié)點(diǎn)的效果：

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.添加權(quán)重and命名結(jié)點(diǎn)

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)

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