图论#

图的定义#

图的表示#

1. 图形表示法（画图）
2. 集合表示法（使用序偶和无序对）
3. 邻接矩阵表示

邻接矩阵的假设：有限图：只有一条边

补充：

1. 邻接表表示法
2. 十字链表法

图的分类#

1. 无向图、有向图、混合图
2. 多重图、线图（线性的）、简单图（无环）
3. 赋权图、无权图

子图和补图#

• 子图：边和结点都是包含关系。

  • 真子图：不相等
  • 生成子图：V相等，E为包含关系
  • 最小生成子图：权值最小的生成子图。
  • 导出子图：V为包含关系，E为对应的所有边。

    如全校关系网络图中，提取某个班的导出子图

• 完全图：在简单图中，任意两个结点都有边相连

  • 无向完全图、有向完全图

    没有自环，邻接矩阵对角线为0

• 补图：完全图的边 - 简单图的边 = 这个简单图的补图

  不要漏掉补图中的孤立结点

握手定理#

• 结点的度：…
• 度为1的结点叫做悬挂结点，对应的边为悬挂边
• 最大入/出度：所有结点中，单个结点的最大入/出度。

握手定理：$deg = 2|E|$

推论：度数为奇数的结点个数为偶数。

图的同构#

设有两个图G和G’，如果存在结点V的双射函数，任意两点之间的边都相同，且重数也相同，则称图G和图G’同构(isomorphism)

连通图#

通路：由结点和边相继交错出现的序列。

$\Gamma = v_0e_1v_1e_2v_2e_3...e_kv_k$

边的数量为通路的长度，$v_0,v_k$为通路的端点。当v_0 = v_k时称作回路。

通路的边互不相同，叫做简单通路

回路的边互不相同，叫做简单回路，反之为复杂回路。

点和边都不相同叫做基本通路/回路

回路是通路的特殊情况。

• 线图中，长度为m的通路数量：
  • 设A的为图G的邻接矩阵。$A^m$中，$a_{ij}$表示从i -> j 长度为m的路径数量
  • 矩阵总和为，整个图中长度为m的通路数量。

可达性和最短通路（最短路径）#