【图论】重庆大学图论与应用课程期末复习资料(私人复习资料)

news/2024/2/29 2:05:40

考试章节范围

在这里插入图片描述
在这里插入图片描述

第一章:1.1、1.2、1.3

填空

  1. 顶点集和边集都有限的图,称为有限图
  2. 只有一个顶点的图,称为平凡图
  3. 边集为空的图,称为空图
  4. 顶点数为n的图,称为n阶图
  5. 连接两个相同顶点的边的条数称为边的重数;重数大于1的边,称为重边
  6. 端点重合为一点的边,称为环
  7. 既无环又无重边的图,称为简单图
  8. 每两个不同的顶点之间都有一条边相连的简单图称为完全图 ,记为 K n K_n Kn n n n为顶点数目在这里插入图片描述
  9. 任何图中,奇次顶点的总数必为偶数
  10. 图同构的必要条件: (1) 顶点数相同(2) 边数相同(3) 关联边数相同的顶点个数相同。
  11. 4个顶点可以组成11个简单图
  12. K 4 K_4 K4分为4个平面
  13. 如果图G的一个子图包含G的所有顶点,称该子图为G的一个生成子图
  14. 图G= (V, E)中所有顶点的度的和等于边数m的2倍(握手定理)在这里插入图片描述
  15. 奇数度的顶点称为奇点,偶数度的顶点称偶点。

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

第二章:2.1、2.4、2.5

填空

  1. 边不重复但顶点可重复的通路,称为道路
  2. 顶点不重复的通路,称为路径
  3. G中任意两点都连通,称为G连通
  4. 起点和重点重合的路径,称为圈
  5. 一条路径所含边的数目,称为这条路径的长度
  6. 一个图是偶图(二部图)当且当它不包含奇圈
  7. 不含圈的图称为无圈图,树是连通的无圈图
  8. 每棵非平凡树至少有两片树叶。
  9. 图G是树当且仅当G中任意两点都被唯一的路连接。
  10. 每个n阶连通图的边数至少为n-1
  11. 任意树T的两个不邻接顶点之间添加一条边后,可以得到唯一圈。
  12. 每个连通图至少包含一棵生成树。

计算

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

第三章:3.1、3.2

填空

  1. 设e是图G的一条边,若ω(G-e)>ω(G), 则称e为G的割边。
  2. e是图G的割边当且仅当e不在G的任何圈中
  3. 设 v 是树的顶点,则 v是G 的割点当且仅当 d(v)>=2

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

第四章:4.1

计算

在这里插入图片描述
在这里插入图片描述
Floyd算法:求任意两点间的最短路.
在这里插入图片描述

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

第五章:5.1、5.2、5.3、5.4

填空

  1. 匹配 M— 如果M是图G的边子集(不含环),且M中的任意两条边没有共同顶点,则称M是G的一个匹配。
  2. 最大匹配 M— 如果M是图G的包含边数最多的匹配,称M是G的一个最大匹配。特别是,若最大匹配饱和了G的所有顶点,称它为G的一个完美匹配(理想匹配)。
  3. M交错路— 如果M是图G的匹配,G中一条由M中的边和非M中的边交错形成的路,称为G中的一条M交错路。特别地,若M交错路的起点与终点是M非饱和点,称这种M交错路为M可扩路(可增长路径)
  4. (贝尔热,1957) G的匹配M是最大匹配,当且仅当G不包含M可扩路
  5. 设M是G的匹配,K是G的覆盖,若|M|=|K|,则M是最大匹配,而K是最小覆盖。
  6. (哥尼,1931) 在偶图中,最大匹配的边数等于最小覆盖的顶点数
  7. (托特定理,1947) 图G有完美匹配当且仅当对V的任意非空真子集S, 有:在这里插入图片描述

计算

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

第六章:6.1、6.2、6.5、6.8、6.9

(TSP两边、迭代)

填空

  1. 设G是H图的充分条件(充分条件) 对于n≧3的简单图G,如果G中有:在这里插入图片描述

  2. 在这里插入图片描述

  3. 在这里插入图片描述

  4. 在这里插入图片描述

  5. 设 G 是非平凡连通图。G 有欧拉道路的充要条件是 G 多只有两个次顶点。

  6. 设G=(V,E)是连通无向图。1、巡回:经过G的每边至少一次的闭通路称为巡回。2、欧拉巡回;经过G的每边正好一次的回称为欧拉巡回。3、欧拉图:存在欧拉的图称为欧拉图E图。4、欧拉道路:经过G的每边正好一次的道路称为欧拉道路。

  7. 设G正好有两个次顶点 u,则沿u到的一条最短路 P(u)加重复边得到 G*,G*的一条欧拉巡回便是 G的最佳巡回。

  8. 经过图G每个顶点正好一次的路径为G的一条哈米尔路径简称H路径。经过G的每个顶点正好一次的圈,称为G的哈米尔顿圈或H圈。含H圈的图称为哈米尔顿图或H图。

计算

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

第七章:7.1、7.2、7.3、7.4、7.5

