Julia999 发表于 2019-8-4 21:03:20

图中的基本概念

图的基本概念:这个嘛,大学离散课本有,这就告诉我们要好好听课,基本概念还是要懂滴!~
有一点必须注意:线性表,树都可以为空,但是图不能为空!!!(主要的事情说n遍){:9_217:}


|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的顶点序列,序列中顶点不重复的路径称为简单路径
路径长度:路径边的长度,若路径最短,就称为距离
回路:第一个顶点和最后一个顶点相同的路径



页: [1]
查看完整版本: 图中的基本概念