图与网络
basic conception
无向图 有向图 赋权图 有限图 简单图
完全图 二分图 子图 母图 顶点的度（入度，出度）
一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。
邻接矩阵表示法 邻接链表表示法 弧表表示法 关联矩阵 星形表示法（前向和反向）
弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m个存储单元，因此当网络比较稀疏时比较方便。
也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为−1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为 0。
道路(walk) 迹(trail) 轨(path) 圈(cycle)
一个连通图的生成树很多,用 $\tau(G)$ 来表示图的生成树的个数，则有如下公式：
匹配问题
1.几个定义
对集 匹配 完美对集 最大对集 交错轨 可增广轨
2.定理:
(1)M是图G的最大对集当且仅当G中无M可增广轨
(2)G 为二分图， X与Y是顶点集的划分，G中存在把X中顶点皆许配的对集的充要条件是，∀S ⊂ X ，则|N(S)|≥|S|，其中N(S)是S中顶点的邻集。
推论 若G是k次正则二分图（每个顶点皆K度的图），则G有完美对集
3.人员分派问题
1.匈牙利算法：利用匈牙利算法可以直接解决人员分派问题，其思路非常简单，故在这里不做介绍。
2.->最优分派问题
这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权$w(x_i,y_j)>=0$表示$x_i$干$y_j$ 工作的效益，求加权图G 上的权最大的完美对集。
解决这个问题可以参照《数学建模算法与应用》（司守奎）（P84）所给出的定义以及Kuhn-Munkres算法，其实质上是在匈牙利算法的进一步改善
如果想要对KM算法作深入的理解，可以参考这个blog
可行顶标$l$,对于任意弧,满足$e(x \rightarrow y) 都有 l_x+l_y\ge w_e$，后定义相等子图，其包含所有的点，但只包含满足$l_x+l_y=w_e$的所有弧$e(x \rightarrow y)$,这些弧已经是最大的弧，如果有完美匹配，那么可以得到最优分派。KM 算法仅仅只适用于找二分图最佳完美匹配，如果无完美匹配，那么算法很可能陷入死循环（如果不存在的边为 -INF 的话就不会，但正确性就无法保证了），对于这种情况要小心处理。
4. Euler 图和Hamilton 图
1.基本概念
经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E
回路；含Euler 回路的图叫做Euler 图。
定理
（i）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次。
（ ii ） G 是Euler 图的充分必要条件是G 连通且$G=\bigcup_{i=1}^dC_i,C_i$是圈，$E（C_i)\bigcap E(C_j)(i \neq j)$
（iii）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点。
包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton 轨叫做Hamilton 圈或H 圈；含Hamilton 圈的图叫做Hamilton 图。
Fleury 算法给出了求Euler 回路的算法