6.1.1 图：基本概念

一，基本概念

1.基本定义

（1）图的定义

顶点集不可以是空集，但边集可以是空集。

（2）

有向图的表示：

圆括号

 无向图的表示：

 尖括号

简单图、多重图：

简单图：

（1）不存在重复边（2）不存在从顶点到自身的边

多重图：

（1）图G中某两个节点之间的边数多于一条

（2）允许通过同一条边与自己关联，则G为多重图

数据结构只探讨简单图

三，顶点的度。入度，出度

 对于无向图：

顶点v的度是指依附于该顶点的边的条数，记为TD(V)

无向图的全部顶点的度的和等于边数的两倍

 对于有向图：

入度是以顶点v为终点的有向边的数目，记为ID（v）

出度是以顶点v为起点的有向边的数目，记为OD（v）

顶点的度是其入度和出度之和。

四，顶点与顶点的关系描述

（1）路径——两个不同的顶点之间的顶点序列。

（2）简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。

（3）点到点的距离：从顶点u出发到顶点v最短路径若存在，则此路径的长度称为从u到v的距离,若不存在此路径，距离记为无穷。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

有向图中中，若从顶点v到顶点w和顶点w和顶点v之间都有路径存在，则称v和w之间是强连通的。

这里的路径可以是很多条。

比如说A和B之间就是强连通的，而B和E之间就不是。

连通图和强连通图 

1）特指无向图

2）特指有向图

 常见考点：

1）对于n个积极点的无向图G

若G是连通图，则最少有n-1条边

若G是非联通图，则最多可能有

EP:

当有5个顶点的情况下：

 地下四个顶点（两两相连）

上面一个顶点只要与下面任意一个顶点相连，就可以使之为连通图

2）

 

接下来我们学习子图：（研究图的局部）

1）理解子图的概念（首先必须是个图）

2）包含原图所哟有的vertex记为生成子图。（顶点集不可以是空集，边集可以是空集）

连通分量

1）连通     2)极大（包含尽可能多的顶点和边）

生成树：

 

 若图中的顶点数为n，则它的生成树含有n-1条边。对于生成树，若看去他的一条边，则会变成非联通树，若加上一条边则会形成一个回路。

与生成树对应得是生成森林

实际应用：

几种特殊形态的图:

 

 

树和森林

 n个顶点的树，必有n-1条边

n得顶点的图，若边数大于n-1，则是有回路的，那就不是树了。