大家好，欢迎来到IT知识分享网。
目录
Complete Bipartite Graphs 完整的二分图
5. Bipartite Graphs and Matchings 二分图和匹配
10. Connectivity 无向图的连通性
1. 图的表示（入门）
图形表示、集合表示
邻接矩阵表示
2. 图的分类
按有无方向分类
undirect graph 无向图
directed graph 有向图
按有无重边（以及环）分类
simple graph 简单图
两个节点之间最多只有一条边
multigraph 多重图
两个节点之间可以有多条边
pseudograph 伪图
存在环
图的分类总结表格
3. 图的术语
degree of a vertex 节点的度数
环要+2！
The Handshaking Theorem 握手定理
4. 特殊的图形
complete graphs 完全图
cycles 环形图
wheels 车轮图
n-Cubes n形立方体图
Bipartite Graphs 二分图
怎么判断一个图是不是二分图？
用两种颜色给节点涂颜色，相邻节点不能涂同一种颜色。涂完之后，相邻节点没有同色的，就是二分图
Complete Bipartite Graphs 完整的二分图
5. Bipartite Graphs and Matchings 二分图和匹配
6. New Graphs from Old
Subgraph 子图
删除或添加图形的边
Edge Contractions 边缘收缩
删除图的节点
Graph Unions 图的结合
7. 图的表示（进阶）
Adjacent List 邻接列表
simple graph 无向简单图
directed graph 有向图
Adjacency Matrix 邻接矩阵
Incidence Matrices 关联矩阵
8. Isomorphism of Graphs 图的同构
证明同构
满足这些条件不一定同构
9. 两个节点间的可达性
通路与回路
通路数量的计算-邻接矩阵
定理的内容和证明
定理的应用
两个节点间可达关系的判断
定理的内容和证明
定理的应用
可达性矩阵
可达性矩阵的简洁求法
两个节点间距离的判定
10. Connectivity 无向图的连通性
Connected Components 连通分支数
点割集与边割集引入
点割集
边割集
Vertex Connectivity 点连通度
Edge Connectivity 边连通度
11. Connectivity 有向图的连通性
强连通图判定的充分必要条件
单向连通图判定的充分必要条件
12. Euler Graph 欧拉图
无向欧拉图的判定定理
有向欧拉图的判定定理
求无向图的欧拉回路
13. Hamilton Graph 哈密顿图
14. 最短路问题
Dijkstra算法
详见此视频【【算法】最短路径查找—Dijkstra算法】 https://www.bilibili.com/video/BV1zz4y1m7Nq/?share_source=copy_web&vd_source=3227c547a8de9a41bb850f
15. Planar Graph 平面图
平面图的定义
能够=我们去尝试，能不能这样画，不是说直接看图去判断
平面图示例
面和边界
Euler‘s formula 欧拉公式
homeomorphic 同胚
收缩
Kuratowski’s Theorem
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/145697.html
