柯尼希定理 (图论)

图论中, 柯尼希定理是指二部图的最大的匹配数与最小的顶点覆盖数相等。该定理以犹太裔匈牙利数学柯尼希·德纳什英语Dénes Kőnig的名字命名。1931年,匈牙利数学家艾盖瓦里·耶内独立发现了该定理在加权图的情形下更一般的形式。

例如,在图中的二部图中,最大匹配(蓝边)和最小顶点覆盖(红点)数均为 6。

匹配与覆盖

图的顶点覆盖是指它的一个顶点集,该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖,则称其为最小顶点覆盖。[1]

图的匹配是指一个边的集合,每两条边都没有公共顶点。一个匹配称为最大匹配,如果不存在一个边数更多的匹配。[2]

对于匹配的每一条边,顶点覆盖中至少有一个顶点为此边的端点,因此任何顶点覆盖集的元素个数都大于等于所有匹配集的元素个数。柯尼希定理表明对于二部图,这两个集合元素大小相同。

定理的陈述

在任意二部图中,最大匹配的边数等于最小顶点覆盖的顶点数。 [3]

证明

 
如图粗线代表匹配 M,红点代表集合 U

 是一个最大匹配,因为顶点覆盖大于等于匹配集的大小,因此我们只需构造一个大小为 的顶点覆盖。构造如下:

将二部图的两部分分别记为 AB。一个图关于匹配 M交错路(alternating path)是指一条从图中一个非匹配顶点出发,边在匹配集 M  中交错出现的道路。[4]取顶点集 U 如下:对于 M 的每条边,如果存在一条交错路终止于该边在 B 中的端点,那么该端点属于 U,否则该边在 A 中的端点属于 U。因为 U 里每一个顶点都与 M 的一条边一一对应,所以 。因此我们只需要证明 U 为一个顶点覆盖。

假设有一条边 ab 没有被 U 覆盖,即  都不在 U 中。如果 a 不是某一匹配的端点,那么 ab 本身就是一条从非匹配顶点出发的交错路,那么 ,矛盾。如果 a 属于某个匹配 ab',那么 。这样, 就是一条交错路,从而 ,矛盾。


参考文献

  1. ^ Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
  2. ^ Bondy & Murty (1976), p. 70.
  3. ^ Bondy & Murty (1976), Theorem 5.3, p. 74; Cook et al. (2011).
  4. ^ Diestel, Reinhard. 图论 Graph Theory. 由于, 青林翻译. 北京: 科学出版社. 2020: 32. ISBN 978-7-03-064807-5. 

参考