图 论（Graph Theory）第一、二章.pptVIP

图 论(Graph Theory) 计算系统生物学教研室 基础医学院三楼表观遗传研究组 复杂网络例子国际互联网 电信网络 美国航空图 生物网络 第一章 图 1.1 图的概念 1.2 子图 1.3 顶点的度 1.4 道路与连通性 1.5 图的运算 什么是图? §1.1图的概念 图 简单图 完全图 补图 同构 一、引例哥尼斯堡七桥问题 ??Leonhard Euler(1707~1783): 人类有史以来最多产的数学家; 1736年,“七桥问题”,图论和拓扑学诞生 1.七桥问题 18世纪的欧洲，有一位伟大的数学家，全欧洲的科学家都以他为师表，都称自己是他的学生，他就是大数学家欧拉。 1736年，为欧拉在彼得堡担任教授时，他解决了一个有趣的“七桥问题”，这个趣题一直流传到现在，并相信它是拓朴学产生的萌芽。 当时与普鲁士首府哥尼斯堡有一条普雷格尔河，这条河有两个支流，还有一个河心岛，共有七座桥把两岸和岛连起来。 有一天，人们教学的时候，有人提出一个问题：“如果每座桥走一次且只走一次，又回到原来地点，应该怎么走？”当时没有一个人能找到答案。 这个问题传到住在彼得堡的欧拉耳中， 环游世界问题 二、二元关系 有序对：两个具体事物按照一定的次序排列，a在前，b在后，记为＜a,b＞，则称＜a,b＞为一个有序对． 有序积：设Ａ和Ｂ是两个集合，由a属于Ａ,b属于Ｂ组成的形如＜a,b＞的所有有序对构成的集合，称为Ａ和Ｂ的笛卡尔积(cartesian product)，或有序积． 二、二元关系 二元关系：有序积Ａ×Ｂ的一个子集合，称为Ａ到Ｂ上的一个二元关系(binary relation)． 当A=B时，集合A到集合B的二元关系称为集合A上的二元关系。 无序对：组成偶对的两个事物a和b与次序无关，则称这种偶对为无序对。用符号(a,b)表示。 无序积：设Ａ，Ｂ为两个集合，由a属于Ａ,b属于Ｂ组成的无序对构成的集合，称为Ａ和Ｂ的无序积，记作ADB。 无序积ADB的一个子集，称为A和B的一个二元关系。当A=B时，A和B的二元关系称为A上的二元关系。 三、图的定义 图：一个图Ｇ定义为一个偶对（Ｖ，Ｅ），记作Ｇ＝ （Ｖ，Ｅ），其中 　（１）Ｖ是一个集合，其中的元素称为顶点； 　（２）Ｅ是无序积ＶDＶ中的一个子集合，其元素称为边，其中的元素可在Ｅ中出现不止一次． 如果一个图有p个顶点和q条边称为(p.q)图，如果p个顶点标以不同的名称称为标定的， 否则称为非标定的。通常用p表示阶数，q表示边数 同构的必要条件： 两个图有相同的顶点或相同的边数。 同构是一个等价关系。 所有图的集合，按照同构关系可以划分等价类，每一个等价类称为一个非标定图。 为了区别非标定图，本节开始定义的图为标定图，给每个顶点和边赋予标记的目的是便于称呼。 1.2 子 图 4.导出子图：设V’是图G=（V，E）的顶点集的一个非空子集，以V’ 作为顶点集，以两个端点均在V’ 中的边的全体为边集的子图，称为由V’ 导出的G的子图，记为G[V’ ]，我们称G[V’ ]是G的导出子图（induced subgraph）. 导出子图G[V/V’],记为G-V’，它是从G中去掉V’中的顶点以及与这些顶点相关联的边所得到的子图。 5.主子图：设V’ ={v}，则把从G中去掉顶点v以及与这个点相关联的边所得到的子图记为G-{v}，简记为G-v，称为主子图。 6.边导出子图：设E’是图G=（V，E）的边集E（G）的非空子集，以E’中边的全部顶点为顶点集组成的子图称为边导出子图。 在边集E(G)中去除子集E’的全部边得到的G的生成子图，记作G-E’（如果删除的边仅是一条则该边的两个顶点仍然保留）。 如果在G上增加一个边集所得的图为G+E’。 如果E’={e}，则分别用G+e和G-e代替G+{e}和G-{e} 1.3顶点的度 问题1：空间中是否存在这样的多面体，它们有奇数个面，而每个面又有奇数条边？ 问题2：晚会上大家握手联欢，是否出现过握手奇数次的为人为奇数的情况？ 1.4 道路与连通性 在1763年，欧拉发表了一篇论文解决了著名的七桥问题，开始了图论的研究阶段。 一个图最重要的性质之一是连通性的问题。 如果途径的起点和终点相同称为闭的，否则称为开的。 途径m中的子序列（前后相连）为m的（ vi, vj）节（section）。 一条道路通过点（除起点和终点）成为内点。 圈的长度成为圈的阶，一个长为K的圈称为K阶圈。 二、连通性 连通性 如果图G是从V0到Vg的一条道路，那么这条道路上的每个内点都是度为偶数的顶点。因为对Vi来说，有一条进入的边，就有一条出来的边，而且进出的边不能重复走过的边，所以与内点Vi相邻的边都是成对的。因此G最多有两个顶点时奇顶点，即V