图论与树

Tips

考虑历年题目，按重要程度书写

最小生成树问题

• 通常以一个带权无向图的形式出现（图可能代表城市、村庄、矿井采集点等）
• 问题直接明了：“求总成本最低的补给线路”、“设计总造价最小的修路方案”、“计算最小成本”等。
• 要求：不仅要算出最小的总权值，通常还需要画出或列出构成最小生成树的边集。

算法：

• 克鲁斯卡尔算法：按权值从小到大选择边，只要不形成回路就加入，直到链接完所有定点为止
• Prim算法：从一个顶点开始，每次选择连接已选顶点集和未选顶点集的权值最小的边
• 一般而言选择第一种算法，更加直观清晰

主要模型建模

• 哈密顿回路/路径：
  • 场景：“圆桌会议”,“旅行商问题”
  • 问题：“能否安排座位使得相邻的人都能交谈？”,“能否找到一条路径访问所有点一次？”
  • 方法：将人/地点视为 顶点，将可以交流/连接的关系视为 边，问题转化为寻找一条经过所有顶点的回路。
  • 判断是否存在哈密顿回路方法：
    • 这是一个完全NP问题，我们可以依据下面一些条件初步判断
      • 若顶点数大于3：
        • Dirac定理：若每个顶点的度数 $deg(v)\ge \frac{n}{2}$则为哈密顿图
        • Orc定理 ：若对两个不相邻的顶点$u,v$ 有$deg(v)+deg(u)\ge n$则是哈密顿图
      • 这是一个充分条件，有时候不满足上述两条也可能构成哈密顿图，需要自己再看看
• 图的着色 (Graph Coloring)
  • 场景：“考试时间安排”、“会议安排”、“地图着色”。
  • 问题：“最少需要多少时间段才能考完所有课程？”
  • 方法：将课程/事件/国家视为顶点，如果两个课程有学生同时选修（即存在冲突），则在对应顶点间连一条边。问题转化为求该图的色数（最少需要多少种颜色给顶点着色，使得相邻顶点颜色不同）。
    • 这是一个著名的NP完全问题，在考试情景下不可能过分困难
    • 勇敢尝试
• 匹配 (Matching)
  • 场景：“配对问题”、“任务分配”
  • 问题：“能否选出4组不同的配对，用完所有8种颜料？
  • 建模方法：将颜料/人员视为顶点，能互相搭配的关系视为边。问题转化为寻找图中的 完美匹配（一个覆盖所有顶点的边子集，且边与边之间不共享顶点）。
    • 完美匹配存在的性质
      • 当一个图的顶点数量$|V|$为偶数时候才有可能存在完美匹配
      • 最大匹配是指图中边数最多的匹配
      • 如果一个最大匹配包含了图中的所有顶点，那么它就是一个完美匹配
      • 如果一个图有偶数个顶点且存在哈密顿回路，那么这个图一定存在完美匹配

理论证明：平面图与欧拉公式

主要考虑

• 欧拉公式：$v-e+f=2$ 
• 其中，$v$:顶点数,$e$:边数, $f$:面数(不用忘记外部面)
  • 推论1： 对于$v\ge 3$的简单连通平面图$e\le 3v-6$
  • 推论2： 如果简单连通平面图中没有长度为3的回路（即没有三角形），$e\le 2v-4$
  • 面度数推论 ：根据握手定理我们可以得出$\sum _{i=1}^{f}deg(F_i)=2e$
  • 即所有面的度数之和等于2倍的边数