最大独立集和最大团
2018-09-16 本文已影响0人
lvanzn
给你一个无向图G,
G的最大独立集是G中两两顶点之间都不相连的最多个数的集合。
G的最大团书G中两两顶点之间都相连的最多个数的集合。(完全图)
1.最大独立集不是唯一的.
2.性质:无向图的最大团==该无向图补图的最大独立集
什么是无向图的补图?
无向图和补图.GIF
给你一个无向图G,
G的最大独立集是G中两两顶点之间都不相连的最多个数的集合。
G的最大团书G中两两顶点之间都相连的最多个数的集合。(完全图)
1.最大独立集不是唯一的.
2.性质:无向图的最大团==该无向图补图的最大独立集
什么是无向图的补图?