| 查看: 1160 | 回复: 6 | ||
[求助]
求解关于图论里的无向图的连通判断问题。。。 已有2人参与
|
|
一个n个顶点的图，我们知道如果他是完全图的话，就有n（n-1）/2条边。。现在，请问最坏情况下，需要询问多少次某条边是否存在，才能判断这个图是否为连通的？？ （如果询问n（n-1）/2次的话，当然能够判断这个图是否为连通，因为所有边都被询问了一次，我们能够知道这个图的连接状况。我现在想知道能否减少询问次数，即使在最坏情况下） |
回复此楼» 猜你喜欢
354求调剂
已经有9人回复
-
化学工程321分求调剂
已经有22人回复
-
考研调剂
已经有3人回复
-
326求调剂
已经有8人回复
-
333求调剂
已经有7人回复
-
一志愿东华大学控制学硕320求调剂
已经有3人回复
-
考研化学学硕调剂，一志愿985
已经有7人回复
-
0703化学调剂
已经有15人回复
-
0703化学调剂 ，六级已过，有科研经历
已经有14人回复
-
326求调剂
已经有4人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 呼唤图论高手！关于图论中子图间连通度的问题。
已经有4人回复
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1016.9
- 散金: 376
- 红花: 18
- 帖子: 742
- 在线: 245.1小时
- 虫号: 1324155
- 注册: 2011-06-16
- 专业: 拓扑学
2楼2015-04-22 12:55:58
3楼2015-04-22 19:12:06
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1016.9
- 散金: 376
- 红花: 18
- 帖子: 742
- 在线: 245.1小时
- 虫号: 1324155
- 注册: 2011-06-16
- 专业: 拓扑学
4楼2015-04-22 20:34:32
5楼2015-04-22 21:39:01
【答案】应助回帖
|
下面的表述中所谓的边，只是一组节点对，是一个可能需要询问的位置，并不是表示真实存在这个边。如果不存在边，将该点对称之为空边。 （构造法）考虑这个图是一颗树的情况。如果想知道图是否连通，必然需要将树的所有边都询问到，否则，当询问到其他可能的边时，返回边不存在的结果，我们总是无法得到连通这一结论。也许存在某种情况，我们根据已询问得到的信息，去决定下一步的询问。下面说明，无论怎样询问，必然存在一颗树，我们必须要到最后的时刻才能得到这颗树。 证明：不妨认为存在某种询问的序列，使得我们可以更早地得到树的信息，不妨令该序列某次询问是询问某个树边e，该次询问是第k次询问（之前是否询问到了树边无关紧要）。 显然在第k次询问之前已得到的树边构成了一个森林（包含那些孤立的节点），则第k次所询问的树边将其中两个森林合二为一，此时分两种情况： （1）在第k次询问之前，我们已经询问过了除边e之外所有这样的边，这些边横跨了这两颗树（这些边必为空边） 这种情况下，我们已经作了非常多的询问，即使在最好的情况下，我们在询问到树的每个边时，都遇到了这种情况，我们仍然无法得到连通的信息。简单说，当我们最后一次询问到了树的某个边，仍然是这种情况，意味着我们已经询问了其他所有可能的边，因为任何一个空边(a,b)，必然存在之前的某个时刻，节点a和b分属于两颗不同的树（该时刻这两颗树刚好需要合并）。 （2）存在某个横跨树的边，我们之前没有询问过。不妨令第k次询问的边为e1，这个之前没问过的边为e2。对于最终的这颗树（即真实存在的树，当前我们还看不到，假设我们有透视眼），e1是某个树边，e2是空边（即不存在边）。现在我们篡改这颗树，将e1和e2的位置互换，即e2是树边，e1是空边。注意，这样的篡改并不会影响之前询问的结果，篡改后仍然是一颗树，故未知的这颗树总是可以和我们对着干，随意地改变它的结构。篡改之后，我们就询问到了一个空边，只有再次发出询问，才能得到更多信息。不断询问的结果就是，每次新得到一个树边，总是要达到情况1；总是得到情况1的结果就是，我们必须要询问到最后一刻。 结论：最坏情况下，我们需要询问所有可能的边，即n(n-1)/2次询问。 |
6楼2016-01-06 19:01:14
7楼2016-01-06 20:34:33
40