拉姆齐定理
在組合數學上，拉姆齐定理（），又称拉姆齐二染色定理，斷言對任意正整數k和l，若一個聚會的人數n足夠大，則無論相识關係如何，必定有k个人相识或l个人互不相识。給定k, l時，保證前述結論的最小n值稱為拉姆齊數R(k,l)，其值取決於k, l。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的k階完全圖或藍色的l階完全圖。 拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文證明此定理…
标签：#图染色
共 10 篇文章
五色定理
五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比四色定理弱，也比四色定理更容易证明。1879年，给出了四色定理的一个证明，当时为人所接受，但11年后，珀西·约翰·希伍德却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。 证明 以下是对五色定理的证明。 给定n阶平面图G，我们对G的阶数进行归纳证明。 当n\leq 5时，正确性显然。 …
库拉托夫斯基定理
G(9,2)中包含K3,3的细分，说明广义佩特森图不是平面图。]] 库拉托夫斯基定理（）是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作。 进一步阐述 平面图（planar graph）是可以画在平面上，使得不同的边在除了…
布鲁克斯定理
图论中，布鲁克定理（） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 背景 图染色数 考慮為G的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。 对于图G，如果存在一个k种颜色的恰当染色方案，…
色临界图
數學分支圖論中，色临界图或臨界圖（）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。 定义 如果图G的任意一个真子图G'\subset G，其色數均满足\chi(G')，则称G为\chi(G)色临界图（）。 相关定义 图染色数 对于给定的图G，存在k种颜色和一种染色方案，将图中G每一个顶点都染成k种颜色中的一种。如果染色方案满足一下条件，那么将称该…
四色定理
四色定理（），又稱四色地圖定理（），是一个数学定理：如果在平面上劃出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是：每个无外飞地的地图都可以用不多於四种颜色来染色，而且不會有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的圆形中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是邻接区域。 “是否只用四…
曲面染色
曲面染色是图论中的问题，是继四色定理之后的问题延续，奇怪的是问题的解决反而在四色定理之前，这个与庞加莱猜想有相似的情况（高维反而最先解决，低维反而更加困难）。 什么是曲面染色 通常所说的地图染色，一般是指在平面上染色，或者在球面上染色，每一个染色区域都是单连通的。而曲面染色是指在一个有洞的物体上划分若干个区域，有一个洞的叫做环面，又叫亏格1的曲面。有两个洞的油饼形状叫做亏格2的曲面。 问题提出与解决 英国数学家彭西·希伍德在1890年首…
图着色问题
图着色问题（，簡稱），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图G=(V, E)，其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。 图色数 有两个相关的术语： 图色数（chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小…
哈德維格-納爾遜問題
哈德維格-納爾遜問題（），是指在平面上為每點填色，最少要多少種顏色，才能使若兩點距離為1，其顏色必定不相同呢？用圖論的語言可這樣敍述：設G為圖，G的頂點是平面上的所有點，兩個頂點相鄰若且唯若它們在平面上的距離為1，求G的點色數。這個問題等於求任意G的有限子集的最大點色數。 這個問題的下界是5，上界是7。 只有三種顏色無法完成的證明如下：平面上任取一點A，設其顏色為x，以其為圓心，分別以1和\sqrt 3為半徑做圓。在半徑\sqrt 3的…
色多项式
在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。 色多项式P(G,t)的值是在图G中顶点的不同的t-着色数目，是关于t的多项式。 例如当图G为一点时，P(G,t)=t。 例子 性质 给定n阶图G，色多项式P(G, t)是关于t的多项式，且满足以下性质： 多项式P(G, t)的次数为n。 t^n的系数为1。 t^{n-1}的系数为-|E(G)|。 t^c,\dots,t^n的系数不为0且正负交替出现。 …