什么是出度介绍

一般来说，图可分为有向图和无向图。有向图的所有边都有方向，即确定了顶点到顶点的一个指向；而无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。在一些问题中，可以把无向图当作所有边都是正向和负向的两条有向边组成。顶点的度是指和该顶点相连的边的条数。特别是对于有向图来说，顶点的出边条数称为该顶点的出度，顶点的入边条数称为该顶点的入度。

出度基本介绍

在无向图中，顶点所具有的边的数目称为顶点的度。如图1(a)中．无向图

的顶点

的度为3，顶点

的度为2。

在有向图中，以顶点为头的边的数目称为该顶点的入度；以顶点为尾的边的数目称为该顶点的出度；一个顶点的入度与出度之和称为该顶点的度。如图1中，有向图

的顶点

的入度为2，出度也是2，顶点

的度则为4。

设无向图

有

个顶点，e条边，每个顶点的度为

，则有：

出度相关概念

出度图的定义

一个图由一个非空有限顶点集和一个边的有限集组成。图

的顶点集和边集分别用

和

表示，则图G可表示成。

在图中，若每条边都用箭头指明了方向，则称此图为有向图，否则为无向图。有向图中的边用

表示，其中

是有向图的两个顶点，

称为尾，

称为头，在有向图中用从

到

的箭头表示，见图2(a)。无向图中的边用

表示，

为无向图的两个顶点。图2(b)是无向图。无向图的边

是无序的，也就是说

与

表示同一条边。

从图2中可知，(b)是一棵树，而(a)不是树，所以说树是图的特例。具有n个顶点的无向图，若有

条边，称之为完全图。图2中(c)便是一个完全图。具有n个顶点的无向图，至多有

条边；具有n个顶点的有向图，则至多有

条边。

出度子图

设图

的顶点集和边集为

和

，图

的顶点集和边集为

和

，若：

则称图

是图

的子图。例如，图2中图

是图

的子图，图

是图

的子图。