【5-图论】1.图的定义【学生版】

发布时间:2021-06-18 15:00:26

讲义编号: 学员: 讲师: 课程类型 数学 “图的定义” 年级: 授课方式(在线或线下): 授课日期: (线下填)授课教学点: 知识定位 图论是组合数学中一个重要分支,*年来图论问题在高等级的比赛中常常出现。图论问题一般通俗易懂,所需 知识不多,却极为机敏灵活,很适合作为竞赛考题。 知识梳理 我们常说的下面这个导致图论诞生的问题将启示我们给出图的基本定义。 例 1 (哥尼斯堡(Konigsberg)桥问题)哥尼斯堡城坐落于普鲁士的普莱格尔河畔。城区包括 Kneiphopf 岛和 河的两岸区域。这四个地区通过下图所示的 7 座桥连接。市民们想知道如果他们从家出发,经过每一座桥恰好 一次,是否又能返回家。这个问题被简化为遍历右侧的阁。图中的黑点表示陆地,曲线表示桥。 基本定义 一个图 G 是一个三元组,这个三元组包含一个顶点集 V(G)、一个边集 E(G)和一个关系。该关系使得每 一条边和两个顶点(不一定是不同的点)相关联,并将这两个顶点称为这条边的端点。图 G 所含的顶点个数 n 叫做图 G 的阶。一个环是一条边,它的两个端点是相同的。重边是具有同一对端点的多条边。一个简单图是不 含环和重边的图。我们用点的集合和边的集合来确定一个简单图,边的集合被表示为一组无序点对的集合。当 1 u 和 v 是一条边的两个端点时,那么它们是相邻的且互为邻居。在一个简单图里我们把一条边视为一个无序点 对并且忽略边和端点间的关联关系。 一条道路是一个简单图,其顶点可以排序使得两个顶点是相邻的当且仅当它们在顶点的序列中是前后相继 的。 一个圈是一个顶点数和边数相等的回路,其顶点可以放置于一个圆周上使得两个顶点是相邻的当且仅当 它们在圆周上相继出现。 图 G 的子图是一个图 H 。 它满足 V(H)包含于 V(G),E(H)包含于 E(G),且 H 中边的顶点的分配和 G 中的一样。 如果 G 中的每一对顶点都属于某一条路径,图 G 是连通的 z。否则。称 G 是非连通的。 设 G 是一个图,v 是图 G 的一个顶点,图 G 中所有和 v 相邻的顶点集合记作 N(v),它叫做顶点 v 的邻域。 所有以 v 为一端点的边数叫做顶点 v 的度,记作 d(v)。 例 2 18 个队进行比赛,在每一轮比赛中,每个队与另一个队比赛一场,并且在以后的各轮中这两个队不再比 赛。现在比赛进入第 9 轮,证明:在前 8 轮比赛中,一定有三个队,彼此之间尚未赛过。 例 3 有一个团体,由 1982 个人组成,其中任意四个人中都至少有一个人认识其他三个人。问该团体中认识其 他所有的人的成员最少有多少? 例 4 在一车厢里,任何 m(m≥3)个旅客都有唯一的公共朋友(当甲是乙的朋友时,乙也是甲的朋友。任何 人不作为他自己的朋友)。问:在这车厢里,有多少人? 例 5 在 20 个城市之间开辟 172 条航线(每两个城市之间至多 1 条航线)。试证明利用这些航 线,可以由其中任何一个城市飞往其他的任一个城市(包括经过若干次中转后到达)。 2 例 6 某省任一城市至多与三个城市有铁路直接相连。从任一城市到其他城市中间至多经过一个城市。问:该省 至多有几个城市? 例 7 6 个城市问有一个铁路网,使得任意两个城市之间均有直通的铁路。而在星期天的时候,一些铁路将关闭 起来以便修整。现铁路部门规定:关闭若干段铁路之后,必须保证仍可通过铁路往返于任意两个城市之间 (未必直达)。问:有多少种不同的铁路修整方式满足铁路部门的要求? 例 8 图 G 有 n 个顶点,q 条边,并将边标以数 1,2,…,q。证明:一定存在一个顶点,从这点出发,可以按标 号从小到大的顺序走过 边。 试题演练 1. n 人聚会,n>3,其中至少有一人没有和其他所有的人握手。聚会中可能和每个人都握手的人数最大之最大值是 多少? 3 2. 某公司有 17 个人,其中每个人都恰认识 4 个人。求证:必有 2 个人互不相识,而且没有共同的熟人。 3. 2n 个人聚会,其中每个人至少认识其中的 n 个人。证明:存在 4 个人,可以让他们围圆桌坐下,使得每个人与 邻座的人认识。 4. *面上有 n 个点,其中任意三点不共线。对其中任意一个点,这 n 个点中至少有 k 个点到它的距离相等。证明: k≥1/2+(2n)1/2。 5. n(n≥5)个城市,每两个城市之间有一条直达道路。证明可将这些道路改为单行道,使得从任意城市可以到 达任一其他城市,中间至多经过一个城市。 6. 设 G 是有 n 条边的连通图。证明可以将边标上 1,2,…,n,使得自一点引出几条边时,各边标号的最大公因 数为 1。 4 讲师评价 知识点 课后掌握情况 所需*题编号 是否需要课时加强 课后掌握情况评分: 1 对本知识点毫无所知,闻所未闻。 2 了解该知识点,能完成简单的识记题。 3 理解该知识点,能运用其分析解答简单问题。 4 把握知识的意义,但缺乏练*与手感,解答稍难的题目速度慢。 5 深刻了解知识内核,能完成相应试题,但有一定的错误率。 6 能够较熟练利用该知识点解决相关试题,但题目稍加变形就难以入手。 7 熟悉该知识点各要素,能顺利解答该知识点范围内各种题目的变形。 8 能把该知识点与其他知识相关联,解答高考中的压轴题。 9 懂得出题规律,只对该知识点范围的难题有兴趣! 10 已拿下该知识点,拥有金钟罩,刀枪不入。 5

