图的定义
图G由顶点集V和边集E组成,记为$G=(V,E)$,其中V(G)表示图G中顶点的有限非空集;$E(G)$表示图G中顶点之间关系(边)集合。若$V={v_1, v_2,v_3,…,v_n}$,则用$|V|$表示图G中顶点的个数,$E={(u, v) | u \in V, v \in V}$,用$|E|$表示图G中边的条数。
线性表和数都可以为空,图不能是空图,顶点集不能为空,可以是空边集
有向图
若E是有向边(也称弧)的有限集合时,则图G为有向图。弧是顶点的有序对,记为[HTML_REMOVED],其中v,w是顶点,v称为弧尾(箭头尾部),w称弧头(箭头处),[HTML_REMOVED]称为从v到w的弧,也称v邻接到w。
指向=邻接 有向边=弧
无向图
若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v,w)或(w,v)。可以说w和v互为邻接点。边(v,w)依附于w和v,或称边(v,w)和v,w关联。
无向边=边=依附=关联=互为指向
简单图
图G满足以下两个条件为简单图
1. 不存在重复边
2. 不存在顶点到自身的边
完全图(简单完全图)
无向图$|E|$的取值范围为$[0, n(n-1)/2]$,有$n(n-1)/2条边的无向图称为完全图$,在完全图中任意两个顶点之间都存在边。对于有向图,$|E|的取值范围为0到n(n-1)$,有n(n-1)条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在相反的两条弧。
完全图是每个点到每个点都有边
有向完全图是每个点到每个点都有来回的弧(弧有向,边无向)
子图
设两个图$G=(V,E)$和$G^{\prime}=(V^{\prime}, E^{\prime})$,若$V^{\prime}是V的子集$,且$E^{\prime}$是E的子集,则称$G^{\prime}是G的子图$。若有$V(G^{\prime})=V(G)$的子图$G^{\prime}$ ,则称其为G的生成子图。
不是V的子集与E的子集都能构成G的子图,可能子边集所需的点不在子点集里
子点集与子边集构成子图
点集与子边集构成生成子图
连通、连通图和连通分量
在无向图中,若顶点V到顶点w有路径存在,称v和w是连通的。若图任意两个顶点都是连通的,则称G为连通图,否则称为非连通图。无向图中的极大连通子图称为连通分量
连通:顶点v可以通过多个顶点到达顶点w,不一定是v与w有直接相连的边
连通分量就是图中与其他子图不连通的子图
强连通图,强连通分量
在有向图中。如果有一对顶点v和w,从v到w和从w到v之间都有路径,则称这两个顶点是强连通的。若任何一对顶点都是强连通的,则此图为强连通图。 有向图的极大强连通子图称为有向图的强连通分量。
连通是对无向图来说;强连通是对有向图来说,因为比无向图多了一条弧,连通性更“强”了
n个点的有向图是强连通图最少需要的边数是n,即每个点都指向同一方向,最后一个点指向第一个点形成一个环
生成树,生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点树为n,则它的生成树有n-1条边。
非连图中,连通分量的生成生树构成了非连通图的生成森林。(每个非连通分量都有自己的生成树)
生成树去掉一条边就会变成非连通图,加上一条边会形成回路。
顶点的度,入度和出度
在无向图中,顶点的度是指依附于顶点v的边数的条数,记为TD(v)。
在有向图中,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目记为ID(v),出度是以顶点v为起点的有向边的数目记为OD(v)。
n个点e条边的无向图,每个点的度的和=2e,因为一条边提供2个度
入度之和=出度之和=边数,因为每条边都提供了一个出度和一个入度
边的权和网
标在边上的数值称为该边的权值。这种边上带有权值的图称为带权图,也称网。
稠密图和稀疏图
边数少是稀疏图,反之是稠密图,当G满足|E|<|V|log|V|时视为稀疏图。
路径,路径长度和回路
顶点p到顶点q之间有一条路径是指顶点序列$p,v_1,v_2,…,v_m,q$。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。
若一个图有n个顶点,且有多于n-条边,则此图一定有环,
简单路径,简单回路
路径中顶点不重复称为简单路径。除第一个顶点与最后一个顶点相同外,其余顶点不重复的回路称为简单回路。
距离
顶点v到顶点u的最短路径存在,此路径长度称为从v到u的距离;若不存在,则距离为无穷
有向树
一个顶点的入度为0,其余顶点的入度均为1的有向图称为有向树。v v