图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图 G = ( V , E ) {\displaystyle G=(V,E)} ，其中 V {\displaystyle V} 为顶点集合， E {\displaystyle...

四色方柱问题是由有四個顏色的立方体組成的問題。由四色（通常是红色，蓝色，绿色和白色）將立方體着色，用四个立方体组成方柱。问题是如何将这些立方体排成一列，使得排成的长方体的每一側(前、后、左、右)都有四种颜色。 四色方柱问题可以转化为图着色问题来解决。 希望通过给定的四个立方体，构造一张图，并通过解决图着色问题得到排列方式。图的构造方式如下：...

在電腦圖學中，著色，也称浓淡处理、明暗处理、着色法（英語：Shading）是在三维模型或插画中通过不同的亮度表现深度的方法。 浓淡处理是用较大压力在纸上绘制较深颜色、用较小压力绘制较浅颜色从而表示不同明暗程度的过程。有许多不同的浓淡处理技术，其中交叉影线是用不同距离互相垂直的网格线绘制不同区域的浓...

_{G_{a}}(k)} . 混合图可用于对车间调度问题进行建模，例如在一定的时间限制下执行一系列任务的问题。在这类问题中，无向边可用于设定两个任务不兼容(不能同时执行)的约束。有向边可用于优先级约束，即其中一个任务必须先于另一个任务执行。用这种方法从调度问题的角度定义的图称为析取图。混合图着色问题可用于规划执行所有任务的最小长度。...

当做一個着色： U {\displaystyle U} 中所有頂點为蓝色， V {\displaystyle V} 中所有頂點着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分圖無法被二著色，例如 K 3 {\displaystyle K_{3}} (3 個頂點的完全圖...

cycle） 每句话至多3个变量的布爾可滿足性問題（Satisfiability with at most 3 literals per clause, 3-SAT） 图着色问题（Chromatic number） 分團覆蓋問題（Clique cover） 精確覆蓋問題（Exact cover） Hitting...

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

多主体优化系统 (multiagent optimization system, MAOS) 是一种基于混合多主体系统和群集智能的优化系统。它已经被用来求解数值优化和组合优化问题，如旅行商问题、图着色问题、背包问题等。 针对TSP问题的MAOS源代码链接（页面存档备份，存于互联网档案馆）...

在图论中，图属性（graph property）或图常量（graph invariant，又称图不变量）是图的一种性质，它只取决于其抽象结构，而不取决于图的表示形式如特定的图标号或图绘制形式。 虽然图的绘制和图的表示都是图论中的有效课题，但为了只关注图的抽象结构，图属性被定义为在图...

一个大环都被弦切割成若干小三角形，因此弦图也被称作三角化图。 弦图是完美图的一种子类。算法可以在线性时间内判定一张图是否为弦图。而且，有些在一般图上困难的问题（比如图着色问题），在弦图上可被高效解决。 设Ck:=v1v2…vkv1{\displaystyle C_{k}:=v_{1}v_{2}\dots...

Hadwiger）（Hugo Hadwiger）对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch（英语：Heinrich Heesch）发表了一个用计算机解决此问题的方法。1976年，凱尼斯·阿佩爾和沃夫冈·哈...