graph 概念及总结

概念

• vertex 点; edge 线

• v1 -> v2, v3, … (被 vertex 指到的 v), 这里指的是 v2, v3, 被称为 v1 的 successors.

• v1 -> v2, v3, … ( 指向 v2, v3 的 v), 这里指的是 v1, 被称为 v2, v3 的 predecessors.

• out degree: 从 vertex 指出去的箭头个数

• in degree: 从别的 v 指向当前 v 的箭头个数

• degree: 与 v 的连线总数

degree 在解题上有很大的用处. 比如: 如果图和树结合的题目, 当 out degree 为0 时,我们就能认定他是 leaf.

• degree 为 0 的 vertex 叫做 isolated vertex.

• 两头都落在同一个 vertex 上面的 edge 叫一个 loop. (多数时候不考虑 loop 因为没有太大意义)

• 起点相同, 终点也相同的两条 edges 称为 parallel edges.

• 一个没有 loops 和 parallel edges 的图叫 simple graph

• 一连串 edges 依序首尾相接, 不重复经过同一个 vertex, 称为一个 simple path.

• 起点和终点相同的 simple path 称为一个 simple cycle.

• 如果给图的每条边规定一个方向，那么得到的图称为有向图

• 边没有方向的图称为无向图

• adjacency matrix 用 matrix 记录各点之间是否相连, 数字的大小可以表示权值的大小

• articulation point: 移除这个 v 会使得图 disconnect 的 v

• bridge: 断掉会使图disconnect 的 edge

图的类别

• Directed Acyclic Graph (DAG): 在一个 directed graph 中没有 cycle 的图就叫 DAG.
• discrete graph: 图中没有 edges, 每一个 vertex 都是 isolated vertex.
• complete graph: 任意两个 vertices 之间都有 edge 相连的 undirected graph 叫做 complete graph. 总共 edges 数为n(n-1)/2.
• bipartite graph: 把 vertices 分为两组, 同一组的 vertices 内彼此之间没有 edges.
• strongly connected graph: 一个 directed graph, 从每个 vertex 出发, 都有路可以到达其他任何一个 vertex, 就叫做一个 strongly connected graph.
• strongly connected component: 每块大到不能再大的 strongly connected subgraph.

如果将 directed graph 所有 strongly connected components 表示出来, 每个 components 以一个大的 vertex 取代, 形成一个新的图, 则这个图是DAG.

subgraph

从原图 G = (V, E) 当中随便取出一些 vertices V’, 并且从 E 中随便取出一些 E’, 并且这些 E’两端都落在 V’之内, 所构成的图 G' = (V', E') 称为 G 的一个 subgraph.

图的骨架 ( spanning tree )

G=(V,E) 的 subgraph G'=(V',E')中如果G'满足:

1. 它是 connected.
2. 它没有 cycle.

G' 称为 G的一个spanning tree.

• 每棵spanning tree 一定恰好有 n-1 条 edges.

• 一个 weighted connected undirected graph 的所有spanning tree当中, edges 总和最小的那些称为 minimal spanning trees. (油管布线或者网路线的配置以最低成本考量, 喜欢布线成 MST).

• 每个 connected component 找出一个 spanning tree, 将这些 spanning tree合起来称为 spanning forest