图中的基本概念

Julia999

图的基本概念：这个嘛，大学离散课本有，这就告诉我们要好好听课，基本概念还是要懂滴！~
有一点必须注意：线性表，树都可以为空，但是图不能为空！！！（主要的事情说n遍）


|V|表示图G中顶点的个数，|E|表示边数

图的分类：
有向图vs无向图
无向边：v-w
无序对:(v,w)=(w,v)
w和v互为邻接点
有向边：v->w
有序对:<v,w>   v和w不能对调~~！！！（v邻接到w或w邻接自v）


简单图vs多重图
简单图：无重复边  不存在结点到自身的边
多重图：这还用解释？不是简单图就是多重图了呗~
（简单图可以是有向图，也可是无向图）
但是，有一个很容易错的点：在有向图中，存在从A指向B的边，也存在从B指向A的边，但这样的图不是多重图，因为这样的边不是重复边~！！！


完全图：
有向完全图（任意两个顶点之间都存在边）  n个顶点有n(n-1)/2条边
无向完全图（任意两个顶点之间都存在方向相反的弧） n(n-1)条边


子图：
大白话说就是，一个图中的点和边都是另外一个图的子集，那么就是他的子图（一模一样也是可以称为子图）（边集为空集也可以是子图）
另外的，如果子图的顶点集和图的相等，那么就是他的生成子图


无向图：
连通（有路径存在就连通）
连通图：任意两个节点都是连通的
连通分量：极大连通子图（在连通的情况下，尽可能的包含更多的边）
极小连通子图：连通子图且包含的边最少


有向图：强连通（有相互连通的两条路径）
（注意，是路径不是边）
强连通图：任意两个顶点之间都是可以互相达到的
强连通分量：极大强连通子图（在连通的情况下，尽可能的包含更多的边）
极小强连通子图：强连通子图且包含的边最少


n个顶点的连通图（强连通图）最少有多少天边？
答案：连通图：n-1   强连通图：n


（图：顶点是不可以为空的，但是边可以为空）


生成树：连通图包含全部顶点的一个极小连通子图
n个顶点的图的生成树有n-1条边
连通图只能生成是生成树，非连通图只能生成生成森林


生成森林：非连通图所有连通分量的生成树组成生成森林


顶点的度：边的数目
无向图中：n个顶点，e条边的无向图中的度的总数是：2e
有向图中：出度/入度   出度和入度的和，称为结点的度  有向图中，出度=入度=e


网：为一个图中的边增加了权重


稠密图和稀疏图
边多vs边少
一般对于稠密和稀疏没有一个确切的定义，但是在一般的情况下，我们认为：|E|<V|log|V||的时候，就认为是稀疏


有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图


路径：图中顶点v到顶点w的顶点序列，序列中顶点不重复的路径称为简单路径
路径长度：路径边的长度，若路径最短，就称为距离
回路：第一个顶点和最后一个顶点相同的路径