Information浅析.pptVIP

问题抽象与归纳1 问题的基本结构是一个有重边的有向图G={V,E} G对应于传输方案（Transmission scheme) V是图的结点集合，其中元素表示特工（agent）； E是图的边集合，其中元素表示联络员（contact） E的另一特点，它是有序集（有向边的集合）。 问题抽象归纳2 问题的目标是将E分为两个交集为空的子集E1、E2， 使G1＝ {V, E1} 与 G2＝ {V, E2} G1、 G2分别是原图的连通子图 这里E1与E2也是有序集。 元素顺序与其在E中的顺序一致。 问题抽象归纳3 给定n个结点，m条边的一个有重复边的有向图G（允许两个结点间的边数多于一条）。 图G有一个根结点，即入度为零的结点 问题是在图G中寻找两条从根结点出发的没有公共边的遍历途径。 输入输出格式 输入文件 第一行：特工人数N，联络员总数M 其后M行：各联络员对应的特工编号 输出 无解：NONE 有解：输出两行，每行对应情报一个部分的有效传输方案。在每行中给出使用的联络员的编号。 朴素的想法 基本思路是，先从边集E中按一定规则选取n-1个元素构成E1，E1与V构成子图G1 在E-E1中选取n-1条边构成E2，E2与V构成子图G2。 若G1与G2都是连通的，则分行依序输出E1与E2中的元素。 若G1或G2有一个是不连通的，则按规则选择另一组E1及其后的E2，直到构成解或重复选择的次数超过了预先的限制。 算法实现思路 该过程可以用一个类似Kruskal的算法实现，即： 对G = { V, E }, 先构造一个只有 n 个顶点, 没有边的非连通图 G1 = { V, ? } 这时G1中每个顶点自成一个连通分量。 然后在 E 中选一条边（从边集E中选择边的顺序可以依E集合本身的顺序，随机选取等）, 若该边的两个顶点在不同的连通分量中，则将此边加入到 G1 中，否则重新选择一条边。 如此重复下去, 直到所有顶点在同一个连通分量上为止。 边数总共有n-1条，G1为生成树。G2同理。 算法实现思路 在构造生成树G1、G2过程中, 可利用并查集的运算检查一条边上的两顶点是否在同一连通分量 (即并查集的同一个子集合) 上 是则舍去这条边；否则将此边加入G1或G2, 同时将这两个顶点并入同一个连通分量。 用BFS或DFS遍历的方法判断图的连通性，如果对生成的子图遍历到全部n个结点，则说明子图是连通的；否则是非连通的。 参考算法 首先使用Prim算法生成一个以第一个结点为根的生成树，即将图G的结点集V分为两个子集V1，V2，其中V1是生成树的顶点集合。 假设G是连通图，那么在V1与V2之间必有至少一条边相连。于是，按一定规则（在Prim算法中是选取权值最小的边，对应于本题则可以根据e∈E的次序）选取一条边e ＝（u, v）（u∈V1，v∈V2）， 将其加入G1＝{V1, E1}，直到|V1|＝n-1。然后使用剩余的边生成G2。 总之，可以先任意构造一棵生成树G1； 然后使用剩余的边，尽可能的尝试构造第二棵生成树G2。 实现操作的基本类 图类Graph 图的存储表示可使用邻接表；也可使用邻接矩阵，但要考虑其稀疏性 稀疏矩阵类Matrix的元素为四元组： 两个整型变量分别为边的首末结点号， 第三个整型变量中存放其间存在的联络员的总数 第四个元素是队列类Queue的对象指针，指向一个队列，其中依次存放两个特工之间的联络员编号。 实现操作的基本类 队列类Queue 用于BFS遍历时记录同层结点，对图中的边进行操作，方便对图的遍历 并查集类UFSets 处理结点与连通分量之间的关系（通过Find与Union操作） 时间和空间的协调：可以增加一些判断 如邻接表存储可以使用双向链表方便使用过的联络员和一些无用联络员的删除 这样对于大的数据来说，时间会节省很多，但是对于小的数据，则额外增加了很多存储空间对时间贡献不大。 拟阵的交 拟阵的交 对于定义在同一个集合E上的两个拟阵 M1=(S,T1), M2=(S,T2) 求T1与T2共有的最大独立集I 重要定理：对于 有 Edmonds 1973年曾证明： 以首结点为根且边不相交的生成树的最大数目等于任意以首结点为割点的割集的最小基数。在Information这道题中，这一基数为２。 惠特尼与拟阵(matroid)理论 惠特尼（美国数学家，1907-1989）在组合论方面的最大成就是他引进拟阵(matroid)理论——一种抽象的线性相关性理论，它不仅包含图论为其特例，而且还包括网络理论、综合几何以及横截(transversal)理论等． 基本出发点大致为，考虑矩阵M的列C1，C2，…，Cn，这些列的子集或者线性独立或者线性相关，从而所有子集可划分为两类，这些类并非任意，它必须