@[TOC]
图的基本概念
1. 图的定义
图由顶点集V和边集E组成,记为G=(V,E).
图中顶点的个数,也称为图G的阶,用|V| 表示图G中顶点的个数, |E|表示图G中边的条数.
注意:
图不可以为空.即图的点集不能为空,图可以没有边,但是有边,边肯定要连接图.
1.1 无向图和有向图
无向图:
E是无向边,边是顶点的无序对,记为(v,w)=(w,v),其中v,w是顶点.
有向图:
E是有向边(也称弧)的有限集合时,则图G为有向图.弧是顶点的有序对,记为,其中v,w是顶点,v称为弧尾,w称为弧头
1.2 简单图和多重图
简单图:
:one: 不存在重复边
:two:不存在顶点到自身的边(无环的意思)
多重图:
可以存在重复边,可以有环.
2.图的一些术语
2.1 顶点的度,入度,出度
对于无向图,顶点的度是指依附于该顶点边的条数,记为TD(v).
简言之,与顶点接触的边的条数,对一个边来说,他必然会和两条边接触。所以一个无向图中,所有顶点的度之和=2倍的边数。
对于有向图,
入度数以顶点v为终点的有向边的数目,记为ID(v).
出度是以顶点v为起点的有向边的数目,记为OD(v)
顶点的度=其入度和出度之和,即TD(v)=ID(v)+OD(v)
简言之,入度数箭头接触该结点的边数,出度是线尾接触结点的边数
2.2 路径 回路,简单路径,路径长度,点到点的距离
路径:顶点v~p~到顶点~q~之间的一条路径是指顶点序列,v~p~,v~1~,v~2~....v~q~
回路:第一个顶点和最后一个顶点相同的路径叫回路
简单路径:在路径序列中,没有顶点重复的路径。
简单回路:除一个顶点和最后一个顶点外,其余顶点不重复的回路
点到点的距离:从顶点v出发到顶点v的最短路径存在,则称路径的长度为u到v到距离,如果两个顶点之间不存在路径,则记为无穷
2.3 连通图,强联通图
引入基本概念:连通,强连通
连通:无向图中,若从顶点v到顶点w有路径存在,则称v和我是连通的
强连通:有向图中,v到w,w到v之间都有路径,则称这两个顶点是强连通的。
连通图:若图中任意两个顶点都是连通的,则称图G为连通图,否则则称非连通图。
对于n个顶点的无向图G,若G是连通图,则最少有n-1条边。
若G是非连通图,则最少有c^2^~n-1~
强连通图,任何一对顶点都是强连通的图。
强连通图,至少有n条边,形成n条边
3. 图的局部--子图
子图是顶点是图的一部分,顶点之间原先在图中的线可以存在,也可以不存在。但是不是两头都有接触的边,肯定不能存在。
3.1 连通分量,强连通分量
无向图中的极大连通子图称为连通分量。
子图必须连通,且包含尽可能多的顶点和边。
有向图中的极大强连通子图称为有向图的强连通分量。
3.2 生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n,则它的生成树含有n-1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
3.3 生成森林
在非连通图中,连通分量的生成树构成了非连通图的生成森林。
3.4 边的权,带权图
边的权--在一个图中国,每条边都可以标上具有某种含义的数值,该数值称为该边的权值
带权图/网 边上带有权值的图为带权图,也称网。
带权路径长度:当图树带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度。
4. 几种特殊形态的图
4.1 无向完全图和有向完全图
4.2 树和有向树
树:不存在回路,且连通的无向图。
n个顶点的树,必有n-1条边,若边>n-1,则一定有回路
有向树:一个顶点的入度为0,其余顶点的入度均为1的有向图,称为有向树