1.图的定义
- 图(graph)由顶点集V(Vertex)和边集E(Edge)组成,记为G = (V,E)
- 图(顶点集)不能为空,但是图的边集可以为空
2.有向图
边带方向,E = <v, w>:使用<>表示,v为弧尾,w为弧头
E = {<1, 2> <2, 1> <2, 3>}
3.无向图
边不带方向,E = (v, w):使用()表示,v和w的元素可以互换
E = {(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)}
4.简单图、多重图、完全图
- 不存在重复边
- 不存在顶点到自己的边
满足1、2条件为简单图,反之则为多重图;如果任意两个顶点之间都存在边,则为完全图,共n(n-1)/2条边,(有向图中,则需要任意两个顶点中都存在方向相反的两条边,共n(n-1)条边)
5.顶点的度、入度和出度
无向图——度:
- 度为该顶点的边数
- 无向图的度的总数为2倍边数(2E):一条边为两个顶点的度数分别+1
有向图——入度、出度:
- 入度:指向该顶点的边数(终点为该顶点)记为ID(v)
- 出度:指出该顶点的边数(起点为该顶点)记为OD(v)
- 有向图中的入度=出度=边数(E):每有一条边,一个顶点的入度+1,另一个顶点的出度+1
6.路径、回路、路径长度
路径:一个顶点到另一个顶点的顶点序列
路径长度:路径上经过的边的数量
点到点的距离:如果一个顶点到另一个顶点的最短路径存在,则为两点之间的距离;如果不存在,则该距离为无穷
回路:第一个顶点和最后一个顶点相同的路径(环)
简单路径:路径中不存在重复出现的顶点
简单回路:除了第一个顶点和最后一个顶点外,回路中没有重复出现其他顶点
7.连通、强连通
无向图——连通:
- 两个顶点之间路径存在,则这两个顶点连通
- 如果整个无向图中任意两个顶点都是连通的,则为连通图
- n个顶点的无向图G:
- 若G为连通图,最少为n - 1条边
- 若G为非连通图,最多为条边
有向图——强连通:
- 顶点a到顶点b路径存在,且顶点b到顶点a路径存在,则这两个顶点强连通
- 如果整个有向图中任意两个顶点都是强连通的,则为强连通图
- n个顶点的有向图G:若G为强连通图,最少为n条边(构成回路)
8.子图、生成子图
设有两个图G = (V, E)和G1 = (V1, E1),若V1是V的子集,E1是E的子集,则G1是G的子图;当V1和V1相等时,G1为G的生成子图(E未必相等)
9.连通分量、强连通分量
- 无向图中极大连通子图为连通分量:子图必须连通、且包含尽可能多的边和顶点
- 有向图中极大强连通子图为强连通分量:子图必须强连通、且包含尽可能多的边和顶点
10.生成树、生成森林
连通图中,包含图中全部顶点的极小连通子图:边尽可能少,但是是连通的
非连通图中,连通分量的生成树组合而成生成森林
11.边的权、带权图
边的权:边上带有某种意义的数值
带权图:边上带有权值的图
带权路径长度:一条路径上所有边的权值之和