在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。 色多项式 P ( G , t ) {\displaystyle P(G,t)} 的值是在图 G {\displaystyle G} 中顶点的不同的 t {\displaystyle t} -着色数目，是关于 t {\displaystyle...

(G)=\min\{k\,\colon \,P(G,k)>0\}.} 下表给出了部分图的色多项式： 五色定理 四色定理 Vizing定理 布鲁克定理 Konig定理（关于二分图） Hadwiger猜想 拉姆齐定理 色数 NP-complete問題列表 幾乎完備（Almost complete（英语：Almost...

的结构直接相关，尤其是与不可约特征标相关。 最后，代数图论的第三个分支研究图不变量的代数性质，尤其是色多项式、Tutte多项式与扭结不变量。例如，图的色多项式计算了顶点着色的个数。佩特森图的色多项式为 t ( t − 1 ) ( t − 2 ) ( t 7 − 12 t 6 + 67 t 5 − 230...

个可有效计算这种常量的方法(图规范化问题)等价于给出一个简单解决富有挑战性的图同构问题的方法。然而，即使多项式的常量值如色多项式，通常也不完备的。例如，爪形图和4个顶点的道路图都具有相同的色多项式。 连通图 二分图 平面图 无三角形图 完美图 欧拉图 汉密尔顿图 顶点数 边数 元件数 电路等级（图的顶点、边和元件的线性组合）...

如果这样的k着色方式存在，那么我们为了给整个图着色的最小着色数（k值）可记为 χ ( G ) {\displaystyle \chi (G)} 。 我们可以通过构建k的多项式函数来计算合理的k着色方式的数量，其被称为图G的着色多项式（可用无向图的着色多项式来类比），其定义式为 χ G ( k ) {\displaystyle...

graph），其色数为3：环上的节点可以用两种颜色染色，而中间的完全点使用第三种颜色。当n为偶数时，Wn的色数为4，且当n ≥ 6时不是完美图。W7是轮图中在欧几里得平面上的唯一一个单位距离图（英语：unit distance graph）。 轮图Wn的色多项式为 P W n ( x )...

4的情况，阿佩尔和哈肯在1989年的单行本的附录中给出一个完整的多项式时间的算法及其证明。 四色问题探讨的是平面上地图的染色问题。更一般的情况：曲面上地图的染色问题是由希伍德开始研究的。他在1890年的论文中不仅指出肯普的错误，而且运用肯普的方法证明了五色定理。在此之后，希伍德又将注意力转移到更一般的曲面染色...

如果只有两项作业或两个工作站，那么开放车间调度问题可以在多项式时间内求解。如果说所有不等于0的解决时间都相等，那么这种问题也可以在多项式时间内完成。因为在这种情况下，这个问题可以等效于给一个以作业和工作站为顶点的二分图的边上色，每条边代表不为0的作业-工作站对，着色中边的颜色对应于工作-工...

交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法，則該解法就可應用在所有NP問題上，亦可證明NP問題等於P問題，然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。...

代数几何（英語：algebraic geometry）是数学的一个分支，经典代数几何研究多项式方程的零点。现代代数几何将抽象代数，尤其是交换代数，同几何学的语言和问题结合起来。 代数几何的基本研究对象为代数簇。代数簇是由空间坐标的若干代数方程的零点集。常见的例子有平面代数曲线，比如直线、圆、椭圆、...

红磷（英語：Red Phosphorus），磷的一种同素异形体 反相色谱法（英語：Reverse phase），一种色谱技术 RP-3，一种火箭弹 RP (复杂度)（英語：RP (complexity)），随机多项式时间，计算复杂度理论中的一类 数学 实射影直线（英語：Real projective...

conjecture）：一个n阶图是否能够由其所有n-1阶导出子图唯一确定？ 点色数（Chromatic number） 边色数（Chromatic index） 色多项式 许多问题与将图以特定方式染色有关，如： 四色问题 完美图问题（strong perfect graph theorem） 列表染色问题，列表边染色问题...

k-分圖是一個图，其點集被分成 k 部分，各部分各自形成独立集。換句话說，可以把圖的所有點著色，使得相鄰的點著不同色且總共用了k 個顏色。k = 2 的情況被稱作二分圖，而 k = 3 的情況被稱作三分圖。 事實上，辨別一個圖是二分圖只需要多項式時間。但當 k > 2，辨別一個圖是否為 k-分圖卻是NP完全的 。不過，在一些圖論的應用場合中，給計算器處理...

亨德里克·倫斯特拉 - 应用几何数论在约束个数的多项式时间内求解变元数较少的整数规划问题。 Eugene M. Luks（英语：Eugene M. Luks） - 对于最大度有上界的图求解图同构问题的多项式时间算法。 1988: 愛娃·塔多斯 - 在强多项式时间内求解网络中的最小费用环流。 Narendra...

{CSP}}(\Gamma )} 在多项式时间归约意義下等價於染 H {\displaystyle H} 色問題。 直觀理解，定理意味着任何算法技巧或複雜度結論，若適用於一般有向圖 H {\displaystyle H} 的染 H {\displaystyle H} 色...

