图论课件--有向图.ppt

图论及其应用应用数学学院怖丹咋诬琅菜鸦塑响隐勇肢智莫绽牙撇森囚啥恰暂过舷潞西虾俱浚逞胚抬图论课件--有向图图论课件--有向图1本次课主要内容(一)、有向图的概念与性质(二)、有向图的连通性有向图(三)、图的定向问题(四)、有向路与有向圈舌右锭窿艳领雄裳庇霍楚伺鲜钨廓田壕声征全哎呵枝铸随桃锤洲淄湾硷擎图论课件--有向图图论课件--有向图21、概念定义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的弧头(终点)。(一)、有向图的概念与性质注:有向图可以简单地理解为“边有方向的图”。佩榆烧濒粉莉辆欲散赊器呕养沃歇琐拣承钞氧贵童椅骇惮右哎嫩汾袖形敞图论课件--有向图图论课件--有向图3例如:有向图Dv4v3v2v1e2e1e4e3e6e5e7v3与v2分别是e1的起点与终点。定义2在一个有向图D中,具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。例如,在上图中,e6与e7是平行边。遮畔纵谦圆窑袒梨麻脏坎挞君秩肤媳掠侣盼住第萨盔这楚涸怎借友怠贪裕图论课件--有向图图论课件--有向图4定义3在一个有向图D中,如果没有有向环和平行边,则称该图为简单有向图。定义4设D是有向图,去掉D中边的方向后得到的无向图G,称为D的基础图。又若G是无向图,给G的每条边加上方向后得到的有向图D称为G的一个定向图。e3非简单有向图Dv4v3v2v1e2e1e4e6e5e7简单有向图Dv4v3v2v1e2e1e4e6e5库撇学庚析抨请缮补酱雀褐枫隆浸积俗培炬摇虾微菊珐愉仗秀喇窿艾瘸赎图论课件--有向图图论课件--有向图5定义5设D是有向图,v是D中顶点。以v为始点的边的条数称为点v的出度,以v为端点的一个自环算1度。点v的出度记为d+(v);以v为终点的边的条数称为点v的入度,以v为端点的一个自环算1度。点v的入度记为d-(v);点v的出度与入度之和称为点v的度,记为d(v)。有向图Dv4v3v2v1e2e1e4e6e5e7稍场蝴部坷懒梅港拍帝表洱镀鼓顽雷三卷卤绪受参沪食夏嵌玻皖揩羊提禽图论课件--有向图图论课件--有向图6例1一个简单图有多少个定向图?答:因为每条边有2种定向方式,所以共有2m(G)种定向。例2求证:G存在一个定向图D,使得对,有证明:不失一般性,设G是连通图。G中奇度顶点个数必然为偶数个,将偶数个奇数度顶点配对,然后在每一对配对顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G的一欧拉环游C,然后顺次地在C上标上方向,由此得到C的定向图C1。在C1中,去掉添加的边后,:诊拖遗堵拼秩袜双亭锹侗馁涸撩禁耕鄙铺桨角阜黍簿炽冷滇炊苗棘咕贞百图论课件--有向图图论课件--有向图7对,有2、性质定理1设D=(V,E)是有向图,则:证明:由出度与入度的定义立即可得上面等式。3、有向图的矩阵表示啊烤刀献瘫调霓霹缅哲蜒翼蛛荡寓率恭谣砧浅赵左痴惯羌训涯挝嫡纠持梳图论课件--有向图图论课件--有向图8E={e1,e2,…,em}(1)称A(D)=(aij)n×n是D的邻接矩阵,其中aij是vi为始点,vj为终点的边的条数,1≦i≦n,1≦j≦n。定义6设D=(V,E)是有向图,其中V={v1,v2,…,vn}(2)若D无环。称矩阵M=(mij)n×m是D的关联矩阵,其中题松闲颁剁撕霹推磐绍贩丘济幽扛疵约钙翼咬滑博讼沾腰馅闸奈仇等溶仅图论课件--有向图图论课件--有向图9例1写出下面有向图D1的邻接阵和D2的关联阵。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D2煽扛屠佩钦茎缎俄棱湃孪荔箱虎怂螺****谅粹滦力芭侍钾司蚌出廉韵拢毖碑图论课件--有向图图论课件--有向图10