24小时热门版块排行榜

返回列表

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

hotydzy

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 126.3
帖子: 22
在线: 13.9小时
虫号: 1952585
注册: 2012-08-23
专业: 通信理论与系统

[求助] 无向图中最大独立节点集的节点数目

请教数学专业图论高手！
如题，本人是工科研究生一枚，目前碰到一个问题是关于无向图的最大独立节点集问题。我的问题不是经典的寻找最大独立节点集，而是只想知道图的最大独立节点的数量与图的节点数量的关系。我感觉不同的拓扑，对应的关系应该是不一样的，那么对应不同的拓扑（树，环。。或者以图的度分类等）有没有经典的理论结论？
希望我表达清楚了，不胜感激！！

回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:

ANSYS能不能同时把节点号、节点坐标、结果list出来，在一个txt里显示已经有7人回复
向大神求助：ansys节点周向位移的施加已经有14人回复
为什么ANSYS后处理list节点应力，节点不全已经有13人回复
cytoscape节点属性设置已经有6人回复
ssh上选定特定节点进行计算的命令已经有6人回复
请问大家什么是邻居节点，什么是竞争节点？已经有3人回复
北京自然科学基金时间节点已经有10人回复
请教VC++6.0 中CTreeCtrl，如何遍历树某个节点下面所有节点？已经有4人回复
SSH登录服务器节点问题！已经有3人回复
求教：ssh 登录集群某节点时不能进入home目录已经有9人回复
国科金评审流程及时间节点控制已经有32人回复
集群上面的节点需要定时间的重启吗？已经有18人回复
rsh无密码节点间互访已经有19人回复
为什么老死节点已经有10人回复
如何限定微机终端可使用的集群节点数已经有11人回复
一句话翻译：指定固定数目的节点并分配优先级已经有7人回复
【求助】关于服务器多节点并行利用效率问题已经有10人回复

1楼 2013-07-16 22:07:59

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

hotydzy

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 126.3
帖子: 22
在线: 13.9小时
虫号: 1952585
注册: 2012-08-23
专业: 通信理论与系统

引用回帖:

3楼: Originally posted by dameng at 2013-07-17 19:53:16
帮你翻了翻书，这有个结论不知道能不能用上：
一个贪心算法用迭代过程构造一个较大的独立集S，它每次迭代从剩下的图中选择度最小的一个顶点添加到S中，并把该顶点及其相邻顶点从图中删除。证明：该算法产生的独立集 ...

不同的贪婪算法会有不同的界，但是我想要的是与算法无关的，即理论界。
我网上找的最相近的结果：
Let $\alpha \left( G \right)$ be the size of the largest independent set in a graph G, and $\chi \left( G \right)$
the chromatic number of G.
Theorem: $\alpha \left( G \right)\chi \left( G \right)\ge \left| G \right|$ .

虽然与着色数有关系，但是着色数本身很难得到，这一结论意义不大。。。
找了些书，也可能这问题本身与图的拓扑关系很大，所以有意义的结论还没找到。

不过还是感谢了！