第八章有向图 §8.1有向图的基本概念 定义811每条边都具有一个方向的图称为有向图。严格的说,一个有向图G是一个有序二 元组((G),AG),其中集合(G)是非空的顶点集,集合A(G)是×V的一个子集(有序对, 元素可重复),它是带有方向的边的集合,称为弧集,A(G)中的元素称为弧或有向边 例811G=(,A),其中V={v1,V2V3,V4,v5},有序对集合 A={V,V2>,<"2,v3><V2v3><V3,v>,<n,V><V1,v5<v12v>,<",v5>。 这便定义出一个有向图。 注:(1)相应地,前面所说的边不带有方向的图称为无向图。 (2)一个无向图G可以对应若干个有向图,它称为所对应的有向图的基础图或底图。 (3)将有向图的顶点可用平面上的一个点来表示,弧可用平面上的有向线段来表示(直 的或曲的),这样画出的平面图形称为图(有向图)的图示。 (4)对一条弧e=<,1>,其第二分量顶点v(即箭头指向的顶点)称为它的首顶点,另 顶点称为它的尾顶点。一条首尾顶点相同的弧称为环弧(如下图中es),两条具有相同首顶 点和相同尾顶点的弧称为并行弧(如下图中e2和e3)。既无环弧又无并行弧的有向图称为简 单有向图(或严格有向图)。 例如,例8.1.1中有向图的一个图示为 定义81设v是有向图G的一个顶点。v的入度d=(v)是指指向v的弧的数目;v的出度d(G) 是指从v出发的弧的数目。出度和入度可简写为d'()和d(v)。 最小出度6(G)=mg( 最小入度δ(G)=min{d()} 最大出度△(G)=may{ad"(v) 最大入度△(G)=ma{d(v)} 顶点v的出邻集N()={u(,n)∈AG) 顶点v的入邻集N(v)={1(4,)∈AG)} 定理811对于有向图G,∑d()=26且∑d(v) lE(G) EV(G 证明与无向图情况类似1 第八章 有向图 §8.1 有向图的基本概念 定义 8.1.1 每条边都具有一个方向的图称为有向图。严格的说，一个有向图G G 是一个有序二 元组( ( ), ( )) V G AG JG JG ，其中集合V G( ) JG 是非空的顶点集，集合 A( ) G JG 是V ×V 的一个子集（有序对， 元素可重复），它是带有方向的边的集合，称为弧集， A( ) G JG 中的元素称为弧或有向边。 例 8.1.1 G VA = (,) ，其中 { , , , , } 1 2 3 4 5 V = v v v v v ，有序对集合 12 23 23 34 35 15 15 55 A vv vv vv vv vv vv vv vv = < >< >< >< >< >< >< >< > {, , , , , , , , , , , , , , , }。 这便定义出一个有向图。 注：（1）相应地，前面所说的边不带有方向的图称为无向图。 （2）一个无向图 G 可以对应若干个有向图，它称为所对应的有向图的基础图或底图。 （3）将有向图的顶点可用平面上的一个点来表示，弧可用平面上的有向线段来表示（直 的或曲的），这样画出的平面图形称为图（有向图）的图示。 （4）对一条弧 e=<u, v>，其第二分量顶点 v（即箭头指向的顶点）称为它的首顶点，另一 顶点称为它的尾顶点。一条首尾顶点相同的弧称为环弧（如下图中 e8），两条具有相同首顶 点和相同尾顶点的弧称为并行弧（如下图中 e2和 e3）。既无环弧又无并行弧的有向图称为简 单有向图（或严格有向图）。 例如，例 8.1.1 中有向图的一个图示为 定义8.1.2 设v是有向图G JG 的一个顶点。v的入度 ( ) G d v − JJG 是指指向v的弧的数目；v的出度 ( ) G d G+ JJG JG 是指从 v 出发的弧的数目。出度和入度可简写为d v( ) + 和d v( ) − 。 最小出度 ( ) ( ) min{ ( )} vVG G dv + + ∈ δ = JJG JG 最小入度 ( ) ( ) min { ( )} vVG G dv − − ∈ δ = JJG JG 最大出度 ( ) ( ) max{ ( )} vVG G dv + + ∈ Δ = JJG JG 最大入度 ( ) ( ) max{ ( )} vVG G dv − − ∈ Δ = JJG JG 顶点 v 的出邻集 ( ) { | ( , ) ( )} G N v u vu AG + JJG = ∈ JG 顶点 v 的入邻集 ( ) { | ( , ) ( )} G N v u uv AG − JJG = ∈ JG 定理 8.1.1 对于有向图 G， ( ) 2ε ( ) ∑ = v∈V G d v 且 ∑ = ∈ + ( ) ( ) v V G d v _ ( ) ( ) vVG d v ε ∈ ∑ = 。 证明与无向图情况类似。 v4 e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v5 e8