图论术语

无向图与有向图

无向图

无向图：一个无向图$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​}

则其关联矩阵
$$\begin{gathered} M=(m_{ij}{)}_{n\times m} \\ {m}_{ij}=\{\begin{array}{ll}1& 顶点v_i与边e_j关联\\ 0& 顶点v_i与边e_j不关联\end{array} \end{gathered}$$

• 设有向图为$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​}

则其关联矩阵
$$\begin{gathered} M=(m_{ij}{)}_{n\times m} \\ {m}_{ij}=\{\begin{array}{ll}1& 顶点v_i为弧a_j的始端\\ 0& 顶点v_i与弧a_j不关联\\ -1& 顶点v_i为弧a_j的末端\end{array} \end{gathered}$$

顶点与顶点的邻接矩阵

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

则其邻接矩阵
$$\begin{gathered} W=(w_{ij}{)}_{n\times n} \\ {w}_{ij}=\{\begin{array}{ll}1& 顶点v_i与v_j相邻\\ 0& 顶点v_i与v_j不相邻或i=j\end{array} \end{gathered}$$

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

则其邻接矩阵
$$\begin{gathered} W=(w_{ij}{)}_{n\times n} \\ {w}_{ij}=\{\begin{array}{ll}1& 弧(v_i,v_j)\in A\\ 0& 弧(v_i,v_j)\notin A或i=j\end{array} \end{gathered}$$

比如，下面的有向非赋权图的邻接矩阵为
$$W=\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]$$

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

则其邻接矩阵
$$\begin{gathered} W=(w_{ij}{)}_{n\times n} \\ {w}_{ij}=\{\begin{array}{ll}{w}_{ij}& 顶点v_i与v_j相邻\\ 0或\infty & 顶点v_i与v_j不相邻或i=j\end{array} \end{gathered}$$

比如，下面的无向赋权图的邻接矩阵为
$$W=\left[\begin{array}{ccccc}0& 0& 10& 60& \\ 0& 0& 5& 20& \\ 10& 5& 0& 1& \\ 60& 20& 1& 0& \end{array}\right]$$

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

matlab代码

主要函数为

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

利用代码创建下图：

邻接矩阵创建图并显示

% 输入邻接矩阵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);

顶点对创建图并显示

% 输入一个顶点
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)

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")