填空

  1. 设G=(n, m)是平面图,则:在这里插入图片描述

  2. (欧拉公式) 设G=(n, m)是连通平面图,ф是G的面数,则:在这里插入图片描述

  3. 在这里插入图片描述

  4. 设G是平面图G的对偶图,则它们的边数(G)、(G),顶点数(G)、(G)和面数(G)、 (G)之间必满足关系式【G的顶点数等于G的面数;G的边数等于G的边数;G的面数等于G的顶点数;d (v)=deg( f )】**

  5. 平面图G的对偶图必然连通

  6. G是平面图,则 在这里插入图片描述当且仅当G是连通的。

  7. 同构的平面图可以有不同构的对偶图。

  8. 库拉托夫斯基定理:图G是非可平面的,当且仅当它含有K5或K3,3细分的子图

  9. 在这里插入图片描述

  10. 在这里插入图片描述

  11. 在这里插入图片描述

  12. 在这里插入图片描述

计算

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

作业

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

历年真题1

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

历年真题2

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

历年真题3

填空题20分
1.非平凡树至少有多少个一次顶点。
2.K5,6的最小覆盖是几5
3.库拉托夫斯基定理:图G是非可平面的,当且仅当它含有K5或K3,3细分的子图
4.门格尔定理
设x和y是图G中的两个不相邻点,则G中分离x和y的最少点数等于独立的(x, y) 路的最大数目。
设x和y是图G中的两个不同点,则G中分离x和y的最少边数等于边不重的(x, y) 路的最大数目。
5.二部图不含什么

算法题70分
1.用floyd定理求下列4x4的矩阵任意两点间的最短路径和距离
2.有五个游泳运动员X1,X2,X3,X4,X5,有五种游泳方式y1,y2,y3,y4,y5,请问怎么做才能在5x100混合泳接力赛上获得最好的成绩,下面给出这五名运动员的每种泳姿的成绩矩阵,为5x5矩阵。(用最大权值的匹配算法)
3.如下图,即图论P142的图6.39所示的图,求近似最佳H圈,并分析解的近似程度。
4.用可平面性算法证明彼得森图是非平面图。(彼得森图在P161图7.8所示)

证明题10分
1.证明对于简单图G,delta>=2,则有长至少为delta+1的圈
2.证明无向树是二部图


https://www.xjx100.cn/news/3119042.html

相关文章

linux rsync 和scp区别

rsync 和 scp 都是 Linux 中用于文件复制的命令,但它们之间存在一些关键差异: 效率:rsync 在复制文件时,只会复制文件中改变的部分,而 scp 则会复制整个文件,即使文件只有一小部分发生了变化。因此&#xf…

fastadmin 中input 变成搜索变成selectpage

1.column 列中 {field:admin_idss,title:"用户名",addclass:"selectpage",extend:data-source"auth/admin/index" data-field"nickenames"} 列入: table.bootstrapTable({ url: $.fn.bootst…

基于STM32+定时器中断和定时器外部时钟(标准库函数讲解)

前言 本篇博客主要学习了解定时器的标准库函数,以及定时器中断进行LED灯的反转,还有定时器外部时钟获取脉冲计数功能。本篇博客大部分是自己收集和整理,如有侵权请联系我删除。 本篇博客主要是对通用定时器来讲解,功能适中比较常…

分割掩模 VS 掩膜

掩膜 Mask分割掩模 Segmentation Mask总结示例 掩膜 Mask “掩膜” 是指一种用于 标识或遮蔽图像中特定区域 的 图像。 在图像处理中,掩膜通常是一个 二值图像,其中的 像素值为 0 或 1。binary Mask 叫做二元掩膜,如下图所示: 这…

Docker的数据持久化;Docker网络;Dockerfile编写

Docker的数据持久化;Docker网络;Dockerfile编写; 文章目录 Docker的数据持久化;Docker网络;Dockerfile编写;**Docker的数据持久化**1)将本地目录映射到容器里2)数据卷3)将…

【Node.js】笔记整理 3 -npm

写在最前:跟着视频学习只是为了在新手期快速入门。想要学习全面、进阶的知识,需要格外注重实战和官方技术文档,文档建议作为手册使用 系列文章 【Node.js】笔记整理 1 - 基础知识【Node.js】笔记整理 2 - 常用模块【Node.js】笔记整理 3 - n…

Flutter之MQTT使用

1.添加依赖: 首先,需要在Flutter项目的​​pubspec.yaml​​​文件中添加​​mqtt_client​​依赖。 dependencies:#https://pub.dev/packages/mqtt_clientmqtt_client: ^10.0.02.创建MQTT客户端并连接到MQTT服务器:2.创建一个MQTT客户端实例来进行连接和通信 Fu…

NoSql非关系型数据库

前言:Nosql not only sql,意即“不仅仅是sql”,泛指非关系型数据库。这些类型的数据存储不需要固定的模式(当然也有固定的模式),无需多余的操作就可以横向扩展。NoSql数据库中的数据是使用聚合模型来进行处…