【免费】2019秋图论期末考试1资源-CSDN文库

需积分: 0 52 浏览量 2022-08-03 20:37:22 上传评论收藏 259KB PDF 举报

资源详情

资源评论

资源推荐

2019秋图论期末考试

Author：中山大学 17数据科学与计算机学院 YSY

https://github.com/ysyisyourbrother

一、简答

1. v顶点的树最大叶和最小叶分别为？结构为？

2. V顶点的图最大点连通度和边连通度为？结构为？

3. 偶数点的Hamilton图有完美对集？

二、举反例子

1. 三正则图都为平面图

2. 对每一个k色图G，都有一个正常k着色满足其中a(G)个点同色，a(G)为最大独立集点个数

三、证明

1. 一定有一种所有顶点入度=出度的竞赛图结构，当且仅当顶点数为奇数

2. 9个人或者4个互相认识或者3个互相不认识

3. 正则图有割点，证明最小正常边着色数大于最大点度数

4. 平面图G不存在围长3的圈，证明E < 2V - 4

四、算法

1. 最小生成树

2. 流标号法+最小割

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

评论0

内容反馈

KerstinTongxi

粉丝: 21
资源: 277

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip