第1讲 图与论概述 .pptVIP

图与网络技术 四川大学工商管理学院 冯 结 制 教师联系方式 冯结 电话 H） 电子邮箱：fengjieasdfg@126.com 本课程学习要求 1.必备三物： 教材，作业本,课堂笔记. 2.成绩评定： 平时成绩占20% 期中测验占20% 期末考试占60% 引例：七桥问题 一笔画问题： 要求笔不离纸，边不重复 哥尼斯堡七桥问题 什么是图？ ●一个图是由两个集合组成： 顶点集V（非空有限集） 边集E（有限集E ） 每条边对应由两个顶点组成的顶点对。若顶点对是无序的，则称为无向图；若顶点对是有序的，则称为有向图。 若图用G 表示，则它的点集和边集就分别记为V(G)，E(G),该图可以记为G=(V(G)，E(G))。在不致引起混淆的情况下可简记为G=(V，E)。 图的本质？ 图最为本质的内容是一个二元关系. 相关基本概念： 有序对，有序积A×B（笛卡尔积）， 无序对，无序积AB， A到B的二元关系，A和B的二元关系 图，是某顶点集合V和V 上的一个二元关系。 只要一个系统若具有二元关系便可以考虑采用图来建立模型解决实际问题。 几个有趣问题 1. 一次集会上面许多朋友相互握手，那么握手次数为奇数的人的数目一定是偶数。 2. 有2人以上的人群中，总有两人在该人群内恰好有相同的朋友数。 3. 证明：任意6个人中，至少有3人相互认识或者至少有3人相互全都不认识。 节目排序问题 要求（1）每个演员不连续参加2个节目的演出； （2）A和H必须安排在首尾两个节目。 图的作用 图是解决问题的一种工具，是一种重要的数学模型。 图往往能够使问题得到简化，便于处理。 图具有直观性和艺术性。 图论与数学（拓扑学，代数学，组合数学）关系密切，如今，它的许多方法在物理学，化学，通讯科学，计算机技术，运筹学，经济学，生物遗传学，心理学，社会学，人类学，语言学等诸多学科的某些领域都有应用。 图的分类 有向图，无向图 平凡图，非平凡图，空图 连通图，不连通图 平面图，非平面图 赋权图，无权图 一些特殊类型的图 ●完全图：任意一对不同顶都有一条边相连的简单图。 n个顶点的完全图记为Kn 关于树图 若图G是连通并且无圈的简单图，则称G为树。 树的性质：边数= 顶点数 – 1 树是在给定顶点个数的连通简单图中，边数最少的图； 树也是在给定顶点个数的无圈简单图中，边数最多的图； 树一定有悬挂点。 任何连通简单图G都存在为树图的生成子图，称为G的生成树。 最小生成树 定义：在赋权图G的所有生成树中，各边权数之和最小的生成树，称为最小生成树。 例：某市6单位经过A铺设煤气管道问题： 求最小生成树的避圈法 避圈法(Kruskal算法)：将图中所有边按权数从小到大排序，每步从未选的非环边中选择一条权数最小的边，但不能构成圈，直到得到n-1条边为止， n为图的顶点数。 例：避圈法求最小生成树 避圈法求解结果 求最小生成树的破圈法 破圈法：在图中任找一圈，去掉该圈上权数最大的边，直到不再含有圈为止，便得到最小生成树。 例：破圈法求最小生成树 破圈法求解结果 谢 谢！ 再 见！ * 图论与应用 常用u,v,w,…或v1,v2,v3,…来标记图的顶点，用a,b,c,…或e1,e2,e3, …标记图的边。每条边用一条连接该边端点的线表示。画图形时，表示顶点的点的位置和表示边的线的相对位置是无关紧要的，因为一个图的图形仅需画出它的顶点与边之间的关系，所以一个图的图形表示不是唯一的。 例1： V={v1,v2,v3,v4,v5,v6} 和E={e1,e2,e3,e4,e5},其中e1=v1v2, e2=v1v4,e3=v5v6,e4=v1v2,e5=v5v5，则G=(V,E)的图形表示为： 图1 若一条边的端点为同一顶点，则称此边为环。（如图1 中的e5 ） 若E 中两条或两条以上不同边具有相同端点，则称这些边为 重复边．（e1 和e4 ） 无环无重边的图称为简单图，只有一个顶点的图称为平凡图，其余为非平凡图。无边的图称为空图。 一条边的端点称为与此边关联的顶点，反之亦然，与同一条边关联的而个顶点称为相邻的，与同一顶点关联的两条边也称为相邻的． 在图l 中，e1 与v1，v2 关联， v1 与v4 相邻，e1 与e2 相邻。 与顶点