图论 离散数学.ppt

5、握手定理（欧拉） 1)设G＝V,E为任意无向图,V＝{v1，v2，…，vn},｜E｜ = m， 则 ∑d(vi) ＝ 2 m (所有结点的度数值和为边数的2倍) 2)设D＝V,E为任意有向图,V＝{v1，v2，…，vn},|E| = m ， 则 ∑d+(vi) ＝ ∑ d-(vi) = m． 且∑d(vi)＝2 m 3) 推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数 4) 结点的度数序列 (1) 设G＝V，E为一个n阶无向图，V＝{v1，v2，…，vn} 称d(v1)，d(v2)， …，d(vn) 为G的度数列 条件：奇度数的结点个数应该是偶数个 （2）序列的可图化： d=(d1,d2,…dn) 对一个整数序列d,若存在以n个顶点的n阶无向图G，有d(vi)=di 称该序列是可图化的 （3）设非负整数列d＝(d1，d2，…，dn)则d是可图化的当且仅当 ∑di = 0 (mod 2) (序列之和必须是偶数) （4）结论：n个结点的简单图中结点的最大度数（△（G)）应小于等于n-1 6、图的同构 定义:两个图的各结点之间，如果存在着一一对应关系f 这种对应关系又保持了结点间的邻接关系，那么这两个图就是同构的 在有向图的情况下，f不但应该保持结点间的邻接关系，还应该保持边的方向 注：1) 互为同构的两个图（必要条件） 有相同样的阶数（结点）和同样数量的边数及顶点的度数序列 2)图之间的同构关系可看成全体图集合上的二元关系 同构的图为一个等价类，在同构的意义之下都可以看成是一个图。 画出4阶3条边的所有非同构的无向简单图 主要掌握：给出边集E，能表示出图 简单图的判断 握手定理的应用 习题类型： 习题十四 3、5、8 7、完全图定义 设G为n阶无向简单图，若G中每个顶点均与其余的n—1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n≥1)． 设D为n阶有向简单图，若D中每个顶点都邻接到其余的n—1个顶点，又邻接于其余的n—1个顶点，则称D是n阶有向完全图． 完全图的性质： n阶无向完全图G的边数与结点的关系 m = n (n-1)/2 n阶有向完全图G的边数与结点的关系 m = n (n-1) 8、通路：首尾相接的边的序列L称为通路 2、序列中首尾结点相同，则称L为回路 3、通路的表示：边的集合表示 可仅用通路中的边序列表示：e1e2…ek 也可仅用通路中所经过的结点的序列表示：v1v2v4v1v3 4、边序列中的各条边全都是互不相同的通路，称为简单通路 5、序列中的每一个结点仅出现一次的通路，称为初级通路 6、序列中首尾结点相同，则称通路为初级回路或圈。 7、序列中边的条数称为它的长度 8、关系：有向图中的每一条初级通路，也都必定是简单通路。 反之不成立 9、在n阶图D中，若从顶点vi到vj存在简单通路，则vi到vj一定存在长度小于或等于n—1的初级通路 10、在一个n阶图D中，若存在vi到自身的简单回路，则一定存在vi到自身长度小于或等于n的初级回路（圈） 掌握：初级通路与简单通路的判断，及其关系 9、图的连通性 1）无向图的连通性 结点的连通： 设无向图G＝V，E，? u,v ∈V，若u，v之间存在通路则称u,v是连通的记作u～v，? u ∈V，规定u～u 结点的连通关系是等价关系 若定义：～ ＝{u，v ┃u，v∈V且 u与v之间有通路} 此关系是自反，对称的，传递的，因而～是V上的等价关系 2）无向图的连通图 若无向图G中任何两个顶点都是连通的，则称G为连通图， 否则称G为非连通图或分离图（各子图为连通分支- 等价类） 3）结点之间的距离 设u，v为无向图G中任意两个顶点,若u～v，称u，v之间长度最短的通路为u，v之间的短程线 短程线的长度称为u，v之间的距离，记作 d(u，v) 当u，v不连通时，规定d(u，v)＝ ∞ 4）有向图的连通性 1、结点的可达性：设D＝V，E为一个有向图． ? vi,vj ∈V，若从vi到vj存在通路,则称vi可达vj, 记作vi → vj 。 规定vi总是可达自身的，即vi → vi． 2、结点的相互可达 若vi → vj 且vj → vi 则称vi与vj是相互可达的， 记作: vi ? vj (规定vi ? vi) 3、 结点的可达关系可为V上的二