二分图相关定理

二分图的最小顶点覆盖

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

定理:二分图最小顶点覆盖 == 二分图最大匹配数

二分图的最大独立集

定义:选出一些顶点使得这些顶点两两不相邻,则这些点构成的集合称为独立集。最大独立集为包含顶点数最多的独立集。

定理:最大独立集 = 所有顶点数 - 最小顶点覆盖

二分图的最大团

定义: 团:选出一些点,使其两两之间都有边。 最大团:点数最大的团

定理:二分图的最大团 = 补图的最大独立集

感性理解:最大独立集为两两之间没有边,那么补图的最大独立集说明在原图中两两之间有边,那么就是原图的最大团

参考:

http://www.cnblogs.com/jianglangcaijin/p/6035945.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏温安适的blog

最小生产树Prim和Kruskal

47512
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

1732
来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3465
来自专栏数据结构与算法

cf633F. The Chocolate Spree(树形dp)

\(g[i]\)表示以\(i\)为根的子树中从\(i\)到叶子节点 加上一条与之不相交的链的最大值

1122
来自专栏灯塔大数据

每周学点大数据 | No.27高维外存查找结构——KD 树

No.27期 高维外存查找结构——KD 树 Mr. 王:以往我们在数据结构中进行的查找,都是查找某一个键值或者某一个区间内的值,这样的查找称之为一维查...

3848
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3435
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

3485
来自专栏数据结构与算法

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

38111
来自专栏小樱的经验随笔

hihoCoder #1142 : 三分求极值

#1142 : 三分·三分求极值 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 这一次我们就简单一点了,题目在此: ? 在直...

3509
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2644

扫码关注云+社区

领取腾讯云代金券