图论课件--有向图.ppt

1、1，图论及其应用，应用数学学院，2，牙齿课的主要内容，(1)，乳香的概念和性质，(2)，乳香的连接性，乳香的连接性，(3)，图的方向问题，(4)，其中V如果e是D的边，u和v是创建D(u，v)=e的顶点，则e从u连接到v，被记录为e=。u是名为e的弧尾(起点)，v是e的弧头(终点)。(a)，乳香度的概念和性质，请注意：乳香度可以简单地解释为“有方向的图”。4，例如，v3和v2分别是E1的起点和终点。在定义的双向地物d中，具有相同起点和终点的边称为平行边。两点之间平行边的条数称为两点之间的重量数。例如，在上图中，E6和E7是平行边。5，定义3方向图D中，如果没有环和平行边，则牙齿图称为简单方向图

2、。定义4集D是去除D的边方向后得到的无向图G，D的基准图，称为方向图。(David aser，Northern Exposure(美国电视电视剧)，定义)另外，如果G是无向图，那么G的每个角加上方向后得到的方向图D称为G的方向图。e3，6，定义5集D是方向图，V是D的顶点。以v开头的边的条数称为点v的出图，以v结尾的自环1度。点v的出图以d (v)记录。以v结尾的边的栏数称为点v的入口度，以v结尾的自环1度。点v的粒度以d-(v)记录。点v的度和粒度的总和称为点v的度，并被记录为d(v)。7，例1简单的图表有多少方向图？a:因为每条边都有两个茄子方向方法，所以总方向为2 m(G)。示例2证明：

3、G有方向也有D，示例，证明：不丢失一般性，将G设置为连接性。g中的奇数顶点数必须是偶数，将偶数个奇数顶点配对，然后在每对成对顶点之间连接边，以获得Euler G1。从G1旋转C到Fluery算法G的欧拉，沿C上标的顺序，C的方向也得到C1。从C1中删除添加的边后，G的方向也得到D。显然：8，4，是，2，性质，定理1设置D=(V，E)是直接图的情况下：证明：出图，3，直接图的矩阵表示法，9，E=e其中V=v1、v2、vn、(2) d是非回路。矩阵M=(mij)nm是D的关联矩阵。其中，10，示例1记录与图D1相邻的数组和D2的关联数组。11，1，相关概念，(2)，直接图的连接性，(1)直接路径(

4、闭合路径)，跟踪(闭合路径)和公路(圆)类似于无方向图的相关概念。(2)直接图形顶点之间的连接，定义7 D=(V，E)是直接图形，U和V是D的两个顶点。1) d具有(u，v)条道路时，u可以到达v，并被记录为uv。如果法规u u .2) d具有(u，v)或(v，u)道路，则u和v是单向连接的。12，3) D具有(U，V)道路和(V，U)道路时，U和V是双向连接或刚性连接。定义8设置D=(V，E)是直接图形。1) d的基本度连接时，d称为弱连接度。2)如果D的两个点是单向连接，则D称为单向连接。3) D的任意两点双向连接时，D称为强连接图。13，在上图中，D1是强连接，D2是单向连接，D3只是弱连接。对于强连通图，我们得出了以下结论：清理1:有向图D=(V，E)仅在存在包含D中所有顶点的循环时才强连接。证明：“需要”，设置v (d)=v1，v2，vn。d是强大的连接图，因此对于任意两点vi和VJ，(vi，VJ)道路和(VJ，VI)道路都存在。因此，有以下闭合路径：v1v2