精华内容
下载资源
问答
  • 强连通弱连通的概念只在有向图中存在。 强连通图: 在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。 弱连通图: 将有向图的所有的有向边替换为无向边,所得到的图...

    图论的起源

    关于图的第一篇论文是瑞士数学家欧拉(E. Euler)在1736年发表的解决“哥尼斯堡"七桥难题的论文:
    在这里插入图片描述

    德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。
    为了寻找答案,1736年欧拉将这个问题抽象或图所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。

    图论的基本概念

    图:图论中的图是由点和点与点之间的线所组成的。通常,我们把点与点之间不带箭头的线叫做,带箭头的线叫做

    无向图:如果一个图是由所构成的,那么,称为无向图,记作G=(V, E),其中V表示图G的点集合,E表示图G的边集合。连接点vi,vj的边记作[vi, vj],或者[vj, vi]。

    有向图:如果一个图是由所构成的,那么称为它为有向图,记作D=(V, A),其中V表示有向图D的点集合,A表示有向图D的弧集合。一条方向从vi指向vj的弧,记作(vi, vj)。

    简单图:一个无环,无多重边的图称为简单图
    在这里插入图片描述

    多重图:一个无环,有多重边的图称为多重图
    在这里插入图片描述
    链:由两两相邻的点及其相关联的边构成的点边序列。如v0,e1,v1,…,vn-1,en,vn。
    简单链:链中所含的边均不相同
    初等链:链中所含的点均不相同,也称通路

    连通图:图中任意两点之间均至少有一条通路,否则称为不连通图
    在这里插入图片描述

    连通图:在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。

    强连通和弱连通的概念只在有向图中存在。

    强连通图:在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。
    在这里插入图片描述

    弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

    展开全文
  • 前言网上现存\(60\%\)的文章都有明显的误区,本文章经过多次修改,能保证正确性本文涉及强连通分量、弱连通分量、割点、割边、边双、点双,属于基本图论范畴在有着直接关联的基础上又有所不同,本文基于把抽象的数组...

    前言

    网上现存\(60\%\)的文章都有明显的误区,本文章经过多次修改,能保证正确性

    本文涉及强连通分量、弱连通分量、割点、割边、边双、点双,属于基本图论范畴

    在有着直接关联的基础上又有所不同,本文基于把抽象的数组转换为在图上的意义,旨在让初学者能更轻松地理解并区分差别

    为避免各个板子的差别过大,在正确的基础上尽量保证代码的相似性

    如果您之前学过,可能与您的定义有所不同,故请在看完每个算法下面的代码后再进行文字阅读

    文字中某个词语后出现带圆框的数字,如①②,这些词语将会在文字下方有详细的注释,方便阅读

    前置

    我们简略地定义\(dfs\)树为遍历路程中路径所组成的一棵树,注意下面说的儿子、叶子节点、子树边界\((\)与子树直接相连的外部节点\()\)等用法都从此基础上得出

    如下图及\(dfs\)树,\(3,7\)为\(1\)的儿子,叶子节点为\(2,5,6,8\),\(7\)的子树边界为\(\{1\}(1\)与\(7\)和\(8\)直接相连\()\),如果新加一条边\((3,4)\),则\(7\)的子树边界为\(\{1,3\}\)

    有向图

    强连通分量

    定义:有向图中某个点集中的点互相能到达的分量为强连通分量

    为方便理解我们采取归纳法:找到完整强连通分量后立即染色

    定义\(dfn_u\):表示\(dfs\)中\(u\)的时间戳;初始化为第几个被遍历到的点。

    定义\(low_u\):表示\(u\)能到达且在\(u\)子树边界的未染色的最小时间戳①\((\)设代表该最小时间戳点的点为\(x\),可证明\(x\)一定能与\(u\)组成强连通分量②\()\);初始化为\(dfn_u\)。

    ①:显然代表该最小时间戳的不为\(u\)的子树\((\)除\(u)\),因为子树内的时间戳\(u\)已经为最小的了。故\(u\)的子树并不影响\(low_u\),真正影响的是\(u\)的子树外,与\(u\)子树有接触,且未染色的。

    ②:\((\)下图为例\()x\)位于\(f\)的左子树,\(x\)所在完整强连通内所有节点不止在左子树\((\)否则就染色了\()\),\(x\)至少能与\(f\)组成强连通分量。故\(x\)一定能与\(u\)组成强连通分量:\(f\rightarrow u\rightarrow x\rightarrow f\)。

    具体做法:在\(u\)的子树遍历完后,\(low_u=dfn_u\)则把栈顶到该点的区间染色\((\)与子树外单向联通,那\(u\)的子树未处理部分与\(u\)组成强连通分量\()\),否则要等回到某个祖先后染色才能分量的完整

    code

    也可更换第\(7\)行代码为:

    else if(visit[v]) low[u]=std::min(low[u],low[v]);

    //此时定义low:能与u组成强连通分量(未染色)的最小时间戳

    void Tarjan(LL u){

    dfn[u]=low[u]=++tim; sta[++top]=u; visit[u]=true;

    for(LL i=head[u];i;i=dis[i].nxt){

    LL v(dis[i].to);

    if(!dfn[v]){

    Tarjan(v); low[u]=std::min(low[u],low[v]);

    }else if(visit[v]) low[u]=std::min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

    LL now; ++nod;

    do{

    now=sta[top--]; col[now]=nod; visit[now]=false;③

    }while(now!=u);

    }

    }

    ③:\(visit\)清空:强连通分量是建立在有向图上的,\(u\rightarrow v,v\nrightarrow u\)时,如果之前先遍历过\(v\),则已经把\(visit\)清空了,此时\(u\)不受\(v\)的任何影响

    弱连通分量

    定义:同一弱连通分量里的任意两个点\(x,y\),保证至少一方能到达另一方

    想象一下某个弱连通分量进行强连通缩点后的样子?能两两到达的肯定存在于同一个大点中了,剩下的肯定是单向联通,故一定是一条单直链

    性质:某一点可能属于多个弱连通分量,显然,属于强连通分量的两点一定属于同一弱连通分量

    做法:在强连通缩点后的\(DAG\)图中,每一条链就是一个弱连通分量

    无向图

    为了割点与桥的统一计算,在无向图中我们不管父亲\((\)类似树的遍历,遇到\(f\)则\(continue)\),稍后会说明原因

    且重新定义:

    定义\(low_u\):\(u\)的子树与子树外接触的最小时间戳\((\)除\((u,f)\)的影响,因为在遍历\(u\)时遇到\(f\)会跳过\()\)

    如下图,蓝边为\(dfs\)树,标号为时间戳,\(6\)的子树为\(\{6,7,8,9\}\),子树与子树外的接触为\((6,3),(7,5),(9,2)\),故\(low_6=2\)

    割点

    定义:无向图中,将该点从原图中拿掉后,连通分量数量增加

    想象一下割点在图上的样子:一个点至少夹在两个互不接触 (( 不考虑该点的连接作用 )) 联通块之间

    为了便于理解,先想一下暴力做法④:特判每一个点,如果该点至少有两个儿子则说明为割点\((\)这些儿子所属的子树互不接触,否则仅需遍历一次,而该点位于子树之间,显然割掉后连通块个数=儿子个数\()\)。时间复杂度\(O(nm)\)

    ④:因为判断儿子得把整个子树全跑一遍。而每一次判断的儿子个数仅对根有效。因为根肯定得把一个子树的点遍历完才能回溯;其他的点由于顺序关系,入度也会成为一个儿子\((\)对于无根树\()\),实际上入度上方可能与儿子有接触,故不能一次性判断。比如下面的这幅图,从\(1\)开始遍历则\(3\)有两个儿子;但从\(3(root)\)开始遍历:\(3\longrightarrow 2\longrightarrow 1\longrightarrow 12\longrightarrow 13\longrightarrow9\longrightarrow8\longrightarrow6\longrightarrow7\longrightarrow5\longrightarrow4\longrightarrow10\longrightarrow11\),最后得到的是\(3\)只有一个儿子,所以\(3\)不为割点

    转换成条件:对于\((u,v),fa_v=u\),在割掉\(u\)后,\(v\)的子树与外界无任何接触。也就是\(v\)的子树仅与外界的\(u\)接触,则当割掉\(u\)后,多生成了一个联通分量。

    抽象成代码:\(u\in Articulation Point \longrightarrow low[v]>=dfn[u]\)

    细节:如果我们首先遍历\(u(root)\),则无论怎样\(low_v\)都会\(≥dfn_u(dfn_u=1)\),则根据定义是把\(u\)判断为割点,其实不然⑤。

    ⑤:有时我们发现根不会为割点,这是为什么呢?因为\(u\)的子树就是所有点,故没有外界,也就是说特判一定满足,故该特判对其无效。

    所以需要判断的是\(u\)是否有至少两个儿子\((\)原理就是上面的暴力做法\()\),否则就为无根树上的叶子节点了\((\)也就是边界\()\)

    code

    void Tarjan(LL u,LL mr,LL f){

    LL rc(0);

    dfn[u]=low[u]=++cnt;

    for(LL i=head[u];i;i=dis[i].nxt){

    LL v(dis[i].to);

    if(v==f) continue;

    if(!dfn[v]){

    Tarjan(v,mr,u);

    low[u]=min(low[u],low[v]);

    if(low[v]>=dfn[u]&&u!=mr)

    cut[u]=true;

    if(u==mr)

    rc++;

    }else low[u]=min(low[u],dfn[v]);

    }

    if(u==mr&&rc>=2)

    cut[mr]=true;

    }

    定义:又称为割边,将该边从原图中拿掉后,连通分量数量增加

    想象一下桥在图上的样子:一条边被两个不接触\((\)不考虑这条边的连接作用\()\)的联通块夹在中间。

    如下方,两个"\(+\)点"间的为桥

    为了便于理解,先想一下暴力做法:枚举每一条边\((x,y)\)从\(x\)节点出发不经过该边遍历一次,如果不能到达\(y\)则该边为桥。时间复杂度\(O(m^2)\)

    转换成条件:对于桥\((u,f),fa_u=f\)的,割掉\((u,f)\)后,\(u\)的子树外界无任何接触。也就是除\((u,f)\)外,\(u\)的子树的边仅局限在内部,相当于u的子树被一根线挂在\(f\)节点上。

    抽象成代码:\((u,v)\in Bridge\longrightarrow low[v]>dfn[u]\)

    void Tarjan(LL u,LL f){

    dfn[u]=low[u]=++cnt;

    for(LL i=head[u];i;i=dis[i].nxt){

    LL v(dis[i].to);

    if(v==f) continue;

    if(!dfn[v]){

    Tarjan(v,u);

    low[u]=min(low[u],low[v]);

    if(low[v]>dfn[u]){

    e[++tot][0]=u; e[tot][1]=v;

    }

    }else low[u]=min(low[u],dfn[v]);

    }

    }

    其实割点是可以考虑父亲的影响,而桥绝对不能

    因为\(f\)为割点仅需要考虑\(u\)的子树最多遍历到\(f\),也就是说\((u,f)\)这条边对判断起不到任何影响

    而桥\((f,u)\)需要:除开这条边,\(u\)的子树最多遍历到\(u\)。如果考虑父亲的影响,\(low_u\)一定会受\(dfn_f\)的影响\((low_u=dfn_f)\),特判起来会变得十分麻烦

    故为了代码的方便,在割点割边时不考虑父亲

    边双连通分量

    定义:简写为边双,同一边双内,点与点的边集中无桥

    如下图,每种颜色的点为一个边双,之间由桥隔开

    具体做法

    两次遍历:这个就比较简单了,直接找出所有的桥删掉,然后遍历一遍染色就行了,因为桥已经被全部删掉,故每种颜色的分量的边集中肯定无桥

    一次遍历:桥的定义入手,考虑桥\((f,u)\),\(u\)的子树局限于内部,故满足\(low_u=dfn_u\);而同属\(u\)的边双内的任意点\(x\),由于无桥,肯定不会局限于\(x\)的子树,故满足\(low_x≠dfn_x\)。与强连通分量的做法类似,判断\(dfn_u=low_u\),把压进栈里的点取出来染色即可

    void Tarjan(LL u,LL fa){

    dfn[u]=low[u]=++tim; sta[++top]=u;

    for(LL i=head[u];i;i=dis[i].nxt){

    LL v(dis[i].to);

    if(v==fa) continue;

    if(!dfn[v]){

    Tarjan(v,u); low[u]=std::min(low[u],low[v]);

    }else low[u]=std::min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

    LL now; ++nod;

    do{

    now=sta[top--]; col[now]=nod;

    }while(now!=u);

    }

    }

    点双连通分量

    定义:简写为点双,对于同属一个点双的任意点,删除后,该分量中的点仍能互相到达;或者说仅对于该分量而言,无割点。

    具体做法:

    依旧从割点的定义入手:割点将原图分成互不相连的多个联通块,显然每个联通块本身已经是一个点双了,但不完整,因为相邻的割点在边界,如果与联通块共同组成一个新联通块,割掉后也不会另外产生联通块\((\)相当于该连通块上的叶子节点\()\),所以需要加上来才完整\((\)故割点是会同时存在于多个点双中的\()\)

    我们怎么染色呢?可以发现在\(dfs\)树中,割点\(u\)在进行与儿子节点的染色时会分给多个点双,而在遍历完儿子后,与祖先将仅产生一个完整点双⑥。所以当\(u\)为割点,给儿子节点染色时,取到儿子借点就够了,栈中保留\(u\),等到\(u\)的某个祖先后再取出来。

    新建一个节点来维护某个点双,该点向该点双的每个点连一条边\((\)当然这是建立在新图上的\()\),这就是广义圆方树

    ⑥:如下图

    void Tarjan(LL u){

    dfn[u]=low[u]=++tim; sta[++sta[0]]=u;

    for(LL i=G1.head[u];i;i=G1.dis[i].next){

    LL v(G1.dis[i].to);

    if(!dfn[v]){

    Tarjan(v);

    low[u]=min(low[u],low[v]);

    if(low[v]>=dfn[u]){

    G2.Add(++tot,u); LL now(0);

    do{

    now=sta[sta[0]--];

    G2.Add(tot,now);

    }while(now!=v);

    }

    }else low[u]=min(low[u],dfn[v]);

    }

    }

    我们把每个点双看作一个分量

    分量无割点:说明整个联通块就是一个点双,建两个出口,随便割一个由于点双的性质所有点都能出去

    分量有一个割点:在除割点的地方建一个出口,割掉割点直接去分量里的出口,割掉出口通过割点跑到其他分量的出口中

    再具体点就相当于多个点双构成了一棵树\((\)仅一个节点的树除外\()\),而我们仅在叶子节点建出口

    显然仅割点会对除本身以外的访问有影响,影响为多个分支所跨该割点访问数,

    记分支的节点数分别为\(size_1,size_2,...,size_k\),\(sum=\sum\limits_{i=1}^k size_i,ans=\sum\limits_{i=1}^k size_i\cdot(sum-size_i)+(n-1)*2\)

    其实就是求:多个点双构成的树,\(x,y\)所在节点间的割点

    首先得所属节点不同:\(low_y>=dfn_x\)

    其次得保证\(u\)是位于期间的割点:\(dfn_u<=low_v\)

    且\(u\)的该分支\(v\),\(y\)存在于子树\(v\)内:\(dfn_v<=dfn_y\)

    纯奇环偶环通过dfs树上,染色判断(由于偶环可能有两个奇环,通过一点相交,dfs树上并不能判完)

    两环如果相交必定形成偶环,由于不可以重复经过边,把每个边双提出来判断一下是否存在两个环以上即可

    展开全文
  • 文章目录无向图割点、桥、双连通分量Tarjan算法求割点和桥(割边)代码:边双连通分量 和 点双连通分量代码边双连通分量 和 点双连通分量 的缩点有向图的弱连通与强连通强连通分量Kosaraju算法Tarjan算法代码: ...

    无向图割点、桥、双连通分量

    • 给定无向联通图G=(V,E) • 对于一个点x,若从图中删除x及所有与x相连的边,图不再联通,x是G的割点
    • 对于一条边e,从图中删去e,图不再联通,e的x的割边
    • 一个图如果不存在割点,则它是一个点双连通图,一个图的极大点双连通子图是他的点双连
    通分量。
    • 一个图如果不存在割边,则它是一个边双连通图,一个图的极大边双连通子图是他的边双连
    通分量。

    Tarjan算法求割点和桥(割边)

    时间戳dfn :第n个搜到这个点
    返祖边:搜索树上一个点连向其祖先节点的边
    横插边:搜索树上一个点连向它另一条支链上的点的边----在无向图中不存在
    追溯值low:当前点及其子树的返祖边能连到的dfn值最小的点
    如果<u,v>是搜索树的边:low[u]=min(low[u],low[v])
    在这里插入图片描述
    在这里插入图片描述
    • u点是割点,v是u搜索树上的一个儿子:dfn[u] <= low[v] ——v的子树中没有返祖边能跨越u点;有多个儿子的根节点
    比如图中的点10和点7

    • 边是桥,搜索树上v是u的儿子:dfn[u]<low[v]——v的子树中没有返祖边能跨越<u,v>这条边

    代码:

    void tarjan(int x)//求割点 
    {
    	dfn[x]=low[x]=++cnt;
    	int flag=0;
    	for(int i=head[x];i;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		if(!dfn[v])
    		{
    			tarjan(v);
    			low[x]=min(low[x],low[v]);
    			if(low[v]>=dfn[x])
    			{
    				flag++;
    				if(x!=root||flag>1)book[x]=1;
    				//flag>!说明根有两个以上的儿子 
    			}
    		}
    		else low[x]=min(low[x],dfn[v]);
    	} 
    }
    

    求割边:if(low[v] > dfn[x])

    边双连通分量 和 点双连通分量

    • 把桥删了每个连通块都是一个边双联通分量——标记出桥之后dfs一遍即可
    • 点双连通分量要复杂一些——一个割点可能属于多个双联通分量

    点双连通分量性质:
    任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性,即BCC中无割点
    若BCC间有公共点,则公共点为原图的割点
    无向连通图中割点一定属于至少两个BCC,非割点只属于一个BC

    点双连通分量求法::
    • 维护一个栈
    • 第一次访问某个节点时,将其入栈
    • 当割点判断法则中dfn[x]<=low[y]成立时,不断从栈中弹出节点,直到y被弹出,这些被弹出的点和x一起构成一个点双连通分量

    代码

    #include<cstdio>
    #include<cctype>
    #include<vector>
    using namespace std;
    struct edge
    {
        int to,pre;
    }edges[1000001];
    int head[1000001],dfn[1000001],dfs_clock,tot;
    int num;//BCC数量 
    int stack[1000001],top;//栈 
    vector<int>bcc[1000001];
    int tarjan(int u,int fa)
    {
        int lowu=dfn[u]=++dfs_clock;
        for(int i=head[u];i;i=edges[i].pre)
            if(!dfn[edges[i].to])
            {
                stack[++top]=edges[i].to;//搜索到的点入栈 
                int lowv=tarjan(edges[i].to,u);
                lowu=min(lowu,lowv);
                if(lowv>=dfn[u])//是割点或根 
                {
                    num++;
                    while(stack[top]!=edges[i].to)//将点出栈直到目标点 
                        bcc[num].push_back(stack[top--]);
                    bcc[num].push_back(stack[top--]);//目标点出栈 
                    bcc[num].push_back(u);//不要忘了将当前点存入bcc 
                }
            }
            else if(edges[i].to!=fa)
                lowu=min(lowu,dfn[edges[i].to]);
        return lowu;
    }
    void add(int x,int y)//邻接表存边 
    {
        edges[++tot].to=y;
        edges[tot].pre=head[x];
        head[x]=tot;
    }
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
        }
        for(int i=1;i<=n;i++)//遍历n个点tarjan 
            if(!dfn[i])
            {
                stack[top=1]=i;
                tarjan(i,i);
            }
        for(int i=1;i<=num;i++)
        {
            printf("BCC#%d: ",i);
            for(int j=0;j<bcc[i].size();j++)
                printf("%d ",bcc[i][j]);
            printf("\n");
        }
        return 0;
    }
    

    边双连通分量 和 点双连通分量 的缩点

    • 每个边双连通分量缩成一个点,再用原来的桥把他们连起来
    • 点双联通分量因为一个割点可能包含在多个点双连通分量里面,所以我们将每个割点保留割点与其所在的点双连通分量连边即可。

    有向图的弱连通与强连通

    • 在有向图G=(V,E)中,如果对于任意两点u,v,存在一条从u到v或者从v到u的路径——弱联通
    • 在有向图G=(V,E)中,如果对于任意两点u,v都互相可达——强联通

    强连通分量

    • 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路
    径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。 • 如果有向图G的每两个顶点都强连通,称G是一个强连通图。
    • 有向图的极大强连通子图,称为强连通分量(strongly connected components)。
    在这里插入图片描述

    Kosaraju算法

    • 对原图进行一次dfs(任意起点)
    • 在第一次形成的森林的每一颗树里,以第一次搜索出栈时间的逆序对反图进行dfs,这次搜索A能到达的点和A都在一个强连通分量里面
    在这里插入图片描述

    Tarjan算法

    • Dfn[n]时间戳
    • Low[n]他和他的子树里返祖边和横叉边能连到还没出栈的dfn最小的点
    • 在dfs的时候维护一个栈第一次访问到某个点就将其加入到栈中,当一个点x的dfn[x] == low[x] 时,他就是这个强连通分量里面在搜索树中最高的点,将栈里点出栈直到x也出栈为止,这些点组成一个强连通分量。

    代码:

    void tarjan(int x)
    {
    	dfn[x]=low[x]=++cnt;
    	stack[++top]=x;
    	vis[x]=1;//x是否在栈里 
    	for(int i=head[x];i;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		if(!dfn[v])
    		{
    			tarjan(v);
    			low[x]=min(low[x],low[y]);
    		}
    		else if(vis[v])low[x]=min(low[x],dfn[v]);
    		
    		if(dfn[x]==low[x])//是否是强连通分量最高的点 
    		{
    			ans++;//新强连通的标号 
    			do
    			{
    				int cur=stack[top--];//栈顶的点 
    				vis[cur]=false;
    				num[cur]=ans;
    			}while(x!=cur);
    		}
    	}
     } 
    
    展开全文
  • 英国广播公司(BBC)在报道中称,国际航空运输协会的航空互联互通指数会衡量一个国家的城市世界其他城市之间的连通程度,这对贸易、旅游、投资和经济来说都至关重要。在去年同期的排名中,全球航空连...

    a0a4e6df622ddc8ec6c266edc7a0fb4a.gif

    据国际航空运输协会(IATA)

    发布的最新消息

    成都为继上海、北京、广州之后

    全球航空连通性最强的第四大城市

    国际航空运输协会是一个由世界各国航空公司所组成的大型国际组织。此次发布的榜单引起了全球广泛关注。英国广播公司(BBC)在报道中称,国际航空运输协会的航空互联互通指数会衡量一个国家的城市与世界其他城市之间的连通程度,这对贸易、旅游、投资和经济来说都至关重要。

    在去年同期的排名中,全球航空连通性排名前十位的城市,分别为伦敦、上海、纽约、北京、东京、洛杉矶、曼谷、香港、首尔、芝加哥。然而,今年发生的新冠肺炎疫情,给航空运输业带来了巨大冲击和影响,打破了世界航空运输格局,全球航空连通性前十强城市排名也遭遇重新洗牌,分别为上海、北京、广州、成都、芝加哥、深圳、洛杉矶、伦敦、达拉斯、亚特兰大。其中,成都今年逆势冲进了“全球前十强”且排名靠前。

    今年以来,尽管遭遇疫情全球蔓延的冲击和挑战,但是成都始终坚持“严防控”和“保畅通”两手抓,保障国际航空运输链畅通,双流国际机场生产运输业务在国内率先触底反弹,先后创下了“全球第一”和“全国第一”:今年5月双流国际机场客运航班起降架次跃升至全球第一,成为全球最为繁忙的机场今年上半年机场旅客吞吐量位列全国第一,成为国内最具人气的机场。

    而到今年9月份,双流国际机场的起降架次、旅客吞吐量、货邮吞吐量三大主要生产指标,首次实现自疫情以来的正增长,各项业务快速恢复,为复产复工提供强力支撑,进一步助力畅通“双循环”。

    数据逆势变化的背后,彰显出一座城市的发展韧性和活力,也与践行新发展理念密不可分。近年来,成都不断扩大对外开放,加快建设国际门户枢纽,加速推进国际航空供应链体系建设。成都的国际(地区)航线数量增至129条,航线规模位列中国内地第四、中西部第一。在“双循环”战略中,成都作为国内大循环的战略腹地、国际大循环的门户枢纽的地位日益凸显。

    与之相呼应的是,今年8月由全球化与世界城市研究网络(GaWC)发布的2020年世界城市榜单,成都位居世界二线强城市(Beta+)榜第9位,较2018年上升了7位,成为唯一入选Beta+榜的中国城市,而在世界城市整体排名中,成都的排名跃升至全球第59位。GaWC的世界城市排名,除了国际性、国际影响力等众多指标依据外,全球通达性——拥有重要的国际机场,作为国际航线的中心;拥有先进的交通系统,提供多元化的运输模式,则是参考的另一个重要依据。


    来源| 成都日报锦观成都发布编辑|古月扫码进群

    145d184ed9ccf129d9fe9a6688a100ae.png

    为成都点赞!

    展开全文
  • 随着我国经济结构的进一步调整优化,第三产业在我国经济结构中所占的比重也越来越大。许多金融、互联网行业的企业扩张意愿较,员工数量迅速增长。因此,写字楼作为办公的商用场所,潜在需求较大,随着哈尔滨新区...
  • 题目的意思是:总学校分发软件,每个学校得过软件后,可以通过单向网络分发软件,求(1)最少的软件分发数;(2)添加最少的线路,使发放到任意的学校就可以让所有... 1、弱连通图没有出度为0或入度为0的点必为强连通图 
  • 摘要:本文介绍了国外某家世界500企业工厂在例行检验中接地检查控制不使用接地电阻测试仪的案例。“例行检验制造厂商可以采用一种更合适其生产计划的试验程序,而且可以在生产过程中适当的阶段进行试验,只要能...
  • 连通性概念总结

    2020-11-07 14:55:12
    强连通图、连通图、单向连通图三者之间的关系是,强连通图必然是单向连通的,单向连通图必然是弱连通图。 无向图的连通性 连通图是无向图的一个概念: 在无向图中,若从顶点 v1v_1v1​ 到顶点 v2v_2v2​ 有路径,...
  •  强连通弱连通的概念只在有向图中存在。  强连通图:在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。  弱连通图:将有向图的所有的有向边替换为无向边,所...
  • 传统的信号恢复方法在噪声背景下具有较大的局限性,有用的信息往往淹没在噪声背景下不易被识别。针对这个难点,提出一种基于三维曲波变换的信号恢复的方法。该方法将三维曲波变换和自适应滤波器相融合,从而...
  • 基本图论-连通分量

    2019-02-19 14:11:00
    本文涉及强连通分量、弱连通分量、割点、割边、边双、点双,属于基本图论范畴 在有着直接关联的基础上又有所不同,本文基于把抽象的数组转换为在图上的意义,旨在让初学者能更轻松地理解并区分差别 为避免各个板子的...
  • 结果表明:华池组(K1h)洛河组(K1l)下段富水性,洛河组(K1l)上段富水性中等,洛河组(K1l)中段或中上段富水性;华池组含水层富水性较洛河组含水层得多,两含水层不存在明显的水力联系;洛河组(K1l)中上段之间的水力...
  • 强连通图:有向图G中,对于任意的两个点之间x,y,都存在x到y的路径,为强连通图; 弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是若连通图; ...
  • 数据结构算法学习笔记——图 C++实现1 概念2 图的表示方法3 算法拓扑排序图的搜索算法广度优先搜索(BFS)深度优先搜索(DFS)(单源)最短路径...连通图、强连通图、基础图、弱连通图、完全图(完全图一定是连通图
  • Rosen8.1 概述表 8-18.2 图的术语8.3 图的表示和图的同构8.3.3 邻接矩阵8.3.4 关联矩阵8.4 连通性8.4.4 有向图的连通性强连通弱连通强连通分支8.5 欧拉通路哈密顿通路8.6 最短通路问题8.7 可平面图 ...
  • 链接 ...相关知识 有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径之关联...如果不考虑图中存在回路,那么每条路径就是一个弱连通子集. 对于一个路径覆盖,有如下
  • * * 1设无向图G的关联矩阵为 则G的顶点数边数分别为_ (A)4, 5 (B)4, 10 (C)5, 4 (D)5, 10 2有向图的连通性可分为弱连通强连通_
  • 强连通弱连通 子图 条件过滤 pred,succ NetworkX是一个用Python语言开发的图论复杂网络建模工具,内置了常用的图复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。networkx支持创建简单...
  • python复杂网络分析库NetworkX阅读目录无向图有向图加权图经典图论算法计算强连通弱连通子图条件过滤pred,succNetworkX是一个用Python语言开发的图论复杂网络建模工具,内置了常用的图复杂网络分析算法,可以...
  • [Luogu5241]序列(DP)

    2019-03-05 14:14:00
    固定一种构造方法,使它能够构造出所有可能的序列。...a[i-1],那么连一条从后往前的边让若干点1所在强连通快合并。显然这样可以得到所有可能的序列。 于是前一部分“连弱连通块”用f[i][k][x]表示前i...
  • 读数据结构算法分析 坑!待填! 若干定义 一个图G = (V , E)由顶点集V和边集E组成...具有这样性质的有向图称为强连通,如果不是强连通的,但它的基础图是连通的,则称为弱连通 图的表示 领接矩阵 - 使用一个...
  • luogu1726 上白泽慧音

    2018-07-29 12:05:00
     求一个有向图含节点数最多且结点编号从小到大排列字典序最小的强连通分量。 注意事项  HDU1269那道题题面、数据太,在这道题上把我害惨了。。。 Dfs点u时,如果u相连的一个点v有DfsN,v必须在栈内我们...
  • 研究结果表明:储层具有—中等偏速敏、中等偏水敏—中等偏水敏、—中等偏盐敏、碱敏性波动范围大、酸敏程度低的特点,且水敏黏土矿物和砂岩物性有关,物性越好,孔隙连通性越好,水敏程度越高。根据储层...
  • 图论学习

    2019-10-02 20:58:39
    基本图论-连通分量(tarjan/联通 割点/边 边/点双) 刷题 提前声明 有一些题目我会写代码,并且挂上去。 有些不会(懒) 题目 P3387 模板 + topo排序 + 超级简单DP 。如果不会topo排序的赶紧去学一下吧 推荐blog...
  • 图论的基础 小白笔录

    2020-08-01 14:56:23
    图的遍历与连通性+图的存储(邻接矩阵) 洛谷 图的遍历 很基础的一个遍历,不过好像不能用正序找最大值,会爆内存,要用倒序,比如点1到点4,那么我们从4遍历,只要4联通的都是4最大 拓扑排序 最大食物链计数 ...
  • 该矿煤系地层底板为茅口组灰岩,岩溶发育,富水性,为煤层的直接充水含水层。依据地表水和地下水的水质特征,结合连通试验,分析了矿区地表水和地下水的补给关系,并讨论了地下水水质的成因及其对茅口组灰岩岩溶发育的...
  • 决策树采用的是CART分类回归数,通过组合各个决策树的分类器,构成一个最终的分类器,在构造决策树的时候采取随机数量的样本数和随机的部分属性进行子决策树的构建,避免了过分拟合的现象发生。详细介绍链接 KDTree...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

强连通与弱连通