当前位置：文档之家 › 图的强彩虹连通数

图的强彩虹连通数

  • 格式：pdf
  • 大小：212.55 KB
  • 文档页数：5

图 的 一 个 强 彩 虹 连 通 数 的上 界 ． 接 着 给 出 了这 个 上 界 取 等 的 充 分 条 件 ．
关键词 ： 彩虹测地线 ； 强 彩 虹 连通 数 ； 边 不 交 的 圈 中图 分 类 号 ： Ｏ１ ５ ７ ． ５ 文献 标 识 码 ： Ａ
１ 引 言 和若 干 定 义
） 表 示 最短 一 路 的长 度．
定义 １ ． ６ 图 Ｇ 称为 是强 彩 虹连 通 的 ， 如 果 对 于 Ｇ 的任 意两 个顶 点 ， ， Ｇ 都有 一 条彩 虹 Ｕ一 测
地 线． 在 这种 情况 下 ， 着色 Ｃ称 为 图 Ｇ 的强彩 虹着 色． 定义 １ ． ７ 在 图 Ｇ 的边上 定义 的一 个着 色 Ｃ ： Ｅ（ Ｇ） 一｛ １ ， ２ ， …， ｋ ） ， 则 满 足 Ｇ 是 一个 强 彩 虹 连通 的 最 小颜 色数 目 ｋ称 为 Ｇ 的强彩 虹连 通数 ， 记做 ｓ ｒ ｃ （ Ｇ） ．
摘 要： 如 果 图 Ｇ的 任 意 两 个 顶 点 由一 条 路 Ｐ连 接 ， 其 中路 Ｐ 的 每 一 条 边 着 不 同 的 颜 色 ， 则 称 图 Ｇ 为 彩 虹 连 通
图． 对 图 Ｇ 的任 意 两 个 顶 点 “和 口 ， Ｇ 的彩 虹 Ｕ一 口测 地 线 是 一 条 长 为 ｄ （ ｕ ， 口 ）的彩 虹 路 ， 其中ｄ （ ｕ ， ）表示 最 短 的 “
收 稿 日期 ： ２ ０ １ ５ — ０ ３ — ０ １
＊
基金项 目： 四川 Ｉ 省 教 育 厅 自然 科 学 基 金 （ １ ５ Ｚ Ｂ ０ ３ ４ ６ ） ； 成 都 师 范 学 院科 研 基 金项 目（ Ｃ Ｓ １ ４ Ｚ Ｂ ０ ６ ） 作者简介 ： 王万 禹 （ １ ９ ８ ６ 一 ） ， 男， 讲师， 研究方 向 ： 图论及其应用．
用 到 的一 些定 义 和注解 ．
定义 １ ． １ 在 图 Ｇ 的一 条路 中 ， 如果 任意 两条 边着 不 同 的颜 色 ， 则称 这条 路为 彩虹 路． 定义 １ ． ２ 边着 色 的图 Ｇ 称 为彩 虹 连通 图如 果 图 中任 意 两个 顶 点 由一 条彩 虹 路 连接 ． 如果 Ｇ 是 彩
Ｊ ｕ ｎ ． ２ ０ １ ５
Ｖｏ１ ． ３２ ＮＯ． ２
第 ３ ２卷 第 ２期
文章 编号 ： １ ０ ０ １ — ８ ７ ４ ３ （ ２ ０ １ ５ ） ０ ２ — ０ ０ ０ １ — ０ ５
图 的 强 彩 虹 连 通 数
王 万 禹
（ 成都 师 范 学院 数 学 系， 四川 成 都 ６ １ １ １ ３ ０ ）
本文中， 我们考 虑 的 图 Ｇ 都是 无 向 ， 有 限和 简单 图． 令 Ｇ 是一 个 非平 凡 的 连通 图 ， 在 Ｇ 的边 上 定 义
一
个着 色 Ｃ ： Ｅ（ Ｇ） 一｛ １ ， ２ ， …， ） ， ∈Ｎ， 其 中相 邻 的边 可 以着 相 同 的颜 色． 接 下来 我 们 给 出本 文 所 需要
２ ０ １ ５年 ６月
广 西师 范 学 院 学 报 ： 自 然科 学版
Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｇｕ ａ ｎ ｇ ｘ ｉ Ｔｅ ａ ｃ ｈ ｅ ｒ ｓ Ｅｄ ｕ ｃ ａ ｔ ｉ ｏ ｎ Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ： Ｎａ ｔ ｕ ｒ ａ ｌ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ Ｅｄ ｉ ｔ ｉ ｏ ｎ
图．
由上 述定 理 ， 我们 知道对 于 任意 图 Ｇ， 给 出其精 确 的强 彩虹 连通 数 ｓ ｒ ｃ （ Ｇ） 是 很难 的 ， 所 以我们 感 兴 趣 的是在 某些 特定 条件 下 ， 去找 到 ｓ ｒ ｃ （ Ｇ） 的一 个 界． 本 文 就是 根 据 图 Ｇ 中含 边 不交 的个 数来 确 定 这 类
一
路的长度． 图 Ｇ 称 为强 彩 虹 连 通 的 如 果 对 Ｇ 的任 意两 点 “和 间都 存 在 一条 彩 虹 Ｕ一 测 地 线 ． 图 Ｇ 的 强 彩 虹
连通 数 是 指 使 得 图 Ｇ 是 强 彩 虹 连 通 而 用 的最 少颜 色 的 数 目 ， 用 ｓ ｒ ｃ （ Ｇ） 表示． 该 文 首 先 给 出 了一 个 含 边 不 交 的 一 圈
对 于每 一个 连通 图 Ｇ， 显 然有 ｄ ｉ ａ ｍ（ Ｇ） ≤ｒ ｃ （ Ｇ） ≤ｓ ｒ ｃ （ Ｇ） ≤ ， 其中 ｄ ｉ ａ ｍ（ Ｇ） 和 ｍ 分别 表示 图 Ｇ 的 直 径 和边数 ．
彩 虹着 色 的 概念 是 由 Ｃ ｈ ａ ｒ ｔ ｒ ａ ｎ ｄ， Ｊ ｏ ｈ ｎ ｓ ，Ｍ ｃ ｋ ｅ ｏ ｎ和 Ｚ ｈ ａ ｎ ｇ Ｌ ｌ 在 ２ ０ ０ ８年 提 出 来 的 ． Ｃ ｈ ａ ｒ ｔ ｒ ａ ｎ ｄ ，ｅ ｔ
ａ １ ． ［ 证 明 了计 算 图 Ｇ 的彩 虹连 通数 是 一个 ＮＰ 一 难 的． 许 多研 究 者
利用 给 图 Ｇ 限定 一些 条 件 ， 如最
小度 ， 连通 度 等来 给 出这类 图 的彩虹 连通 数 的界． 对于 图论 中一 般性 的概 念 ， 我们参 照 文献 Ｅ ｓ － ｉ ． 定理 １ ． ８ （ ［ ２ ３ ） 对 于任意 整数 ｋ ≥３ ， 要确 定 ｓ ｒ ｃ （ Ｇ） ≤ 尼是否 成立 是一 个 ＮＰ 一 难 么边 着色 Ｃ称 为彩 虹着 色．
定义 １ ． ３ 如果 一个 彩虹 着 色 图用 了 志种颜 色 ， 那 么我们 称这 个 图为 志一彩虹 着色 图． 定义 １ ． ４ 使得 图 Ｇ 是 彩 虹连 通 图的最 小颜 色数 目ｋ称 为 图 Ｇ 的彩 虹连 通数 ， 记做 ｒ ｃ （ Ｇ） ． 定义 １ ． ５ 对 Ｇ 的任 意两 个顶 点 “， ， 彩虹 Ｕ 一 测 地线 是 一 条 长 为 ｄ （ ， ） 的彩 虹 路 ， 其中ｄ （ ｕ，