多项式方程的可解性。 克羅內克於1888年表示，現代代數的研究始於范德蒙的第一篇論文。柯西明確地表示，范德蒙有著優於拉格朗日的非凡想法，這最終導致了群論的研究。 保羅·魯菲尼是第一個發展置換群理論的數學家，如同他的前輩一般，也是為了多项式方程的求解。他的目標是確定一個大於4次的一元多项式...

是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用于...

我们也可以确定原图是否是连通的，因为这等价于任意两个 G i {\displaystyle G_{i}} 是连通的。 Tutte polynomial 图的特征多项式 平面性 图中生成树的种类 色多项式 重构猜想和顶点重构猜想在图的阶数小于等于11的情况下均已被Brendan McKay验证。 Béla Bollobás提出，在概率意义下几乎所有的图都是可重构的。...

伊斯蘭數學家納色阿爾圖斯（英语：Sharaf al-Dīn al-Tūsī）（1135年–1213年）在其著作《Treatise on Equations》中說明了部份三次方程有解的條件，是透過找適當三次多項式的最大值來求得。他證明了三次多項式 a x2 — x3的最大值出現在x...

中国邮差问题：由中华民国组合数学家管梅谷教授提出。邮差要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。也是圖論題。 任务分配问题（也称分配问题）：有一些员工...

已知构造序列时，也有可能在多项式时间内为团宽有界图找到最优图着色或哈密顿环，但多项式的指数随团宽增加，计算复杂度理论的证据表明这种依赖可能是必要的。 团宽有界图是χ-有界的，这是说它们的色数最多是其最大团大小的函数。 运用基于裂分解的算法，可在多项式时间内识别出团宽为3的图，并找到构造序列。...

米斯拉-格里斯边着色算法是图论算法的一种，能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用 Δ + 1 {\displaystyle \Delta +1} 种颜色， Δ {\displaystyle \Delta } 是该图节点的最大度数。这对于一些图而言是最优的，根据Vizin...

上提出了许多算法，指数时间复杂度算法包括Bron–Kerbosch算法（英语：Bron–Kerbosch_algorithm），而针对特定一类图有多项式时间复杂度算法，例如平面图和完美图（英语：Perfect_graph）。 其实Kuratowski (1930)更早提出完全子图一词（一个有限图是...

minor characterization）也存在。 给定图G和图H，可以在多项式时间内判断H是否是G的子式。 连同上述禁子式表征，这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。 其他涉及到图子式的定理和猜想包括图结构定理（英语：graph structure...

国际数学联盟在1990年授予威滕菲尔兹奖，成为第一位获得该奖项的物理学家（也是唯一一位）。他对纯数学方面的研究影响深远，例如他使用琼斯多项式（Jones Polynomial）来解释陈-西蒙斯理论」（Chern-Simons theory）。这项研究对于低维拓扑结构有深远影响，并推导出量子不变量。...

在理论计算机科学，复杂度类P指所有可由确定型图灵机在多项式时间内解决的问题，类NP是所有可在多项式时间内验证解的正确性的问题。这里所谓「多项式时间」指的是求解算法运行时间至多是输入规模的多项式函数。粗略说，P类问题是可以在计算机上快速求解的问题，而对NP问题则可快速确定某...

布劳威尔不动点定理 本迪克森-杜拉克定理 本原元定理 垂径定理 陈氏定理 采样定理 迪尼定理 等周定理 代数基本定理 多项式余数定理 大数定律 狄利克雷定理 棣莫弗定理 棣莫弗-拉普拉斯定理 笛卡儿定理 多项式定理 笛沙格定理 达布定理 达布定理 (微分几何) 笛卡儿符号法则 单调收敛定理 单值化定理 狄利克雷定理...

全體平方数的集合是小集（其倒數和為 π 2 / 6 {\displaystyle \pi ^{2}/6} ）。立方數、四次方數等亦然。更一般地，任何二次以上的正整數系數多項式取值的集合必為小集。 2 {\displaystyle 2} 的冪組成的集合 { 1 , 2 , 4 , 8 , … } {\displaystyle...

这个定义中的行列式可以展开成一个关于 λ {\displaystyle \lambda } 的n阶多项式，叫做矩阵A的特征多项式，记为 p A {\displaystyle p_{\mathbf {A} }} 。特征多项式是一个首一多项式（最高次项系数是1的多项式）。它的根就是矩阵 A {\displaystyle \mathbf...

，我们知道最快的近似必须包含一些随机性。 对于某些问题，具有多项式时间复杂度的随机算法能否成为最快的算法，是一个被称为“ P/NP问题”的悬而未决的问题。这种算法有两大类: 蒙特卡罗算法以高概率返回正确答案。例如 RP 是这些运行在多项式时间的子类。 拉斯维加斯算法总是返回正确的答案，但他们的运行时间只是概率约束，例如...

秀爾演算法能在量子電腦上以多項式時間執行整數的因數分解，和已知的古典演算法相比具有超多項式加速。 一般認為使用古典資源分解整數很困難，然而嚴謹的證明尚未出現。缺乏古典計算困難度的證明，是難以明確展示量子優越性的主要原因。這影響了常見的量子優越性問題：Aaronson和Arkhipov的玻色子抽樣問題（boson...