27.图的基本概念.ppt

计算机数学 例1： （1）（3，3，2，3，4）能称为图的度数列吗？为什么？ （2）已知图G中有11条边，1个4度顶点，4个3度顶点，其余顶点的度数均不大于2，问G中至少有几个顶点？ （3）（3，3，2，3，5）能称为图的度数列吗？为什么？如果能够图化，能简单图化吗？ 解 （1）（3，3，2，3，4）不能称为图的度数序列，因为其中奇数度的顶点个数为奇数，不满足握手定理。 （2）由握手引理，G中的各顶点度之和为22，1个4度顶点，4个3度顶点共占去16度，还剩6度，若其余顶点全是2度点，还需要3个顶点，所以G至少有1+4+3=8个顶点。 （3）（3，3，2，3，5）满足握手定理，因此能图化。在此图中，有5个顶点，并且顶点的最大度为5，因此不是简单图，即该度数列不能简单图化。 【练习】 求解下列各题: （1）无向完全图Kn有28条边，则它的顶点数n为多少？ （2）图G的度数列为2，2，3，5，6，则边数m为多少? （3）图G有12条边，度数为3的顶点有6个，余者度数均小于3，问G至少有几个顶点？ 可简单图化 定理： 设非负整数列 d=(d1,d2,…,dn) 且 (n-1)?d1 ? d2 ? …? dn ?0，则d是可简单图化的充分必要条件是 d?=(d2-1,d3-1,dd1+1-1,dd1+2,…,dn) 可简单图化的。 例1 判断下面两个非负整数列是否可简单图化？ (1) (5, 5, 4, 4, 2, 2); (2) (4, 4, 3, 3, 2, 2)。 上例（2）的简单图。 图7.1.7给出了图G 以及它的真子图G1和生成子图G2。 例2: 在下图中，（b）是（a）的 子图、真子图、生成子图. 同构满足条件: 由定义可知，两个图 G1=V1，E1和 G2=V2，E2是同构的，必须满足以下条件： (1)节点数目相等； (2)边数相等； (3) 度数相同的节点数目相等。 以上3个条件是判断2个图是否同构的必要条 件，而不是充分条件。 判断2个图是否同构，到目前为止，只能根据定义来判断，还没有充分判别法。 教师：田检 图 7.1.1哥尼斯堡七桥问题 图论起源于哥尼斯堡（彼德堡）普雷格尔河上的七桥问题。1736年数学家欧拉发表论文解决这个问题。从而奠定图论的基础。 图 7.1.2 在许多数学家的努力下,先后解决了周游世界问题(哈密顿)、棋盘走马问题、迷宫问题和四色猜想问题，使图论得到快速发展。 20世纪40年代，随着计算机科学和管理科学的发展，图论得到广泛的应用。 考虑右图： 我们将结点a、b 的无序结点对记为(a，b）， 有序 结点对记为〈a，b〉。 一个图G可用一个图形来表示称为图解,但一个图的图解不是唯一的。 【例7.1.2】 设G=〈V(G),E(G)〉,其中V(G)={a,b,c,d}， E(G)={e1,e2,e3,e4,e5,e6,e7},e1=(a,b),e2=(a,c),e3=(b,d), e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。则图G可用图7.1.2(a)或(b)表示。 没有边的图（零图）是简单图么？ 思 考 给定任意一个含有n个结点的图G,总可以把它补成一个具有同样结点的完全图,方法是把那些缺少的边添上。 定义7.1.2 设G＝〈V, E〉是一个具有n个结点的简单 图。以V为结点集，以从完全图Kn中删去G的所有边后得到的图（或由G中所有结点和所有能使G成为完全图的添加边组成的图）称为G的补图，记为 。 下图给出了一个图G和G的补图 。 7.1.2 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念——结点的度数。 定义7.1.3 图中结点v所关联的边数(有自回路时计算两次)称为结点v 的度数，记为deg(v)。 如图7.1.3中的deg（v1）＝2，deg（v2）＝3， deg（v3）＝5。 图中所有顶点的度数之和与边的条数有什么关系？ 握 手 定 理 定义7.1.4 在有向图中,射入结点v的边数称为结 点v 的入度， 记为 ;由结点v射出的边数称为 结点v 的出度， 记为 。 结点v的入度与出度之和就是结点v的度数deg(v)。 如图: ＝1， ＝2。 定理 7.1.2 在任何有向图G＝〈V ,E〉中， 有 讨 论 题 ⑴ 1，2，3，4，5； ⑵ 2，2，2，2，2； ⑶ 4，3，3，2，2； ⑷ 2，3，2，3，2； ⑸ 3，3，3，3，2. 解 (1) (5, 5, 4