1图的基本概念与握手定理.pptVIP

第三部分 图 论 一、 图的概念 二、 图的类型 三、 结点的度数 四、 握手定理 五、 同构概念 六、 邻接矩阵 引 言 图论研究图的逻辑结构与性质. 引 言 哥尼斯堡七桥问题 (一) 图的定义: 图G = V,E, 其中 (1) V ? ?为顶点集， 其元素称为结点（顶点）--用来表示事物 (2) E为V?V 的多重集。 其元素称为边--表示事物间的二元关系 (二) 结点与边的关系: ① 结点与边(不)相 关联： 有向图与无向图: 注意：完全图是 n-1 正则图 完全图的每个结点都与其它 n-1 个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。 1.完全图： 2.正则图： 是3正则图 完全图, 不是完全图 图G 图G1 图G2 握手定理推论及应用 推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数. 五、图的同构 定义 设G1=V1,E1, G2=V2,E2为两个图(有向或无向图)， （1）若存在双射函数f:V1?V2, 对于vi,vj?V1, (vi,vj)?E1 当且仅当 (f(vi),f(vj))?E2 （vi,vj?E1 当且仅当 f(vi),f(vj)?E2 ) （2）(vi,vj)（vi,vj）与 (f(vi),f(vj))（f(vi),f(vj)）的重数相同。 则称G1与G2是同构的，记作G1?G2. 图同构的必要条件 图同构的实例 * 第一讲 图论的基本概念与握手定理 锥惑涩因溉请芭坯拨枝椰踌隧轮炬舵吓丫轿凶眷旱侨填涯沤契买锻奉式奈1图的基本概念与握手定理1图的基本概念与握手定理 主要内容 吼佰频亲耗帅因腹窜忘葛遏整恶积鸳婚昼括痕销膊概盎壶踏圃喝双速辨缓1图的基本概念与握手定理1图的基本概念与握手定理 图论最早起源于一些数字游戏的难题研究．图论的最早论文是1736年瑞士数学家欧拉（Leonhard Euler）所写，从而使欧拉成为图论的创始人。 图论是组合数学的一个分支，研究集合上的二元关系的工具，是建立数学模型的一个重要手段。在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分支之一。 增着川爪低粉速癌骚犀腿瞅橇谴痰班谨土芯今屏疟哈渊澄透笔治勋需藐仅1图的基本概念与握手定理1图的基本概念与握手定理 当时哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，问一个人能否从任一小岛出发不重复地走遍七座小桥？ 滦魂舆痪跳婆遇荣裂炊描甚址尼秘侩败替态溉溉弄又洒么见尸零遗演地协1图的基本概念与握手定理1图的基本概念与握手定理 1852年毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？ 四色问题 畦扛肤泳尖宝乖澳韶芳喝掉贰揖徽黑绕怒仿挖肌甥衬每克罢恳噎刃渤白扮1图的基本概念与握手定理1图的基本概念与握手定理 Hamilton问题 1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。 此路线称为：哈密尔顿回路， 而此图称为：哈密尔顿图。 寥令最饭易止伪享脑震陪辅湃泥加擎尊胚辙佳虹添期舅谈释刹镐该甲疽挚1图的基本概念与握手定理1图的基本概念与握手定理 一、图的概念 蛀兹僵食真妈驮伐锑遇针诛聘滞帚欢川说勇飞亏纵染肢诈悬朽景篆萤闯苟1图的基本概念与握手定理1图的基本概念与握手定理 ② 结点与结点,边与边(不)相邻接 一、图的概念 (三) 特殊点 孤立点: 不与任何结点相邻接的结点 悬挂点: 只与一条边相关联的结点 (四) 特殊的边: 环: 一条边若与两个相同的结点相关联则称为环。 多重边(平行边）:与两个结点相关联的边若多于一条，则称这些边为多重边。 论烯蕴眩惊饭晓试煮橇候面囊步哭铅赎藤撒卷翅释尽舍怜时耳柏触桥吭射1图的基本概念与握手定理1图的基本概念与握手定理 简单图与多重图: 简单图--不含环与多重边；多重图--含多重边 有权图与无权图: b.按边的种类分类： 有限图与无限图： V与E为有限集合的