离散数学10图的基本概念.ppt

第10章 图的基本概念 如何找到物流运输的最优路径？ 如何找到最优的网络通信线路？ 如果你想周游全国所有城市，如何设计旅游线路？ 化学化合物分析：结构是否相同？ 程序结构度量：程序是否结构相似？ 如何为考试分配教室，使得资源利用率最优？ 如何安排工作流程而达到最高效率？ 如何设计为众多的电视台频道分配最优方案？ 如何设计通信编码以提高信息传输效率？ 操作系统中,如何调度进程而使得系统效率最优？ 如何设计集成电路线路布局而达到最优效率？ 如何设计计算机鼓轮？ 七枚同重量硬币与一枚较轻的伪币，使用天平秤多少次就能找出伪币？ 如何设计下棋程序？ n-皇后问题 最少用几种颜色就能将世界地图都着色？ 如何使箱子尽可能装满物体？ 一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢？ 研究主题 旅行商问题：TSP问题 中国邮路问题 地图着色问题：四色定理 最短路径问题 网络流 匹配 组合计数 主要内容 1) 图的基本术语； 2) 结点的度，子图，完全图； 3) 图的连通性； 4) 图的运算，图的矩阵表示及其性质； 5) 图的同构； 6) 欧拉图与哈密尔顿图的性质及其应用。 10.1 图论概述 图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。图论是有许多应用的古老学科，也一直以来都是一个热门学科，它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。 10.2 图与图模型 例10.2 某学校共有10名教师，他们分别参加7个班级的讨论课，每个班级可能同时需要多位教师参加，有的教师可能需要参加多个班级的讨论，每个班级必须单独开展讨论课，则如何安排才使得所有班级在最短时间段内完成讨论课？讨论课的情况如下（Vi为班级编号，数字1-10为教师编号）： 10.2 图与图模型 10.2 图与图模型 定义10.1 图G=(V,E)包括两个集合： 结点集V(G) ：非空的对象的集合,V={v1,v2,…,vn} ； 边集E(G) ：有限的两个对象构成的V的无序对构成的集合。E={e1,e2,…,em}; 其中，每一条边都是集合V的二元子集，如边ei={u，v}，常常简记为uv或vu，其中u、v称为边uv的端点。 10.2 图与图模型 10.2 图与图模型 节点集合V(G)的基数n表示图G的阶，边集合E(G)的基数m表示图G的规模，有时也将图G记作(n,m)。 在图G中，若边集E(G)=Ф,则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图（Trivial graph）。 N7 10.2 图与图模型 结点集为空集的图为空图（Empty Graph），并将空图记为?。 阶为有限的图称为有限图(Finite Graph)，否则称为无限图(Infinite Graph)。 10.2 图与图模型:无向图 10.2 图与图模型 如果图中存在某两条边的端点都相同，则称该图为多重图(Multigraph)，该两条边称为平行边。如果一条边关联的两个结点是相同的结点，则称该边为圈或自环(Loop)。不存在平行边与圈的图即称为简单图(Simple Graph)。 10.2 图与图模型 定义10.2 如果uv是图G的边，记为e，即uv?E(G),则称结点u和v邻接(Adjacent), 否则称结点u与v非邻接。 与同一个结点关联的两条边称为邻接边。 与结点v关联的边数称为结点v的度，记作deg(v)。与结点v关联的环对v的度数的贡献要计算两次。 如果结点v的度为0，则称之为孤立点(Isolated Vertex)。 一度的结点称为悬挂点（Pendant Vertex）。 图G的所有结点度数的最小度数称为G的最小度，记作?(G)， 而所有结点度数的最大者称为G的最大度，记作?(G)。 各结点的度均相同的图称为正则图（Regular Graph）。各结点度均为k的正则图称为k-正则图。 10.2 图与图模型 定义10.3 如果图的每条边是二结点构成的有序对，则该图称为有向图(Directed Graph)，上文所定义的图都是无向图(Undirected Graph)。有向图中边uv与vu是两条不同的边，对于边uv，称u为始点，v为终点。 有向图中，结点v的度分为入度，即与该结点相关联并以该结点为终点的边的数目，以及出度,即与该结点相关联并以该结点为始点的边的数目,分别记作deg+