【离散数学】图论

图

无向图

<V,E>有序二元组，代表一个无向图G

V是顶点的集合，元素为顶点；称为顶点集

E是边的集合，元素为无向边；称为边集合

有向图

<V,E>有序二元组，代表一个有向图G

V是顶点的集合，元素为顶点；称为顶点集

E是边的集合，元素为无向边；称为边集合

 

RUN

图：有向图+无向图，G代表有向图，D代表无向图阶：定点数，有n个顶点称n阶图 

 零图：只有点没有边，有n个点为n阶零图，记为Nn

 

 空图：顶点集为空（什么也没有），记为 ∅

标定图：有符号标识的图

非标定图：无符号标识的图

基图：有向图原型（无向图）1.1为1.2的基图

端点 关联

无向图：ek = (Vi,Vj)则Vi、Vj为ek的端点（就是一条线两边的点），ek与Vi（Vj）关联

if Vi != Vj ，则ek与Vi（Vj）的关联次数为1（就是一个点只碰了一次这个线）

if vi = vj，则ek与vi（vj）的关联次数为2，并称ek为环（一个点碰了线2次）

 

有向图：ek = (vi,vj)则vi，vj为ek的端点，vi为始点，vj为终点，ek 与 vi（vj）关联

if vi ≠ vj，则ek与vi（vj）的关联次数为1（就是一个点只碰了一次这条线）

if vi = vj，则ek与vi（vj）的关联次数为2，并称ek为环（一个点碰了线2次）

 

相邻：vi 与 vj 有一条边连接，则两顶点相邻，两边至少有一个公共顶点则两边相邻 

孤立点：V3

一些集合 

无向图：G = <V,E>, ∀v∈V

邻域：与v1相邻的点的集合（相邻见上） 

闭邻域：邻域 + v1（自己）的集合

关联集：与v相关联的边的集合（关联见上）

 有向图：D = <V,E>, ∀v∈V

后继元集：从v2出发，到达的点的集合先驱元集：到达v2的出发点的集合 

邻域：先驱元集+后继元集

闭邻域：

 

平行边：一对顶点的无向边多于1条，则为平行边（有向边：方向也需要相同

重数：平行边的条数 

多重图：含平行边的图

简单图：不含平行边，不含环的图（在有向图中，相同端点，方向不同的边，不算平行度 

 

无向图 G = <V,E>, ∀v∈V

度数：v关联的边的数量（环以v做两次端点）,即：dg(v)，v点勾搭的边数

G的最大度：G中含有的最大度数

G的最小度：G中含有的最小度数

有向图：D = <V,E>, ∀v∈V

出度：v为始点的次数（箭头出去的数量）

入度：v为终点的次数（箭头进来的数量）

度数：出度+入度

记牢符号

 悬挂顶点：度数为1的顶点

悬挂边：与悬挂顶点关联的边

偶度（奇度）顶点：度为偶数(奇数)的顶点

握手定理

无向图：所有顶点的度数之和等于边数的2倍；度数 = 边数*2=2m

有向图：所有顶点的度数之和等于边数的2倍；入度之和 = 出度之和 = 边数

度数列：G=<V,E>为一个n阶无向图，V{v1，v2，...，vn}，称d(v1)，d(v2)，...，d(vn)为G的度数列对于顶点标定的无向图,它的度数列是唯一的

可图化：度数列的和为偶数，即度数列可图化，反之则不可图化

 简单可图化，在可图化的基础上，d(vn)max < n，则可实现简单图化 同构 

同构图：两个无向图（有向图），具备阶数相同，边数相同，度数列相同等条件。

 

完全图&竞赛图 

完全图：G为n阶简单图，图内每个顶点与其余顶点都相邻（每个点都有线相连）

则G为n阶无向（有向）完全图

竞赛图：D为n阶有向简单图，若基图是无向完全图，则其为竞赛图

 母图&导出子图 类似于父集与子集的关系 以产生原因分辨图为V1/E1的导出子图  补图 

 

人话：

与G含有相同顶点，能够使G补成完全图的图，为G的补图

通路与回路   通路：即一个点到另一个点，所走的路径

vi0与vil即为通路的始点与终点

其中边的条数为通路的长度

若vi0 = vil，则为回路

若经过的边没有重复，则为简单通路（回路），反之则为复杂回路（通路）

若经过的顶点没有重复，则为初级通路/路径（初级回路/圈）

长度为奇数，称奇圈，为偶数，称偶圈

图的连通性

连通：无向图G = <V,E>，若两顶点之前存在通路，则称两点连通，即u~v, d(vi , vi)

连通图：即无向图G = <V,E>任何两个顶点都是连通的

注意！！！

与完全图存在区别，连通指的是能从这个点走到那个点就好，完全图则需要任意两个顶点都要有边

完全图（n >= 1）都是连通图

零图（n >= 2）都是非连通图

短程线（距离）：即两点间的最短通路

割集：在连通图中删去某些边，某些点，使连通图变得不连通

点割集：在原图中删去顶点的集合，使连通图变得不连通

割点：点割集中只有一个顶点v

边割集：在原图中删去边的集合，使连通图变得不连通

割边/桥：：点割集中只有一条边e

点连通度：最小删掉的顶点数

无向完全图的点连通度为：n-1

非连通图：0

k-连通图：点连通度为k

边连通度：最小删掉的边数

无向完全图的边连通度为：n-1

非连通图：0

r-边连通图：边连通度为r

点连通度 <= 边连通度 <= 最小度

 有向图的连通性：∀vi ,  vi∈V，表示方法有所不同 d<vi  ,  vi>