最大独立集和最大团

2018-09-16  本文已影响0人  lvanzn

给你一个无向图G,
G的最大独立集是G中两两顶点之间都不相连的最多个数的集合。
G的最大团书G中两两顶点之间都相连的最多个数的集合。(完全图)
1.最大独立集不是唯一的.
2.性质:无向图的最大团==该无向图补图的最大独立集

什么是无向图的补图?


无向图和补图.GIF
上一篇下一篇

猜你喜欢

热点阅读