图
2023年9月1日大约 2 分钟
图
基本概念
注意：
线性表可以是空表，树可以是空树，但图不可以是空，即v一定是非空集
无向图、有向图
简单图、多重图
- 简单图
- 多重图
顶点的度、入度、出度
无向图：顶点v的度是指依附于改顶点的边的条数，极左TD(v)
有向图：
入读是以顶点v为终点的有向边的数目，记为ID(v)
出度是以顶点v为起点的有向边的数目，记为OD(v)
顶点的度等于入度和出度之和，TD(v)=ID(v)+OD(v)
顶点-顶点的关系描述
- ：顶点v1到顶点v2之间的一条路径
- ：第一个顶点和最后一个顶点相同的路径称为回路或环
- ：在路径序列中，顶点不重复出现的路径称为简单路径。
- :除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
- :路径上边的数目
- :从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷
- 中，若从顶点v到顶点w有路径存在，则称v和w是的
- 中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是的