图的基本概念
图的定义
图G由顶点集V和边集E组成，记为G=(V,E)。
- 其中V(G) 表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系集合（即边集）。
- 用|V|表示图G中的顶点个数，又称为图的阶。
- 用|E|表示图G中边的条数。
特别地，线性表可以是空表，树可以是空树，图不能是空图。即必须有顶点，可以无边。
简单图
图满足不存在重复的边，也不存在顶点到自身的边，称为简单图。
多重图
图某两个结点之间存在多条边，或允许顶点与自身相连，称为多重图。
父子图
G=(V,E),G’=(V’,E’)，若V’是V的子集,E’是E的子集，则G‘是G的子图。
如果G的子图的顶点集和G一样，即V(G’)=V(G)，则称该子图为G的生成子图。
无向图
若E是无向边（简称边），则图为无向图。
边是顶点的无序对，记为(v,w)。
连通图和连通分量
在无向图中，若v到w有路径存在，则两点是连通的。
若任意两点均连通，则图为连通图，否则为非连通图。
连通分量指的是极大连通子图（极大指的是边数极大，即该连通子图包含它所有的边）
常见结论：
-
非连通图最多可能有$C_{n-1}^{2}$条边。
-
连通图最少有$n-1$条边；小于$n-1$条边必是非连通图。
-
$n$个顶点保证连通，则有$C_{n-1}^{2}+1$条边。
注：必须前$n-1$个顶点互通，最后任连一条边到最后一个顶点上。
生成树和生成森林
连通图的生成树指的是包含全部顶点的极小连通子图（极小指的是边数极小而保持连通）
常见结论：
-
$n$个顶点的生成树含有$n-1$条边。
-
生成树任意去掉一条边则变成非连通图，任意加上一条边则形成环。
推论：$n$个顶点$n$条边可能不是连通图，但一定有环。
有向图
若E是有向边（简称弧），则图为有向图。
弧是顶点的有序对，记为<v,w>。起点v为尾，终点w为头。
强连通图和强连通分量
在有向图中，若从v到w和从w到v都有路径存在（即能往返），则两点是强连通的。
若任意两点均是强连通的，则图为强连通图。
强连通分量指的是极大强连通子图（极大指的是边数极大，即该强连通子图包含它所有的边）
常见结论：强连通图最少有$n$条边。
顶点的度
无向图中，顶点的度是依附于该顶点的边的条数，记为TD(v)。
有向图中，顶点的度分为入度和出度，入度是以顶点v为终点（即指向该点）的有向边的数目，记为ID(v)；出度是以顶点v为起点（即从该点指向其他点）的有向边的数目，记为OD(v)。顶点的度等于其入度和出度数之和。即TD(v)=ID(v)+OD(v)。
