本次课主要内容 有向图 (一)、有向图的概念与性质 (二)、有向图的连通性 (三)、图的定向问题
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本次课主要内容 (一)、有向图的概念与性质 (二)、有向图的连通性 有向图 (三)、图的定向问题
(一)、有向图的概念与性质 1、概念 定义1一个有向图D是指一个三元组VD),ED),中)。其 中，V(①)是非空的顶点集合，E(D)是不与V(D)相交的边集合， 而中D是关联函数，它使D的每条边对应D的有序顶点对不必 相异) 如果e是D的一条边，而u与v是使得中o(u,y=e的顶点， 那么称e是由u连接到v,记为e=<u,v>。同时，称u为e的 弧尾（起点），v为e的弧头（终点）。 注：有向图可以简单地理解为“边有方向的图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 1、概念 定义1 一个有向图D是指一个三元组(V(D) , E(D), фD)。其 中，V(D)是非空的顶点集合，E(D)是不与V(D)相交的边集合， 而фD是关联函数，它使D的每条边对应D的有序顶点对(不必 相异)。 如果e是D的一条边，而u与v是使得фD(u,v)=e的顶点， 那么称e是由u连接到v，记为e=<u, v>。同时，称u为e的 弧尾(起点), v为e的弧头(终点)。 (一)、有向图的概念与性质 注：有向图可以简单地理解为“边有方向的图
例如： e 有向图D e =<V3,V2> v3与v分别是e,的起点与终点。 定义2在一个有向图D中，具有相同起点和终点的边 称为平行边。两点间平行边的条数称为该两点间的重数。 例如，在上图中，e。与e2是平行边
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 例如： 有向图D v4 v3 v2 v1 e2 e1 e4 e3 e6 e5 e7 1 32 e vv , v3与v2分别是e1 的起点与终点。 定义2 在一个有向图D中，具有相同起点和终点的边 称为平行边。两点间平行边的条数称为该两点间的重数。 例如，在上图中，e6与e7是平行边
定义3在一个有向图D中，如果没有有向环和平行边， 则称该图为简单有向图。 非简单有向图D 简单有向图D 定义4设D是有向图，去掉D中边的方向后得到的无向 图G,称为D的基础图。又若G是无向图，给G的每条边 加上方向后得到的有向图D称为G的一个定向图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 定义3 在一个有向图D中，如果没有有向环和平行边， 则称该图为简单有向图。 定义4 设D是有向图，去掉D中边的方向后得到的无向 图G，称为D的基础图。又若G是无向图，给G的每条边 加上方向后得到的有向图D称为G的一个定向图。 e3 非简单有向图D v4 v3 v2 v1 e2 e1 e4 e6 e5 e7 简单有向图D v4 v3 v2 v1 e2 e1 e4 e6 e5
定义5设D是有向图，v是D中顶点。以v为始点的边的条 数称为点v的出度，以v为端点的一个自环算1度。点v的出度 记为d(w);以v为终点的边的条数称为点v的入度，以v为端点 的一个自环算1度。点v的入度记为d(w); 点v的出度与入度之和称为点v的度，记为d)。 d*(y4)=2 d(y4)=2 dv4)=4 有向图D 6
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 定义5 设D是有向图，v是D中顶点。以v为始点的边的条 数称为点v的出度，以v为端点的一个自环算1度。点v的出度 记为d+(v);以v为终点的边的条数称为点v的入度，以v为端点 的一个自环算1度。点v的入度记为d-(v); 点v的出度与入度之和称为点v的度，记为d(v)。 有向图D v4 v3 v2 v1 e2 e1 e4 e6 e5 e7 4 d v() 2 4 d v() 2 4 d v() 4