图的基本概念

 

定义 图G由顶点集V和边集E组成，记为G=(V,E)

• V(G):表示图G中顶点的有限非空集
• E(G):表示图G中顶点之间关系的集合
• V={v1,v2,v3,…,vn}:顶点集
• |V|:表示图G中顶点的个数
• E={(u,v)|u∈V,v∈V}:边集，说明一条边存在的前提是一定要连着两个顶点
• |E|:表示图G中边的条数

无向图和有向图 无向图

• E是无向边（简称边）的有限集合，则G为无向图
  • 记为(v,w)=(w,v)，称w和v互为邻接点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v、w相关联

有向图

• E是有向边（简称弧）的有限集合，则G为有向图
  • 记为，其中v和w为顶点，v是弧尾，w为弧头，称为顶点v到顶点w的弧，也称为v邻接到w，或者w邻接自v。注意≠

顶点的度、出度和入度 无向图

• TD(v):依附于顶点v的边的条数
• 特性：全部顶点的度等于边数的2倍

有向图

• 入度ID(v):以顶点v为终点的有向边的数目
• 出度OD(v):以顶点v为起点的有向边的数目
• 特性1：TD(v)=ID(v)+OD(v)
• 特性2：全部顶点的入度之和和出度之和相等，并且等于边数

边的权、带权图/网

• 权值：每条边上带有特定含义的数值
• 带权路径长度：一条路径上所有边的权值之和
• 网：边上带有权值的图称为带权图，又称为网

点到点的关系 路径、回路、简答路径、简单回路

• 路径：顶点vp到顶点vq之间的一条路径是指顶点序列vp，vi1，vi2，…，vq
• 回路（环）：第一个顶点和最后一个顶点相同的路径称为回路或者环
• 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径
• 简单回路：除第一个顶点和最后一个顶点除外，其余顶点不重复出现的回路

路径长度

• 路径长度：路径上边的数目

距离

• 距离：从顶点u到顶点v的最短路径如果存在，就叫做距离。如果不存在路径，则距离为∞

无向图顶点的连通性、连通图

• 顶点的连通性：从顶点v到顶点w有路径存在，则v到w为连通的
• 连通图：图G中任意两个结点都是连通的

有向图顶点的强连通性、强连通图

• 顶点的强连通性：从顶点v到顶点w和从顶点v到顶点v之间都有路径，则v和w为强连通
• 强连通图：图G中任意两对结点都是强连通的

图的局部 子图

• 子图：图G为(V,E)，图G‘为(V’,E’)，E‘为E的子集，V’为V的子集，则称G‘为G的子图
• 生成子图：满足V(G’)=V(G)的子图G’就是G的生成子图（必须包含所有的结点，但是不一定包含所有的边）

连通分量-极大连通子图

• 无向图G
• 子图必须连通
• 尽可能包含更多的顶点和边

强连通分量-极大强连通子图

• 有向图G
• 子图必须强连通
• 尽可能包含更多的边

生成树-包含全部顶点的极小连通子图

• 无向连通图G
• 包含图G中的全部顶点
• 极小连通子图：边尽可能少且保持图连通

生成森林-各连通分量的生成树

• 无向非连通图G
• 先生成 连通分量（极大连通子图）
• 再对各个连通分量生成极小连通子图

几种特殊形态的图 完全图

• 无向完全图：无向图中任意两个顶点之间都存在边
• 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧

稠密图、稀疏图

• 稠密图：边数很多的图
• 稀疏图：边数很少的图
• 判断依据：|E|<|V|log|V|时G为稀疏图

树、森林、有向树

• 树：不存在回路，且连通的无向图
• 有向树：一个顶点入度为0、其余顶点的入度为1的有向图

常见考点 n个顶点无向图

• 所有顶点的度之和=2|E|
• 若G为连通图，则最少可能有n-1条边；若|E|>n-1，则一定有回路
• 若G为非连通图，则最多可能有(n-1)C2条边
• 无向完全图共有nC2条边

n个顶点有向图

• 所有结点的入度之和=出度之和=|E|
• 所有顶点的度之和=2|E|
• 若G为强连通图，则最少有n条边（形成一个环状）
• 有向完全图共有2*nC2条边