个人数学建模算法库之图的创建与可视化

图论术语

无向图与有向图

无向图

无向图：一个无向图$G$，由非空顶点集 V = { v 1 , v 2 , . . . v n } V=\{v_1,v_2,...v_n\} V={v1​,v2​,...vn​}和边集 E = { e 1 , e 2 , . . . e m } E=\{e_1,e_2,...e_m\} E={e1​,e2​,...em​}组成，通常记作$G(V,E)$

边与顶点：一条边连接两个顶点(可相同)。故任意一条边可由两个顶点表示：$e_k=(v_i,v_j)$ 。顶点$v_i,v_j$ 称为边$e_k$的端点。边$e_k$与顶点$v_i,v_j$关联。

无向图特点：无向图中的边没有方向，即$(v_i,v_j)=(v_j,v_i)$

相邻：有公共端点的边称为相邻的边(邻边)。同一条边的两个端点，称为相邻的顶点。

有向图

弧:有方向的边称为弧。$a_k=(v_i,v_j)$ 代表弧$a_k$从顶点$v_i$出发指向顶点$v_j$。$v_i$称为$a_k$的始端，$v_j$称为$a_k$的末端。$a_k$称为$v_i$的出弧，称为$v_j$的入弧。

有向图:一个有向图$D$，由非空顶点集 V = { v 1 , v 2 , . . . v n } V=\{v_1,v_2,...v_n\} V={v1​,v2​,...vn​}和弧集 A = { a 1 , a 2 , . . . a m } A=\{a_1,a_2,...a_m\} A={a1​,a2​,...am​}组成，通常记作$G(V,A)$

有向图特点：有向图中的边带有方向，即$(v_i,v_j)\ne (v_j,v_i)$

基本图与定向图 :有向图$D=(V,A)$去掉所有边的方向后可以得到对应无向图$G=(V,E)$。称$G$为$D$的基本图，$G$为$D$的定向图。如无向图$G_1$与有向图$D_1$之间。

简单图，完全图与赋权图

环：两个端点为同一个顶点的边

重边/平行边:有相同端点的两条或多条边

孤立点:与任何边都不关联的顶点

简单图:无环无重边的图

完全图:任意两顶点都相邻的简单图

赋权图(网络):每条边$e_k$都附加一个权重$w_k$的图 。可记作$N=(V,E,W)$。

顶点的度

顶点$v$的度:无向图中，与顶点$v$关联的边数;有向图中，弧从顶点$v$出入的总次数。记作$d(v)$

出度:有向图中，从顶点$v$引出的弧的数目。记作$d^{+}(v)$

入度:有向图中，引入顶点$v$的弧的数目。记作$d^{-}(v)$

在有向图中，$d(v)=d^{+}(v)+d^{-}(v)$

子图与图的连通性

子图/母图:设有图$G_1(V_1,E_1)$,$G_2(V_2,E_2)$ .若$G_1$的顶点和边都在$G_2$中能找到，即$V_1\subset V_2,E_1\subset E_2$,则称$G_1$是$G_2$的子图，$G_2$是$G_1$的母图。$G_2$删减若干个顶点和若干条边，可得到$G_1$

生成子图/支撑子图：若$G_1$是$G_2$的子图且两者顶点相同，则称$G_1$是$G_2$的生成子图/支撑子图。$G_2$删减若干条边可生成$G_1$

道路/路 ：称$v_0{e}_1{v}_1{e}_2...e_k{v}_k$为从顶点$v_0$到$v_k$的一条道路。其中边$e_i$与顶点$v_{i-1}$,$v_i$相关联。$v_0$为路的起点，$v_k$为路的终点

路长：路所经过的边的条数。即$k$

迹:途径边互异的路。

轨道:途经顶点互异的路。

回路:起点和终点重合的路。

圈:起点和终点重合的轨道。

两顶点间的距离:两顶点间的最短轨道长。

连通:若两顶点间存在路，则称两顶点连通。

连通图:若图的任意两顶点连通，则称该图为连通图。否则称为非连通图。

连通分支:连通图的连通子图

强连通图:若有向图两个顶点$v_i,v_j$间两个方向上都存在路，则称该图为强连通图。

图论表示

边与顶点的关联矩阵

• 设无向图为$G(V,E)$, V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}, E = { e 1 , e 2 , . . . , e m } E=\{e_1,e_2,...,e_m\} E={e1​,e2​,...,em​}

