24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

dameng

银虫 (小有名气)

应助: 23 (小学生)
金币: 476.3
红花: 4
帖子: 224
在线: 481.8小时
虫号: 280996
注册: 2006-09-23
性别: GG
专业: 计算机软件

[求助] 呼唤图论高手！关于图论中子图间连通度的问题。

一个图可以包括多个连通分量（就是连通分支）；每个连通分量又可以包括多个双连通分量（即其中任两点间至少存在两条没有共同边的路径，即边不相交），这些双连通分量之间形成树的结构（如果两个双连通分量间有边当且仅当原图中存在一条边，边的两个端点分别在这两个双连通分量内）；每个双连通分量又包括多个三连通分量，这些分量之间形成图的结构（边连通度为2的图，允许重边）；三连通分量又可以继续分下去，分成4连通分量，5连通分量等...当然最后会分到底，比方说8连通分量，之后就再也分不下去了，因为其中没有9连通分量。

我的问题是，对于这种层次化结构，应该已经有人提出过，是否有过研究，或者某些已有的概念等？希望图论牛人能帮帮我！

PS：上面是边连通度，这样可以保证同层次的分量间没有重叠节点。如果换成点连通度，这个...好像没什么意义吧。我是搞算法的，所以如果数学研究上没什么意义，算法上可能会有，希望大家帮忙，谢谢！

PPS：k层次内，两个k连通分量间不可能有公共节点，它们之间也不可能存在≥k条边不相交路径，因此我觉得对分量的划分是唯一的，应该没什么问题。

[ Last edited by dameng on 2013-3-25 at 21:05 ]

回复此楼