离散数学-第5章-3、4.ppt

Chapter 5 graph theory 置换矩阵：相当于将单位矩阵中相应的行与行，或者列与列互换的矩阵。 邻接矩阵中图的性质： (3) B=A2。 (4) 有向图中：C=AAT。 (5) 有向图中：D=ATA。 图的同构-1 判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得：A1＝PA2P。 其中A1，A2分别是G1 ，G2的邻接矩阵。 如何判断两图同构是图论中一个困难问题。 道路和回路 图G=(V,E)的一个顶点与边相交替的序列μ=v0e1v1…vk-1ekvk，且边ei的端点为vi-1和vi (i=1,2,…,k)，则称μ为一条道路(路径path)，又称为v0－vk道路。 若图G中的μ所有边均不相同——简单道路； 若道路μ中v0=vk(即首尾相同)——回路； 若回路μ中没有重复边——简单回路。 顶点v1～v7代表七座城市，有方向的边vivj表示从vi城到vj城的单行车道，问从v1城到v7城有无道路相通？ 如下图所示： 通过观察上图容易得出解答。 如果我们进一步问：若v1城到v7有道路相通，共有几条不同的道路？ 考察邻接矩阵： 现在来看看 的值有什么实际意义。以 为例： 例如 ，我们来看一下它的形成过程： 对图G=(V,E) 而言，若两顶点vi,vj 间存在路径，则称vi,vj 相连通； 无向图G中,若任意两点都连通，则称G为连通图(connected graph) ，否则为非连通图； 非连通图可分解为若干个连通子图(连通分量); 每个连通分量均有极大连通子图。 * * 5.4 Connectivity Connectedness in directed graphs 有向图的连通性 强连通的：若每当a和b都是一个有向图里的顶点时，就有从a到b和从b到a的通路. 弱连通的：若在有向图的底图里，任何两个顶点之间都有通路 由定义可知：任何强连通有向图也是弱连通的。 For example, a b c d a b c d Weakly connected Strongly connected * * 5.4 Connectivity Paths and Isomorphism 通路与同构 Idea: Some other invariants 一些其他的不变量 The number and size of connected components 连通分支的数目及其大小 Path Two graphs are isomorphic only if they have simple circuits of the same length. 两图同构只有当他们具有相同长度的简单回路。 Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree. 应用两图中相应顶点具有相同的度来判断两图的同构情况 We can also use paths to find mapping that are potential isomorphisms. * * 5.4 Connectivity 〖Example 3〗 Are these two graphs isomorphic? Solution: No. Because the right graph contains circuits of length 3, while the left graph does not. * * 5.4 Connectivity Homework: P. 476 18（b,c）, 20 本节内容到此结束 * * v4 v1 v2 v3 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 A ＝ 竖入横出 (2) A=(αij)n×n中，第i列中非0元素的个数等于顶点vi的入度，第i行中非0元素的个数等于顶点vi的出度。(有向图) a11 a12 … a1n a21 a22 … a2n …… an1 an2 … ann B=A2= a11 a12 … a1n a21 a22 … a2n …… an1