图论复习

未完成——不想写了

图的基本概念

  • 阶：图G中顶点的个数$\nu (G)=|V(G)|$（简记为$\nu,V$）
  • $\epsilon (G)=|E(G)|$（简记为$\epsilon ,E$）
  • 无限图：$\nu(G)+\epsilon (G)=+\infty$，否则成为有限图
  • 关联/相邻/邻顶：$\psi (e)=\{u,v\}$
  • 重边/环
  • 简单图：无环无重边
  • 完全图 二分图 完全二分图
  • 零图 星图
  • 度数$deg(\nu)=d_1(\nu)+2\times l(\nu)$
  • 最大/最小度数$\delta (G)=min_{\nu \in V(G)},\Delta (G)=max_{\nu\in V(G)}$
  • 无向图$\sum_{\nu\in V(G)}{deg(\nu)=2\epsilon(G)}$
    • 给定图G，G中度数为奇数的顶点个数为偶数
  • 真子图，生成子图（V(H)=V(G)），顶点导出子图，边导出子图
  • 补图，边图：边图的边对应原图的顶点，顶点对应原图的边
  • 并，交
  • 积：$G\times H=(V’,E’)$,边集合分为三类：
    • 两个顶点在的两个分量在原图中均相邻
    • 有一个分量在原图中相邻，另外一个分量为同一个顶点
  • 路径/行迹/轨道/回路/圈
  • 连通/不连通：连通存在距离
  • 图的同构：元素之间的二元关系完全相同
  • Ulam猜想：G与H全等 等价于 对任何$\nu \in V(G),G-\nu=V-\nu$
  • 有向图D：$D=(V(D),E(D),\psi _D)$
  • $\sum_{\nu\in V(G)}{deg^-(\nu)}(入度)=\sum_{\nu\in V(G)}{deg^+(\nu)}(出度)=\epsilon(G)$

定理：G为二分图当且仅当G中无奇圈

最长轨道 反证例：若G为简单图，$\delta (G)>=2$，则G中必含圈

​ 若G为简单图，$\delta (G)>=3$，则G中必含有偶圈

最短路径问题$\omega (P_0(u,v))$——Dijkstra算法

​ 证明略。

类似最短路径的相关思路——如取生成子图最大边数：

任给无向图G，存在H为G的生成子图，满足：

  • H是二分图
  • 任给$u\in V(G)=V(H),有d_H(u)>=d_G(u)/2$

取H为边数最大的二分图，假设不满足条件2

树

基本概念:

  • 树叶/分支点（树枝） 森林/平凡树

以下命题等价

图的连通性

平面图

匹配理论

Euler图和Hamilton图

图的着色

有向图

网络流理论

图矩阵和图空间