合集下载

强连通分量——精选推荐

强连通分量——精选推荐

强连通分量写在前⾯：我是⼀只蒟蒻今天，我们来介绍⼀下强连通分量这个玩意⼉有向图的DFS：与⽆向图的差别就在于，搜索时只能顺边。

所以，有时的搜索树会不⽌⼀个根，因为，从⼀点出发不⼀定能⾛完所有点。

在⼀个搜索图中，每条有向边（x,y）⼀定是以下三（四）种之⼀：⽗⼦边——具有⽗⼦关系返祖边——指向其祖先横叉边——dfn[y]<dfn[x]强连通图定义给定⼀张有向图。

若对于图中任意两节点x,y，既存在x到y的路径，也存在y到x的路径，则称该有向图是“强连通图”。

强连通分量（SCC）即有向图中的极⼤强连通⼦图。

思想实现Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的⼀棵⼦树。

搜索时，把当前搜索树中未处理的节点加⼊⼀个堆栈，回溯时可以判断栈顶到栈中的节点是否为⼀个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的⼦树能够追溯到的最早的栈中节点的次序号。

当DFN(u)=Low(u)时，以u为根的搜索⼦树上所有节点是⼀个强连通分量。

下⾯我们对这个图进⾏⼀下模拟这样，我们就完成了找强连通分量的过程，下⾯我们来看⼀下核⼼代码，1void tarjan(int x){2 dfn[x]=low[x]=++num;//更新3 s[++top]=x;in[x]=1;//当前元素⼊栈4for(int i=head[x];i;i=e[i].next){5int y=e[i].to;6if(!dfn[y]){7 tarjan(y);8 low[x]=min(low[x],low[y]);9 }else{10if(in[y])low[x]=min(low[x],dfn[y]);//如果被访问过且还在栈中，更新11 }12 }13if(dfn[x]==low[x]){//是强连通分量14 cnt++;int c;//颜⾊块加⼀15do{16 c=s[top--];17 a[c]=cnt;//进⾏染⾊处理18 v[cnt]++;//当前连通块的数量统计19in[c]=0;//出栈标记20 }while(x!=c);21 }22 }OK，我们就结束了基本讲解，下⾯是两道基本栗题。

图的连通性精品PPT课件

图的连通性精品PPT课件

ar Cows
给定一个有向图，求有多少个顶点是由任何顶 点出发都可达的。
顶点数<= 10,000,边数 <= 50,000
有用的定理:
有向无环图中唯一出度为0的点，一定可 以由任何点出发均可达(由于无环，所 以从任何点出发往前走，必然终止于 一个出度为0的点)
ACM2186: 解题思路
有向图的强连通分支
定义
在有向图G中，如果任意两个不同的顶点 相互可达，则称该有向图是强连通的。 有向图G的极大强连通子图称为G的强连 通分支。
转置图的定义：将有向图G中的每一条 边反向形成的图称为G的转置GT。（注 意到原图和GT的强连通分支是一样的）
Korasaju算法
procedure Strongly_Connected_Components(G);
学习并没有结束，希望继续努力
Thanks for listening, this course is expected to bring you value and help 为方便学习与使用课件内容，课件可以在下载后自由编辑
ACM1236: 解题思路
1. 求出所有强连通分量
2. 每个强连通分量缩成一点，则形成一个有 向无环图DAG。
3. DAG上面有多少个入度为0的顶点，问题1的 答案就是多少
ACM1236: 解题思路
在DAG上要加几条边，才能使得DAG变成强连通 的，问题2的答案就是多少
加边的方法：
要为每个入度为0的点添加入边，为每个出度 为0的点添加出边
end; 证明参考：
(a)为有向图G， 其中的阴影部分 是G的强连通分 支，对每个顶点 都标出了其发现 时刻与完成时刻 ，黑色边为深度 优先搜索的树 枝；
彩虹连通图

彩虹连通图

引言1.1 基本概念在本节中，我们要收集的大部分术语和符号用于此专题。

这里还没有给出，在需要时他们将被定义出来。

所有的图形在这本书中被认为是有限、简单和无向的。

我们也遵循那些不在这里定义的[ 9 ]符号术语。

在这我们分别用V（G）和E（G）表示顶点集，G的边集。

用任何子集（G），用G [X]表示诱导的子图，并且设E[×]的边集为G [X]；同样，对E(G)的任意子集为F，让G [F]表示包含在F中的子图。

然后我们表示成，和，这是所有对于y的图的总和。

A 是图G定义的一个集合，作为G的一个完全子图，并且最大集合中不包含任何G的较大的集合。

F对于集合S，|S|为S的势。

一个连通图的边称为桥，它去除将会断开该连通图。

没有桥的图叫做无桥图。

一条有n个顶点的路径表示为n P，其长度为N—1并且用表示。

一个顶点的度是1 那么就叫做悬垂。

我们称G路径长度为悬垂k路径，如果一个末顶点度为1，而所有内顶点度为2。

悬垂1长度的路径就是一个悬垂的势。

我们用表示一个周期的顶点。

对于n≥3，周期为是通过加入一个新的顶点对于每个顶点。

让是一个完全偶图（它的大小可以分别表示成s、t两部分）。

线图G是图(或）其顶点集V(L(G))=E(G)和两个对于相邻顶点当且仅当他它们在G中是相邻。

图G的迭代线图对于图形的线图L(G)，被表示成。

一般而言，k-迭代线图是线图。

对于一个相交图集，其顶点可以映射到集，所以有图中的两个顶点之间的边当且仅当对应的两个集合有一个非空交。

区间图是一个实线区间图的相交图。

圆弧图是圆弧形的一个相交图。

一个独立的三个顶点的x、y、z图G一个星状的三重(AT)，如果每一对中的顶点，有一个路径不包含任何相邻的第三路径。

有自动测试系统的图形称为无图[25]。

图G如果存在权函数，一个阈值图：V(G)→R和真正的常数，那么要两个顶点 u，v∈V(G)相邻只有满足w(u)+w(v)≥t。

二部图G(A，B)称为链图，如果一个顶点可以令为那么。

求有向图的强连通分量个数（kosaraju算法）

求有向图的强连通分量个数（kosaraju算法）

求有向图的强连通分量个数（kosaraju算法）求有向图的强连通分量个数（kosaraju算法）1. 定义连通分量：在⽆向图中，即为连通⼦图。

上图中，总共有四个连通分量。

顶点A、B、C、D构成了⼀个连通分量，顶点E构成了⼀个连通分量，顶点F，G和H，I分别构成了两个连通分量。

强连通分量：有向图中，尽可能多的若⼲顶点组成的⼦图中，这些顶点都是相互可到达的，则这些顶点成为⼀个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

2. 连通分量的求解⽅法对于⼀个⽆向图的连通分量，从连通分量的任意⼀个顶点开始，进⾏⼀次DFS，⼀定能遍历这个连通分量的所有顶点。

所以，整个图的连通分量数应该等价于遍历整个图进⾏了⼏次（最外层的）DFS。

⼀次DFS中遍历的所有顶点属于同⼀个连通分量。

下⾯我们将介绍有向图的强连通分量的求解⽅法。

3. Kosaraju算法的基本原理我们⽤⼀个最简单的例⼦讲解Kosaraju算法显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。

每个连通分量中有若⼲个可以相互访问的顶点（这⾥都是3个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成⼀个整体，即看成同⼀个强连通分量。

我们现在试想能否按照⽆向图中求连通分量的思路求解有向图的强连通分量。

我们假设，DFS从强连通分量B的任意⼀个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，⽽且每次DFS遍历的顶点恰好属于同⼀个连通分量。

但是，我们若从连通分量A中任意⼀个顶点开始DFS，就不能得到正确的结果，因为此时我们只需要⼀次DFS就访问了所有的顶点。

所以，我们不应该按照顶点编号的⾃然顺序（0,1,2，……）或者任意其它顺序进⾏DFS，⽽是应该按照被指向的强连通分量的顶点排在前⾯的顺序进⾏DFS。

上图中由强连通分量A指向了强连通分量B。