算法设计与分析课程Part1笔记(3)

3.2 算法分析

3.3 图的基本

   图简单来说是有点和边构成&＃xff0c;通常用G表示&＃xff0c;G&＃61;(V, E)&＃xff0c;其中V是顶点集合&＃xff0c;E是边集合。一般用n代表G的节点数目&＃xff0c;m代表G的边数。

   图的割集指的是&＃xff1a;将图的顶点分为两个非空集合A和B&＃xff0c;那么对于端点分别在A和B中即连接两个断点集合的边数为c&＃xff0c;A和B可以称为图G的一个割集。

   其中使得c最小的割集&＃xff0c;为G的最小割(minimumcut)。一个包含n个节点的图G其割集有2ⁿ个。

   图的两种基本表示&＃xff1a;邻接矩阵和链接表&＃xff0c;一个方便随机存取&＃xff0c;一个节省空间&＃xff0c;对于sparse的图(即图密度m/n比较小)来说&＃xff0c;链接表虽然不利于随机存取&＃xff0c;但是很节省空间。

3.4 最小割问题

  Random_Construction_Algorithm(Karger, early 90s):

   -- while there more than 2 vertices:

    --pick a remaining edge (u,v) uniformly at random

    --merge u and v into a single vertex

    --remove  self-loops

    最后只剩下了两个顶点&＃xff0c;两个顶点之间的边数c是一个割集的cross edges的数目&＃xff0c;但是不一定是最小的。