首页 > 其他 > 详细

关于无向图的最大团的问题。

时间:2020-06-03 21:25:51      阅读:73      评论:0      收藏:0      [点我收藏+]


今天观摩别人代码的时候,出现了求无向图最大团。

描述:团就是最大完全子图。(极大团)

给定无向图G=(V,E)。如果U包含于V,且对任意u,v属于U且有(u,v)属于E,则称U是G的完全子图。

G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中,即U就是最大完全子图。

G的最大团是指G中所含顶点数最多的团。(团中的顶点两两互连

// 最大团: V中取K个顶点,两点间相互连接

// 最大独立集: V中取K个顶点,两点间不连接 

// 最大团数量: 补图中最大独立集数

https://www.cnblogs.com/smartwhite/p/9588768.html

 

 

问题描述:团就是最大完全子图。

给定无向图G=(V,E)。如果U技术分享图片V,且对任意u,v技术分享图片U 有(u,v) 技术分享图片 E,则称U 是G 的完全子图。

G 的完全子图U是G的团当且仅当U不包含在G 的更大的完全子图中,即U就是最大完全子图。

G 的最大团是指G中所含顶点数最多的团。

例如:

       技术分享图片     技术分享图片          技术分享图片         技术分享图片

                 (a)                                        (b)                             (c)                            (d)

图a是一个无向图,图b、c、d都是图a的团,且都是最大团。

关于无向图的最大团的问题。

原文:https://www.cnblogs.com/qiu-hua/p/13040124.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!