拉姆齐定理
在組合數學上，拉姆齐定理（），又称拉姆齐二染色定理，斷言對任意正整數k和l，若一個聚會的人數n足夠大，則無論相识關係如何，必定有k个人相识或l个人互不相识。給定k, l時，保證前述結論的最小n值稱為拉姆齊數R(k,l)，其值取決於k, l。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的k階完全圖或藍色的l階完全圖。 拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文證明此定理…
标签：#图论定理
共 17 篇文章
最大流最小割定理
最大流最小割定理是最优化理论的定理。根据该定理，在一个网络流中，从源点到汇点的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。 定义 最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。 图 设 G…
霍爾婚配定理
数学上，霍爾婚配定理（）是菲利浦·霍爾最先證明的圖論定理，又稱霍爾定理，描述二分图中，能將一側全部頂點牽線匹配到另一側的充要條件。定理另有一個等價的組合敍述，確定一族有限集合在何種充要條件下，可自每個集合各揀選一個元素，而使所選元素兩兩互異（即沒有元素是重復的）。 集族表述 設 S 為 X 的有限子集組成的有限多重族。 S 的一個'是 S 至 X 的單射，且該單射 f 將族中任意集合 s\in S 映至該集合的某元素 f(s)。換言之，…
奥尔定理
奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。 内容 设 为（有限的）简单无向图，其顶点数 。 奥尔定理表明，如果对每对 中的不相邻顶点对 和 ，均有 那么 是哈密顿图。 式中， 表示 中顶点 的度数（即与 相连的边数）。 证明 ，但…
Vizing定理
Vizing定理是圖論中的定理。它描述了邊著色數與度的關係。 定理陳述 Vizing定理：任意(簡單, 無向)圖 G 的邊著色數 (edge chromatic number, χ′(G)) 等於 Δ(G) 或 Δ(G) + 1，其中 Δ(G) 指圖 G 中最大的度。 分類法 由Vizing定理可知χ′(G)=Δ(G) 或 Δ(G) + 1。若為前者，稱G為第一類圖(Class 1)，否則稱為第二類圖 (Class 2)。雖然只有兩類，…
五色定理
五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比四色定理弱，也比四色定理更容易证明。1879年，给出了四色定理的一个证明，当时为人所接受，但11年后，珀西·约翰·希伍德却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。 证明 以下是对五色定理的证明。 给定n阶平面图G，我们对G的阶数进行归纳证明。 当n\leq 5时，正确性显然。 …
门格尔定理
在图论中，门格尔定理（）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一，刻畫了连通性的性质。该定理可由最大流量小割定理推广，后者是带权重的边版本，并且是線性規劃的强对偶性定理的一个特例。 邊連通度 門格爾定理的邊連通度版本敘述為：設 G 是個有限无向圖，x 和 y 是其中兩個不同的頂點。則 x 和 y 之間的最小邊割集元…
塔特定理
分解成三個奇元件，故塔特定理推出此圖沒有完美匹配。（定理中，取U為僅含該頂點的一元集。）]] 在图论中，塔特定理（）是： 图 G = (V, E) 有匹配，当且仅当 \text{odd}(G - U) \leq |U|。 其中 U \subseteq V、\operatorname{odd}(H)是图H的奇数元件的数量（有奇数个頂點的连通元件）。 相关 塔特–柏格公式是塔特定理的推广 该定理也是赫尔婚姻定理的推广（二分图） 阅读 参考文…
完美图定理
在图论中，完美图定理（由洛瓦兹·拉兹洛证明）断言：一个无向图是完美的当且仅当其補圖也是完美的。这个结论一度是提出的猜想。它有时也被称为弱完美图定理，以和强完美图定理作区分。强完美图定理通过禁止导出子图来刻画完美图。 定理叙述 一个完美图是具有下述性质的无向图：在其每个导出子图中，最大团的顶点数都等于对该导出子图的着色的颜色数的最小值。完美图包括了很多重要类型的图，例如二分图、弦圖和。 一个图的补图在某两个顶点之间连一条边当且仅当原图在这…
库拉托夫斯基定理
G(9,2)中包含K3,3的细分，说明广义佩特森图不是平面图。]] 库拉托夫斯基定理（）是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作。 进一步阐述 平面图（planar graph）是可以画在平面上，使得不同的边在除了…
艾狄胥-斯通定理
中，埃尔德什－斯通定理（）是禁止某子圖H出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許H為完全圖的情況）。定理由埃尔德什·帕尔與於1946年證明，因而得名。稱其為「極值圖論的基本定理」。 圖蘭圖的極值函數 先定義極值函數（）\mathrm{ex}如下：\mathrm{ex}(n; H)是眾多n個頂點的圖之中，不包含子圖（同構於）H的圖的邊數最大值。圖蘭定理斷言，當H取為完全圖K_r時，有\mathrm{ex}(n; K_r) = t…
艾狄胥－波沙定理
在圖論中，艾狄胥－波沙定理（）由保羅·艾狄胥與 Lajos Pósa 於 1965 年證明
柯尼希定理 (图论)
中，最大匹配（蓝边）和最小顶点覆盖（红点）数均为 6。]] 在图论中， 柯尼希定理是指二部图的最大的匹配数与最小的顶点覆盖数相等。该定理以犹太裔匈牙利数学的名字命名。1931年，匈牙利数学家艾蓋瓦里·耶內独立发现了该定理在加权图的情形下更一般的形式。 匹配与覆盖 图的顶点覆盖是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。 图的匹配是指一个边的集合，每两条边都没…
布鲁克斯定理
图论中，布鲁克定理（） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 背景 图染色数 考慮為G的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。 对于图G，如果存在一个k种颜色的恰当染色方案，…
四色定理
四色定理（），又稱四色地圖定理（），是一个数学定理：如果在平面上劃出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是：每个无外飞地的地图都可以用不多於四种颜色来染色，而且不會有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的圆形中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是邻接区域。 “是否只用四…
曲面染色
曲面染色是图论中的问题，是继四色定理之后的问题延续，奇怪的是问题的解决反而在四色定理之前，这个与庞加莱猜想有相似的情况（高维反而最先解决，低维反而更加困难）。 什么是曲面染色 通常所说的地图染色，一般是指在平面上染色，或者在球面上染色，每一个染色区域都是单连通的。而曲面染色是指在一个有洞的物体上划分若干个区域，有一个洞的叫做环面，又叫亏格1的曲面。有两个洞的油饼形状叫做亏格2的曲面。 问题提出与解决 英国数学家彭西·希伍德在1890年首…
瓦格纳定理
的图子式 (彩色小圆圈和黑色边，删除红色顶点，收缩每个黄色圆圈内的边)。]] 在图论中，瓦格纳理论（）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。 这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。 库拉托夫斯基定理的关系 瓦格纳1937年发表了证明。 库拉托夫斯基以前1…