第四章 有向图
4.1 有向图与有向 Euler 图
边为有向的图称为有向图，用
D=(V,A)表示，此时有向边
称为弧。
定义 1：点 的出弧数称为出次数，记为
i
v d
+
( )。
i
v
点 的入弧数称为入次数，记为
i
v d
−
( )。
i
v
则 的次数 d(v )=
i
v
i
d
+
( )+d
i
v
−
(v )
i
且 = =m(边的个数)
1
()
n
i
i
dv
+
=
∑
1
()
n
i
i
dv
−
=
∑
①
③
④
②
定义 2：无向图 G，每边指定方向后成为有向图，称为与 G
相伴的有向图，给定一有向图 D，去掉方向后得一
无向图，称为有向图 D 的基础图。
有向完全图称为竞赛图
定义 3：点不重复的有向边列(每条边都与定向一致)，称为
有向路径(道路);点不重复的有向边列构成的回路，称为有
向回路。
在有向图 D 中，若从每一点到其他任何一点至少存在一
条有向路径，称图 D 是强连通的；若 D 非强连通而其基础图
是连通的，称图 D 是弱连通的。
例;
①
②
③
④ ⑤ ⑥
强连通 弱连通
1