相关文档

  • 图论-图的基本概念
  • 第7章 图论-1图的基本概念
  • 实验5:图论的基本概念2008[1].4.28
  • (图论)图的基本概念--第一章分析
  • 图论课件第一章 图的基本概念
  • 图论 4-1图概念
  • 图论讲义第1章-图的概念
  • 5图论-图基本概念10-13
  • 第七章 图论第一节. 图的基本概念定义7-1.1 一个图是一汇总
  • 图论 第一章 图的基本概念(4)
  • 猜你喜欢

  • 郑州生耀商贸有限公司企业信用报告-天眼查
  • 小学作文可爱的小狗
  • 厨房美食菜谱:葡式蛋挞的做法_3
  • 以开学为话题的作文800字
  • 【参考文档】水泥企业优质服务承诺书-精选word文档 (3页)
  • 2019-2020年高三政治上学期第一次模拟考试试题
  • 施工与安全技术交底安全油漆工
  • IPv6 标准的制定及在我国发展动态的分析
  • 厨房美食菜谱:轻乳酪蛋糕的做法_0
  • 初三叙事作文:门其实开着10
  • 云南省中考复*历史(人教版)第1部分教材知识梳理(中国现代史)课件:第六、七单元 经济和社会生活的变
  • 深圳市安远欣贸易有限公司企业信用报告-天眼查
  • 2016年安全月手抄报大全
  • 卓越领导力与高效执行力6H海航讲义ppt课件92页
  • 探究式教学在初中道德与法治课中的策略探讨
  • 2015至2016年下学期六年级语文教学工作总结
  • 2010年广东省高考试题(理综生物)解析版
  • 政府带给我们美好的生活_高一作文
  • 浅谈 JAVA中静态初始化块和非静态初始化块的区别
  • 郑州新郑国际机场扩建空管工程设计项目
  • 武汉寰鼎股权投资基金管理有限公司(企业信用报告)- 天眼查
  • 北京大学2011年招收地区高中毕业生本科招生专业一
  • 天津大学精密仪器及机械专业考研
  • 汤姆索亚历险记的相关读书笔记
  • 单县鲁权净化粉条有限公司企业信用报告-天眼查
  • 描写森林公园的句子
  • 使用微波炉加热鸡蛋爆了炉内很脏如何清洗
  • 2010广东省最新公开选拔镇副科级领导干部必过技巧
  • 小学语文阅读教学中怎样培养学生的创新思维能力
  • 苏州途龙商贸有限公司(企业信用报告)- 天眼查
  • 鸡蛋蛋生
  • 【计算机应用与软件】_系统框架_期刊发文热词逐年推荐_20140724
  • 茂名海龙饲料有限公司市场环境和行业前景研究报告
  • 佛山市明宸达有机硅有限公司(企业信用报告)- 天眼查
  • 13—14歙县上丰学校少年宫信息辅导员工作总结t
  • 2015年下半年吉林省重要数据基础
  • 政法干警考试民法知识:民法概述
  • 通用的教师个人的述职报告
  • 广州美巨生物科技有限公司(企业信用报告)- 天眼查
  • 热门温暖的早安心语短信汇总51句
  • 美国重要指标解读原版
  • 节约粮食的名言大全
  • 电脑版