查看“2012级--讨论记录 (第三学期)”的源代码

=2013年9月6日=
[[媒体文件:讨论记录-第三学期-2班-第1次.pdf|[课件下载]]]
<ol>
  <li>Bellman-Ford算法。</li>
  <li>Dijkstra算法。</li>
  <li>
    最短路问题的应用：
    <ul>
      <li>差分约束问题：制作番茄炒蛋的时间表。</li>
      <li>设备更新问题。</li>
    </ul>
  </li>
</ol>

=2013年9月13日=
[[媒体文件:讨论记录-第三学期-2班-第2次.pdf|[课件下载]]]
<ol>
  <li>简单的动态规划法。</li>
  <li>Floyd-Warshall算法。</li>
  <li>Johnson算法。</li>
  <li>
    多源最短路问题的应用。
    <ul>
      <li>选址问题。</li>
      <li>最宽路问题：Schulze投票法。</li>
    </ul>
  </li>
</ol>

=2013年9月20日=
[[媒体文件:讨论记录-第三学期-2班-第3次.pdf|[课件下载]]]
<ol>
  <li>最大/最小 点/边 独立/覆盖集，及其相互关系。</li>
  <li>
    最大匹配算法。
    <ul>
      <li>增广路算法。</li>
      <li>Hopcroft-Karp算法。</li>
      <li>Edmonds算法。</li>
    </ul>
  </li>
  <li>
    独立/覆盖问题的应用。
    <ul>
      <li>教室分配问题。</li>
      <li>公园选址问题。</li>
      <li>剪纸问题。</li>
    </ul>
  </li>
</ol>

=2013年9月27日=
[[媒体文件:讨论记录-第三学期-第4次.pdf|[课件下载]]]
<ol>
  <li>
    连通度。
    <ul>
      <li>点/边连通度和k点/边连通，及分情况举例。</li>
      <li>惠特尼定理，及分情况举例。</li>
      <li>3-正则图点、边连通度相等的证明。</li>
    </ul>
  </li>
  <li>
    块。
    <ul>
      <li>块及其性质。</li>
      <li>块-割点图及其性质。</li>
      <li>块算法。</li>
    </ul>
  </li>
  <li>
    k连通图。
    <ul>
      <li>x-y cut。</li>
      <li>Menger定理。</li>
      <li>连通度和不交路之间的联系。</li>
    </ul>
  </li>
</ol>

=2013年10月11日=
[[媒体文件:讨论记录-第三学期-2班-第5次.pdf|[课件下载]]]
<ol>
  <li>
    网络流。
    <ul>
      <li>Menger's Theorem和Max-flow Min-cut Theorem当capacity是整数时的对应关系。</li>
      <li>求二部图最大匹配的增广路算法和Ford-Fulkerson算法在求二部图最大匹配时的对应关系。</li>
    </ul>
  </li>
  <li>
    染色。
    <ul>
      <li>基本概念。</li>
      <li>色数和团数之间的关系及举例。</li>
      <li>建模：活动时间安排；数独求解；课程时间安排。</li>
      <li>贪婪染色及其改进。</li>
    </ul>
  </li>
  <li>
    平面图。
    <ul>
      <li>基本概念（特别是planar graph和plane graph的区别）。</li>
      <li>face到outer face的转换。</li>
      <li>图的可平面性和block的可平面性。</li>
      <li>对偶图及其性质。</li>
    </ul>
  </li>
  <li>
    哈密尔顿圈。
    <ul>
      <li>欧拉回路和中国邮递员问题。</li>
      <li>哈密尔顿圈和旅行商问题。</li>
    </ul>
  </li>
</ol>