Skip to content

Latest commit

 

History

History
65 lines (44 loc) · 2.33 KB

图论.md

File metadata and controls

65 lines (44 loc) · 2.33 KB

基本概念


  • V: vertex set 顶点集
    • V(G)
    • 非空有限集合
  • E: edge set 边集合
    • E(G)
    • 可以是空集
    • 无序偶可重集
    • image.png

顶点一定要用小圆圈或者黑点表示

简单图

  • (1,0)图--孤立点或平凡图
  • (p,0)图(p>=2)--空图或者零图
  • 简单图:没有自环线self loop平行线的图

邻接和度

邻接和度

度的举例

正则图

正则图 彼得森图

p阶k度正则图的度之和为:pk

完全图

p阶完全图

握手定理

握手定理

子图

  • 生成子图
  • 导出子图 生成子图 | 导出子图

示例

图的运算

图的运算

  • 对p行数学归纳法--递归
  • 对q行数学归纳法--递归或递推

二部图

二部图

二部图示例

二部图判别:

  • 标记法(有效的方法)
  • 同构检测(标号法,部分有效的方法) 标记法

img_v3_02ba_7592476e-e829-4275-aa7c-f968ba98c38g.jpg

img_v3_02ba_ed801a13-9c67-49d8-9abb-18c33c88247g.jpg

img_v3_02ba_bb14f41d-4a53-45b5-a518-5516e3f9916g.jpg