图连通小结

有关连通的一些定义和性质 ：

 一，哈密顿路径：给定两个顶点，存在连接他们的一条简单路径，使得访问图中的每个顶点一次且只有一次，如果这条路径是从一个顶点又返回到自身，那么这条路径就称为哈密顿路径；

二，欧拉路径：给定两个顶点，存在连接它们的一条路径（不必是简单路径），使得使用图中的边有且只有一次，如果这条路径是从一个顶点又返回到自身，那么这条路径就称为欧拉路径；
三，二分图：（又称二部图）设G=（V，E）是一个无向图，如果顶点V可分割为两个互不相交的子集（A，B），并且图中的每条边所关联的两个顶点不在同一子集A（或B）中； 

四，桥（分离边或割边）：桥是一条边，如果删除这条边，会将一个连通图分成两个不相交的子图。

五，缩点：在无向图中，没有桥的子图缩成一点称为缩点；（其实并不是指缩块）；

六，边连通：不含桥的图称为边连通的；
七，关节点（分离顶点或割点）：关节点是一个顶点，如果删除这个顶点，将把一个连通图至少分成两个不相交的子图；

十三，边连通度：图的边连通度是将图分为两部分所需删除的最小边数

有关连通的一些定理，性质，和推论

一，推论：一个图含有欧拉路径，当且仅当它是连通的，并且其中只有两个顶点的度为奇数

二，推论：每个非平凡无环连通图至少有两个顶点不是割点。

三，定理：一个连通图是树当且仅当它的每条边都是割边

四，Whitney定理：顶点V>=3的图G是2-连通图，当且仅当G中任两顶点共圈；

五，推论：顶点V>=3的图是2—连通图，当且仅当G中任两顶点被至少两条内部无公共顶点的路所连；

六，推论：顶点V>=3的图G是2-连通图，则G的任两边都位于同一个圈上；

七，Menger定理：对任意图G，设x, y是G 中两个不相邻顶点，则G 中分离x, y所需的最少顶点数等于G 中两两内部点不交的(x, y)路的最大条数，即s(x, y) = r(x, y)。

八，Menger定理：对任意图G，设x, y 是G 中两个不相邻顶点，则G 中分离x, y 所需的最少边数等于G中两两边不交(x,
y)路的最大条数，即s′(x,y) = r′(x, y)。

九，推论：图 G 是k 边连通图当且仅当G 中任二顶点至少被k 条两两无公共边的路所连

pku的一些练习题目：

一，pku 1236network of Schools 

问题转化：
*
subtask1:求最小的学校数（即软件数），使得软件能传递给所有的学校
*         ：求入度为零的强连通分量个数
*
subtaxk2：求需要增加得最小的学校列表，使得从任何学校发布软件，其他学校都能收到
*         ：max（入度为零的强连通分量，出度为零的强连通分量）

解题代码：超现实领地

二，pku 1523 SPF

题意：给定一个无向图，求这样的点（如果去掉该点，形成的强连通分量数大于1）

解题代码：超现实领地

三，pku 2553 The Bottom of a Graph 

题意：给定一个有向图，如果vertex归属的连通分量的出度为零，则输出该点；输出要从小到大排序；

解题代码：超现实领地

四，pku 1515 Street Directions 

题意：给定一个向无连通图，将图中的边改为有向边输出(顺序随意)，改动过程中必须保持图是连通的，如果此边改为单向边后无法连通，那么改为双向边输出（）

思路：如果边是桥，只能更改为双向边，否则改为有向边

解题代码：超现实领地

五，pku 1438 One-way Traffic

题意：给定一个图，有的边是无向的，有的图是有向的，现在尽可能多的将无向边改为有向边，要求改变后图仍然是一个连通图；无向边如果能改为有向边 输出     v1  v2  1  如果不能该，输出 v1  v2  2；

思路：同上一题；

解题代码：超现实领地

六，pku 3177 Redundant Paths

题意：增加多少边使无向图是双连通图！

解题代码：超现实领地