《有向图理论，算法及其应用》读书笔记 - 有向图相关的基本概念

《有向图理论，算法及其应用》读书笔记 -- 有向图相关的基本概念

有向图 D：

pass

有向伪图：

具有平行弧( 或者称为多重弧 )和自环的 D

有向多重图：

无自环的有向伪图

弧集合 arc_in_from_to_( D, X, Y )：

包含了在 (in)D 图中从 (from) 全体尾部在 X 中头在 (to) Y 中的弧

arc_in_from_to_( D, W, T ) = { ( B, C ) }

arc_in_from_to_( D, T, W ) = { ( C, B ), ( C, A ) }

arc_in_from_to_( D, W, W ) = { ( B, C ), ( C, B ) }

V 的子集合 W 的出邻集 out_neighbourhood( W ):

W 中每个顶点的出邻集的“并”减去 W 中的点

V 的子集合 W 的如邻集 in_neighbourhood( W ):

W 中每个顶点的入邻集的“并”减去 W 中的点

V 的子集合 W 的出度 out_degree( W )：

是全体尾部在 W 中， 头部在 V - W 中的弧的数目 

out_degree( W ) = size( arc_in_from_to_( D, W, V - W ) )

V 的子集合 W 的出度 in_degree( W )： 

in_degree( W ) = size( arc_in_from_to_( D, V - W, V ) )

V 的子集合 W 的半度：

一个集合 W 的出度或者入度均称为这个集合的半度

V 的子集合 W 的度：

W 的两个半度之和

有向伪图某个顶点 v 的出伪度：

全体以 v 为尾部的弧的数目

有向伪图某个顶点的出伪度：

全体以 v 为头部的弧的数目

有向图 D 的最小出度：min( 每个在 D 中的点的出度 )

有向图 D 的最小入度：min( 每个在 D 中的点的入度 )

有向图 D 的最大出度：min( 每个在 D 中的点的出度 )

有向图 D 的最大入度：min( 每个在 D 中的点的入度 )

有向图 D 的最大半度：max( 有向图 D 的最大出度， 有向图 D 的最大入度 )

有向图 D 的最小半度：min( 有向图 D 的最小出度， 有向图 D 的最小入度 )

有向正则图：满足D 中的最大半度等于 D 中的最小半度的图

每个有向多重图基本性质：

顶点集合中所有顶点的入度和等于顶点集中所有顶点的出度和也就是等于弧的总数

该性质也可以用用到有向伪图中。

有向子图 H：

pass

支撑有向子图 H：

若V( H ) == V( D )，则称 H 为有向支撑子图，或者是 D 的因子。