图论

当我们研究的对象能够被抽象为离散的元素集合和集合上的二元关系时，用关系图进行表示和处理是很方便的。

• 图可分为有限图和无限图两类
• 有限图：顶点和边都是有限集合

图的基本概念

• 图论研究的不同于几何图形，机械图形的另一种数学结构，不关心图中顶点的位置，边的长短和形状，只关心顶点与边的联结关系

1.定义

一个图G是一个三元组**<V(G),E(G),Φ(G)>**，其中V(G)为顶点集合，E(G)为边的集合，Φ(G)是从边集E到节点偶对集合上的函数

讨论定义：

(a)：V(G={V1,V2,…,Vn}为有限非空集合，V1称为节点，简称V是点集。

(b)：E(G)={e1,…,em}为有限的边集合，e1称为边，每个ei是连结V中的某两个顶点的，称E为边集。

©：可用e=<Vi,Vj>或e=(Vi,Vj)，来表示图的边，这样可把图简化为：G=<V,E>

2.

每条边都是无向边的图称为无向图，每条边都是有向的称为有向图，如果图中既有无向边又有有向边，则称该图为混合图。

该图应如何表示：

G=<V,E>,其中v={a,b,c,d}，E={<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>}

则为：G=<V,E>=<{a,b,c,d},{<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>}>

3.邻接点

在一个图中，若两个结点有一条有向边或者一条无向边关联，则这两个结点称为邻接点

孤立节点：在一个图中不与任何结点相邻的结点称为孤立节点。

4.零图

仅由孤立节点构成的图（点不一定只有一个）

5.平凡图

仅由一个孤立节点构成的图

邻接边：关联于同一结点的两条边

6.自回路（环）

关联于同一结点的一条边称为自回路

7.度数

在图G=<V,E>中，与结点v(v∈V)关联的边数，称为该节点的度数，记作deg(v)

约定：每个环在其对应结点上度数增加2度

最大度，记为：Δ(G)

最小度，记为：δ(G)

• 定理一：每个图中，结点度数的总和等于边数的两倍。

证明：每条边必关联两个结点，而一条边基于关联的每个结点的度数为1。故成立

• 定理二：在任何图中，度数为奇数的结点必定是偶数个。

证明：设V1和V2分别是G中奇数度数和偶数度数的结点集，则由上述定理有：

由于∑deg(v2)是偶数之和，必为偶数，而2|E|是偶数。所以∑deg(v1)也必定为偶数，即|V1|是偶数。

8.入度，出度

在有向图中，射入一个结点的边数称为该结点的入度。由一个结点射出的边数称为该结点的出度。结点的出度与入度的和即为该结点的度数

• 定理三：在任何有向图中，所有节点的入度和等于所有结点的出度之和。

证明：每一条有向边必对应一个入度和出度，若一个结点具有一个入度或出度，则必关联一条有向边。所以，有向图中各结点入读和等于边数，各结点出度和也等于边数。因此，任何有向图中，入度之和等于出度和。

9.

连接于同一对结点的多条边称为是平行的

定义：含有平行边的任何一个图形称为多重图

​ 不含有平行边和环的图称作简单图

10.完全图

简单图G=<V,E>中，若每一对结点间都有边相连，则称该图为完全图。

• 定理四：n个结点的无完全图的边数为：1/2n(n-1)

证明：在有n个结点的无向安全图中，任意两点间都有边连接，n个结点中任意取两点的组合

故有n个结点的无向完全图的边数

11.补图

给定一个图G，由G中所有结点和所有能使G称为完全图的添加边组成的图，称作G的相对于完全图的补图，或简称为G的补图。

12.子图

设图G=<V,E>，如果有图G’=<V’,E’>，且E’⊆E，V’⊆V，则称G’为G的子图。

13.生成子图

如果G的子图包含G的所有结点，则称该子图为G的生成子图。

路与回路

定义一

在图G<V,E>中，设v0，v1,…,vn∈V，e1，e2,…,en∈E，其中e1使关联与结点vi-1，vi的边，结点与边的交替序列v0，e1，v1…en,vn称为联结v0到vn的路。

路的其他概念：

(1)V0和Vn分别称作路的起点和终点

(2)一条路中所有的边的数目被称作路的长度

(3)若V0=Vn则路称作回路

(4)一条路中所有的边均不相同，则此路称为迹

(5)一条路中所有的结点均不相同，则此路称作通路

(6)对于回路，除V0=Vn外，其余结点均不相同，则此路称作图

路的表示方法：

(a)结点表示法：（v1,v2,…,vk)

(b)边表示法：(e1,e2,…,ek)

例：求起始于1，终止于3的路：

​ 结点表示法：(1,2,3)，(1,4,3)

• 无向图的结点连通性：

定义二

设图G为无向图，且vi，vj∈V，若从vi到vj存在一条路的话，则称vi到vj是连通的。

• 定理：无向图结点之间的联通关系是等价关系
• 等价关系：自反性，对称性，传递性

对于无向图G=<V,E>，因为顶点之间的连通关系是等价关系，从而可将V划分成等价类V1，V2，…，Vp。子图G[V1],G[V2],…,G[Vp]称为无向图G的连通分支，简称分支。G的连通分支数记为W(G)。

• 图的连通性：一个无向图G，如果它的任何两个结点间均是连通的，即G只有一个连通分支，则称图G是连通的，否则是非连通的。

