扫码加入数据分析学习群

1、图的定义

图 是一个顶点集合Vertex和一个顶点间关系的集合Edge组成，记G=(V,E)
V(Vertex)：顶点的有限非空集合。
E(Edge)：顶点间关系的有限集合（边集）。
存在一个结点v，可能含有多个前驱节点和后继结点。
例如：

2、无向图和有向图

无向图

在G=(V,E)中，如果对于任意的结点a,b∈V，当(a,b)∈E时，必有(b,a)∈E（即关系R对称），此图称为无向图。
无向图中用不带箭头的边表示顶点的关系。
例如：
V={1,2,3,4,5}
E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)}

有向图

在G=(V,E)中，如果对于任意的结点a,b∈V，当(a,b)∈E时，(b,a)∈E未必成立，称此图为有向图。
有向图中通常用带箭头的边连接两个有关联的结点。
例如：
V={1,2,3,4,5}
E={

带权图
一般的图边上没有数字，边仅表示两个顶点间相连接关系。如：图2；
图中的边可以加上表示某种含义的数值，数值称为边的权。
例如：

3、顶点的度

在无向图中，顶点v的度是指与顶点v相连的边的数目D(v)。
如：图2中，D(2)=3。

在有向图中，
入度：

以该顶点为终点的边的数目。
出度：

以该顶点为起点的边的数目。
度=该顶点的（入度+出度）
如： 图3中，ID(3)=2，OD(3)=1，D(5)=ID(5)+OD(5)=1+2=3。

奇点\偶点:

度数为奇数的顶点叫奇点，度数为偶数的点叫偶点。
所有顶点的度等于边数的两倍。

4、路径、回路

在图G=(V,E)中，过对于结点a,b，存在满足下述条件的结点序列x1...xk(k>1)有x1=a,xk=b,(xi,xi+1)∈E,i=1...k−1，则称结点序列x1=a,x2,...,xk=b为结点a到b的一条路径，而路径上边的数目(k-1)则称为该路径的长度。
如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，称此路径为一条简单路径。x1=xk的简单路径称为回路（也称为环）。
例如：

路径(1,2,3,5)，长度=3；
路径(1,2,3,5,2)，长度=4；
回路(1,2,5,4,1)，长度=4；

路径(1,2,5,4)，长度=3.

5、连通性

连通：如果存在一条从顶点u到v的路径，则称u和v是连通的。
连通图：图中任意两个顶点都是连通的，称为连通图；否则为非连通图。
连通分量：无向图中的极大连通子图。
例如：
图2，图3，连通图。

图5，非连通图。
有3个连通分量：{1,2,4,5},{3,6},{7,8}