则其关联矩阵
M = ( m i j ) n × m m i j = { 1 顶点 v i 与边 e j 关联 0 顶点 v i 与边 e j 不关联 M=(m_{ij})_{n\times m} \\ m_{ij}=

M=(mij​)n×m​mij​={10​顶点vi​与边ej​关联顶点vi​与边ej​不关联​

• 设有向图为$D(V,A)$, V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}, A = { a 1 , a 2 , . . . , a m } A=\{a_1,a_2,...,a_m\} A={a1​,a2​,...,am​}

则其关联矩阵
M = ( m i j ) n × m m i j = { 1 顶点 v i 为弧 a j 的始端 0 顶点 v i 与弧 a j 不关联 − 1 顶点 v i 为弧 a j 的末端 M=(m_{ij})_{n\times m} \\ m_{ij}=

M=(mij​)n×m​mij​=⎩ ⎨ ⎧​10−1​顶点vi​为弧aj​的始端顶点vi​与弧aj​不关联顶点vi​为弧aj​的末端​

顶点与顶点的邻接矩阵

• 设无向非赋权图为$G(V,E)$, V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}

则其邻接矩阵
W = ( w i j ) n × n w i j = { 1 顶点 v i 与 v j 相邻 0 顶点 v i 与 v j 不相邻或 i = j W=(w_{ij})_{n\times n} \\ w_{ij}=

W=(wij​)n×n​wij​={10​顶点vi​与vj​相邻顶点vi​与vj​不相邻或i=j​

• 设有向非赋权图为$D(V,A)$, V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}

则其邻接矩阵
W = ( w i j ) n × n w i j = { 1 弧 ( v i , v j ) ∈ A 0 弧 ( v i , v j ) ∉ A 或 i = j W=(w_{ij})_{n\times n} \\ w_{ij}=

W=(wij​)n×n​wij​={10​弧(vi​,vj​)∈A弧(vi​,vj​)∈/A或i=j​

比如，下面的有向非赋权图的邻接矩阵为
W = [ 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 ] W=

[011000001000010010010001010100000010]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢000000101110110000000010001001000100⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{cccccc}0& 1& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 0& 1& 0& 0& 0& 1\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\end{array}\right]$$

W=⎣ ⎡​000000​101110​110000​000010​001001​000100​⎦ ⎤​

• 设无向赋权图为$G(V,E,W)$, V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}

则其邻接矩阵
W = ( w i j ) n × n w i j = { w i j 顶点 v i 与 v j 相邻 0 或 ∞ 顶点 v i 与 v j 不相邻或 i = j W=(w_{ij})_{n\times n} \\ w_{ij}=

W=(wij​)n×n​wij​={wij​0或∞​顶点vi​与vj​相邻顶点vi​与vj​不相邻或i=j​

比如，下面的无向赋权图的邻接矩阵为
W = [ 0 0 10 60 0 0 5 20 10 5 0 1 60 20 1 0 ] W=

[0010600052010501602010]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢0010600052010501602010⎤⎦⎥⎥⎥$$\left[\begin{array}{cccc}0& 0& 10& 60\\ 0& 0& 5& 20& \\ 10& 5& 0& 1\\ 60& 20& 1& 0\end{array}\right]$$

W=⎣ ⎡​001060​00520​10501​602010​⎦ ⎤​

邻接矩阵的看法或写法为:固定一个顶点(行)，看另外的顶点(该行的各列)是否与它相邻，权为多少。

matlab代码

主要函数为

graph() % 创建无向图
disgraph() % 创建有向图
plot() % 绘制图
1
2
3

利用代码创建下图：

邻接矩阵创建图并显示

% 输入邻接矩阵A
A = [ 0 0 10 60;
    0 0 5 20;
    10 5 0 1;
    60 20 1 0];	
    
% 输入结点名
nodes=["v_1","v_2","v_3","v_4"];

% 使用邻接矩阵A和结点名nodes创建赋权无向图
G = graph(A,nodes);

% plot函数显示图
plot(G,"EdgeLabel",G.Edges.Weight,"NodeFontSize",12);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

顶点对创建图并显示

% 输入一个顶点
s = [1 1 2 2 3];

% 输入另一个顶点
t = [3 4 3 4 4];

% 输入结点名
nodes = ["v_1","v_2","v_3","v_4"];

% 输入权值
weights = [10 60 5 20 1];

% 使用顶点对s,t和结点名nodes创建赋权无向图
G = graph(s,t,weights,nodes);

% plot函数显示图
plot(G,"EdgeLabel",G.Edges.Weight,"NodeFontSize",12)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Python代码

用到的库为networkx（简写为nx)

顶点对创建图并显示

# 导库
import networkx as nx

# 输入边和权
s = [f"$v_{i}$" for i in [1, 1, 2, 2, 3]]
t = [f"$v_{i}$" for i in [3, 4, 3, 4, 4]]
w = [10, 60, 5, 20, 1]
edges = list(zip(s, t, w))

# 创建空图并添加顶点和边权
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 计算顶点位置
pos = nx.spring_layout(G)

# 绘制无权图
nx.draw(G, pos, with_labels=True,font_size=14)

# 追加绘制权
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels,font_color="red")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22