对于连通图，常常由于删除了图中的边或点，而影响了图的连通性。所谓在图像删除结点v，就是把v以及与v关联的边都删去。在图中删除某边，仅需把该边删去。`

定义三

设无向图G=<V,E>是连通图，若存在V1⊆V，使图G删除了V1中所有的结点后，所得的子图是不连通的，而对于任意的V2⊆V1，图G删除了V2中所有的结点后，所得的子图是连通的，则称V1是G的点割集。

若某一个结点构成一个点割集，则称该结点为割点。

定义四

设G为无向连通图且为非完全图，则称：

k(G)=min{|V1||V1为G的点割集|}为G的点连通度，简称连通度。

点连通度k(G)是为了产生一个不连通图需要删除的点的最少数目。

对于完全图Kn(n≥1)，删去任何m个(m<n-1)点后仍是连通图但是删去n-1个点后产生了一个平凡图，故规定完全图Kn点连通度为n-1；规定平凡图的点连通度为0.

定义五：设无向图G=<V,E>是连通图，若存在E1⊂E，使图G删除了E1中所有的边后，所得的子图是不连通的，而对于任意的E2⊂E，图G删除了E2中所有的边后，所得的子图是连通的，则称E1使G的边割集。

若某一条边构成一个边割集，则称该条边为割边或桥。

在下图中，{e6},{e5},{e2,e3},{e1,e2},{e3,e4},{e1,e4},{e1,e3},{e2,e4}都是边割集，其中e6和e5使桥。

• 定理：对于任何无向图G，有K(G)≤λ(G)≤δ(G)

  • K(G)：点连通度

  • λ(G)：边连通度

  • δ(G)：最小度(度数最小顶点对应的度数)

例：(1)：给出一些无向简单图，使得：K=λ=δ

​ (2)：给出一些无向简单图，使得：K<λ<δ

解：(1)：无向完全图Kn和零图Nn均满足要求

​ 完全无向图：K=n-1，λ=n-1，δ=n-1

​ (2)：在两个Kn(n≥4)之间放置一个顶点v，使v与两个Kn中任意两个不同的顶点相邻，所得简单图满足要求。

​ 因为这样的图中有一个割点v，所以，K=1(当n=4时，δ=3)

​ 因为有两条边组成的边割集，所以λ=2(当n=5时，δ=4)

###定义五

有向图的结点可达性：设图G为简单有向图，且vi，vj∈V，若从vi到vj存在任何一条路径的话，则称vi到vj是可达的

强连通

如果G的任何两个结点间均可互相可达的，则称图G是强连通的。

单侧联通

如果G的任何两结点间至少有一个结点到另一个结点时可达的，则称G时单侧连通的。

弱联通

如果忽略边的方向，将他看成无向图后，图是连通的则称该图为弱连通的。

• 定理：一个有向图G是强连通的充要条件时：它包含一个回路，该贿赂至少包含每个结点一次。

证明：充分性：如果G中有一个回路至少包含每个结点一次，则G中任何两个结点都是相互可达的，故G是强连通图。

​ 必要性：如果有图是强连通的，则任何两个结点都是相互可达的，故必可做一回路经过图中所有各点。若不然，必有一回路不包含某一结点v，则v与回路上的各结点就不是相互可达的，与强连通条件矛盾。

短程线与距离

###u与v之间的短程线

u与v之间长度最短的通路(u与v连通)

###u与v之间的距离d(u,v)

u与v之间短程线的长度

若u与v不连通，规定d(u,v)=∞

性质

d(u,v)≥0，且d(u,v)=0↔u=v

d(u,v)+d(v,w)≥d(u,w)

图的矩阵表示

矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出图的路径、回路和其它一些性质。

图的邻接矩阵表示方法

定义一

设G<V,E>是简单图，其中V={v1,v2,…,vn}定义一个n*n的矩阵A，并把其中各元素aij表示为：

则称矩阵A为图G的邻接矩阵

例：下图是简单无向图和它的邻接矩阵。

无向图邻接矩阵的性质

1.矩阵A是对称矩阵

2.矩阵A第i行(列)元素之和恰好是顶点vi的度

3.矩阵A第i行主对角线元素为顶点vi处环的数目

4.矩阵A所有元素之和翘尾G的边数的两倍

5.顶点vi是一个孤立的顶点，等价于矩阵A第i行元素全为0

6.G是简单图，等价于矩阵A中只有0和1元素，且对角线上全是0(无环存在)

简单图：没有平行边，没有自回路

有向图邻接矩阵的性质

以下是简单有向图和它的邻接矩阵：

1.矩阵A第i行元素之和为顶点vi的出度，第j列元素之和为顶点vj的入度

2.矩阵A所有元素之和恰为G的边数(及所有的出度或入度)

3.矩阵A第i行主对角线元素为顶点vi处环的数目

4.矩阵A第i行元素全为0，等价于没有任何边以vi为起点。矩阵A第i列元素全为0，等价于没有任何边一vi为终点

5.G是简单图，等价于A中只有0和1元素且对角线元素都是0

矩阵的计算

####定理

设A是图G的邻接矩阵，则A^{k(A的k阶矩)中i行j列元素aij}k等于G中联结vi与vj的长度为k的路的数目

bij表示从节点vi到vj有长度分别为1，2，3，4的不同路径总数

此时bij≠0，表明从vi到vj是可达的

定义二

设G=<V,E>是简单有向图，其中|V|=n(n属于I+)，定义一个n*n矩阵P，它的元素为：

则称P为图G的可达性矩阵。

由Bn矩阵可计算出可达性矩阵，其方法为：若Bn中(i，j)是非"0"元素，则对应的Pij=1否则Pij=0.

定义三

设无向图G=<V,E>，其V={v1,v2,…,vn},E={e1,e2,…,em}。令B=(bij)n*m

则称B为无向图G的完全关联矩阵

权矩阵

一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n*n其中

简单图基本上可以用权矩阵来表示

无向图G的权矩阵是一个对称矩阵

本文链接：https://my.lmcjl.com/post/13810.html