تلوين مخطط

	تلوين المخطط
	;
	القرار
الاسم	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 3 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 3 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

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

متعددات الحدود اللونية لمخططات محددة
Triangle K₃	$t(t-1)(t-2)$
Complete graph K_n	$t(t-1)(t-2)\cdots (t-(n-1))$
Tree with n vertices	$t(t-1)^{n-1}$
Cycle C_n	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen graph	$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

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.

انظر أيضاً

الهامش

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

وصلات خارجية

Graph Coloring Page by Joseph Culberson (graph coloring programs)
CoLoRaTiOn 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

هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، ساهم في إثرائها بالمشاركة في تحريرها.

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

[1]