完全图与强连通图的那些坑

前言

图这个数据结构相比队列、栈、树来说算是复杂多了,关于图的问题也多如牛毛,先来看一下常见的问题:

若无向图 G 中含7个顶点,要想保证图 G 在任何情况下都是连通的,则需要的边数最少是几条?

回答这种问题一定要注意细节,找到关键的点,不然一定会掉到坑里的。这个题关键点有以下几个:

  • 7个顶点
  • 任何条件下连通
  • 最少几条边

其中第1点和第3点不容易出错,比较容易出现问题的是第2点,要想保证任何条件下连通,意思给定边数以后无论怎么连都能通?

先说下答案是16,至于为什么,我们后面先复习一下图相关的概念再慢慢解释,因为此刻的我连什么是强联通图都忘了~

一些概念

  • :是由顶点V集和边E集构成,边表示了与之相连的两点间的关系,因此图可以表示成G = (V, E)
  • 有向图:是指图中的两个顶点从A到B和从B到A的含义是不同的,我们认为两点的关系是有方向的,则称其为有向图
  • 无向图:是指两点间的连接线无方向无关,这种图叫做无向图
  • 连通性:从图中一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的
  • 连通图:在无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图
  • 完全图:在无向图中,如果任意两个顶点之间都边直接相连,则称此无向图为完全图
  • 连通分量:若无向图不是连通图,但图中存在某个子图符合连通图的性质,则称该子图为连通分量
  • 强连通图:在有向图中,若任意两个顶点之间包含至少来回两条通路,则称此有向图为强连通图
  • 有向完全图:在有向图中,如果任意两个顶点之间都有相反的两条弧直接相连,则称此有向图为有向完全图
  • 强连通分量:若有向图不是强连通图,但图中存在某个子图符合强连通图的性质,则称该子图为强连通分量

关于题目的解释

这是一个无向图,要想在任何情况下都连通,那考虑极端情况就是孤立一个顶点,让尽可能多的边连接剩余的顶点,那会构成一个 n-1 个顶点的完全图,然后再考虑加一条边把剩下的孤立顶点连起来,这样得到的边数是 N = 5+4+3+2+1 + 1 = 16,用组合数表示就是

$$
C^2_{n-1} + 1= (n-1) * (n-2) / 2 + 1
$$

题目变型

  • 若无向图 G 中含7个顶点,要想保证图 G 在是连通的,至少需要几条边?

    答案6条,即 (n-1)

  • 一个包含7个顶点的无向图 G 为完全图,那么它共有几条边?

    答案21条,即 n * (n-1) / 2

  • 若有向图 G 中含7个顶点,要想保证图 G 在是强连通的,至少需要几条弧?

    答案7条,即 n,也就是形成一个环

  • 一个包含7个顶点的有向图 G 为完全图,那么它共有几条弧?

    答案42条,即 n * (n-1)

补充两个图例

  • 完全图,特点是任何两个顶点都有直接的边相连
1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph TB
A((A))---B((B));
A((A))---C((C));
A((A))---D((D));
A((A))---E((E));

B((B))---C((C));
B((B))---D((D));
B((B))---E((E));

C((C))---D((D));
C((C))---E((E));

D((D))---E((E));
  • 强连通图,任意两点间都有路径可达
1
2
3
4
5
6
7
8
graph TB
A((A))-->B((B));
B((B))-->C((C));
C((C))-->D((D));
D((D))-->E((E));
E((E))-->A((A));
A((A))-->F((F));
F((F))-->A((A));
Albert Shi wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客