目录
石墨笔记 PPT版
https://shimo.im/docs/TPjwqXqPr8PCRWdD
1 二部图 偶图 双图 二分图 Ks,t G(V1,V2,E)
2 欧拉图
哥尼斯堡问题,一笔画完问题
无向欧拉回路,连通图且无奇度顶点
无向欧拉通路,连通图恰有两个奇度顶点,在有两个奇度顶点的连通图中,每条欧拉通路都以这两个奇度顶点为端点. 例子:矩形加一条对角线
有向欧拉回路:连通且所以顶点入度＝出度
有向欧拉通路:连通且两个奇度顶点,一个入度+1=出度,另一个出度+1=入度
若存在入度比出度大2,或出度比入度大2的顶点,肯定没有欧拉通路,更不是欧拉图
3 哈密顿图
4 平面图
欧拉公式
推论: n-m+r = k+1
G是具有k(k>=2)个连通分支的平面图
m <=3n-6是平面图的必要条件
不满足m <=3n-6是非平面图
m <= ((k-2)/k )*(n-2)是平面图的必要条件
库拉图斯基定理:
1 一个图是平面图当且仅当它不含与k5同胚的子图,也不含与K3,3同胚的子图
2 一个图是平面图当且仅当它没有可以收缩到与k5同±胚的子图,也没有可以收缩到K3,3同胚的子图
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/231080.html原文链接：https://javaforall.net
