تلوين مخطط

	تلوين المخطط
	;
	القرار
الاسم	Graph coloring, vertex coloring, k-coloring
المُدخل	Graph G with n vertices. Integer k
المُخرج	هل G تتيح تلوين رؤوس سليم بعدد k من الألوان؟
زمن الحساب	O(2 nn)
التعقد	NP-complete
اختزال من	3-Satisfiability
Garey–Johnson	GT4
	Optimisation
الاسم	الرقم اللوني
المُدخل	المخطط G ذوn من الرؤوس.
المُخرج	χ(G)
التعقد	NP-hard
امكانية التقريب	O(n (log n)−3(log log n)2)
عدم امكانية التقريب	O(n1−ε) إلا إذا P = NP
	مشكلة العـد
الاسم	متعددة الحدود اللونية
المُدخل	المخطط G حيث n رؤوس. عدد سليم k
المُخرج	العدد P (G,k) لعدد k مناسب -تلوينات G
زمن الحساب	O(2 nn)
التعقد	#P-complete
امكانية التقريب	FPRAS لحالات محددة
عدم امكانية التقريب	No PTAS إلا إذا P = NP

مسألة NP كاملة
	قابلية الإرضاء 3SAT; NAE; OIT; ;
	تلوين مخطط تلوين مخطط بثلاثة ألوان; تلوين مخطط مستوبثلاثة ألوان; ;
	زمرة كبرى
	مسار هاملتونياني
	عدل

تلوين رؤوس مناسب في مخطط پيترسن بثلاث ألوان، وهوأقل عدد ممكن.

في مخطط عادي نريد تلوين جميع رأس بلون، حيث لا نلون رأسين متجاورين بنفس اللون. المشكلة هي كيف من الممكن أن نحدد أقل عدد ممكن من الألوان؟

التعريف والمصطلحات

This graph can be 3-colored in 12 different ways.

تلوين الرؤوس

متعددة الحدود اللونية

All nonisomorphic graphs on ثلاثة vertices and their chromatic polynomials. The empty graph E₃ (red) admits a 1-coloring, the others admit no such colorings. The green graph admits 12 colorings with ثلاثة colors.

الألوان المتاحة	1	2	3	4	…
عدد التلوينات	0	0	12	72	…

The chromatic polynomial is a function P(G, t) that counts the number of t-colorings of G. As the name indicates, for a given G the function is indeed a polynomial in t. For the example graph, P(G, t) = t(t − 1)²(t − 2), and indeed P(G, 4) = 72.

The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number. Indeed, χ is the smallest positive integer that is not a root of the chromatic polynomial

{\displaystyle \chi (G)=\min\{k\colon P(G,k)>0\ .

متعددات الحدود اللونية لمخططات محددة
Triangle K₃	${\displaystyle t(t-1)(t-2)$
Complete graph K_n	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))$
Tree with n vertices	${\displaystyle t(t-1)^{n-1$
Cycle C_n	${\displaystyle (t-1)^{n +(-1)^{n (t-1)$
Petersen graph	${\displaystyle t(t-1)(t-2)(t^{7 -12t^{6 +67t^{5 -230t^{4 +529t^{3 -814t^{2 +775t-352)$

تلوين الأضلاع

خصائص

تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. وتحديد هذا العدد من المشاكل الكاملة, وهذا المشكل له علاقة قريبة جدا من معضلة المخطط الكامل ضمن مخطط ومعضلة المخطط المستقر ضمن مخطط.

الخوارزميات

زمن متعددة الحدود

تلوين طماع

Two greedy colorings of the same graph using different vertex orders. The right example generalises to 2-colorable graphs with n vertices, where the greedy algorithm expends

{\displaystyle n/2

colors.

التلوين بثلاثة ألوان

تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هوأيضا مأزق تام حيث يمكن اختصار أي مأزق من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان.

التطبيقات

الجدولة الزمنية

تلوينات أخرى

نظرية رامسي

تلوينات أخرى

List coloring: Each vertex chooses from a list of colors
List edge-coloring: Each edge chooses from a list of colors
Total coloring: Vertices and edges are colored
Harmonious coloring: Every pair of colors appears on at most one edge
Complete coloring: Every pair of colors appears on at least one edge
Exact coloring: Every pair of colors appears on exactly one edge
Acyclic coloring: Every 2-chromatic subgraph is acyclic
Star coloring: Every 2-chromatic subgraph is a disjoint collection of stars
Strong coloring: Every color appears in every partition of equal size exactly once
Strong edge coloring: Edges are colored such that each color class induces a matching (equivalent to coloring the square of the line graph)
Equitable coloring: The sizes of color classes differ by at most one
T-coloring: Distance between two colors of adjacent vertices must not belong to fixed set T

Rank coloring: If two vertices have the same color i, then every path between them contain a vertex with color greater than i
Interval edge-coloring: A color of edges meeting in a common vertex must be contiguous
Circular coloring: Motivated by task systems in which production proceeds in a cyclic way
Path coloring: Models a routing problem in graphs
Fractional coloring: Vertices may have multiple colors, and on each edge the sum of the color parts of each vertex is not greater than one
Oriented coloring: Takes into account orientation of edges of the graph
Cocoloring: An improper vertex coloring where every color class induces an independent set or a clique
Subcoloring: An improper vertex coloring where every color class induces a union of cliques
Weak coloring: An improper vertex coloring where every non-isolated node has at least one neighbor with a different color
Sum-coloring: The criterion of minimalization is the sum of colors

Coloring can also be considered for signed graphs and gain graphs.

انظر أيضاً

Circular coloring
Critical graph
Cycle rank - Ordered chromatic number
Graph homomorphism
Mathematics of Sudoku
Uniquely colorable graph

الهامش

^ خطأ استشهاد: وسم <ref> غير سليم؛ لا نص تم توفيره للمراجع المسماة bhk

وصلات خارجية

by Joseph Culberson (graph coloring programs)
by Jim Andrews and Mike Fellows is a graph coloring puzzle
GF-Graph Coloring Program [1]
Links to Graph Coloring source codes
Code for efficiently computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle