تلوين مخطط

(تم التحويل من Graph coloring)
تلوين رؤوس مناسب في مخطط پيترسن بثلاث ألوان، وهو أقل عدد ممكن.
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

تلوين الرؤوس

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

All nonisomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 (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(Gt) 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(Gt) = t(t − 1)2(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

متعددات الحدود اللونية لمخططات محددة
Triangle K3
Complete graph Kn
Tree with n vertices
Cycle Cn
Petersen graph

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

خصائص

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

الخوارزميات

تلوين المخطط
3-coloringEx.svg
القرار
الاسمGraph coloring, vertex coloring, k-coloring
المُدخلGraph G with n vertices. Integer k
المُخرجهل G تتيح تلوين رؤوس صحيح بعدد k من الألوان؟
زمن الحسابO(2nn)[1]
التعقدNP-complete
اختزال من3-Satisfiability
Garey–JohnsonGT4
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(2nn)
التعقد#P-complete
امكانية التقريبFPRAS لحالات محددة
عدم امكانية التقريبNo PTAS إلا إذا P = NP

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

تلوين طماع

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 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.

انظر أيضاً

الهامش

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

وصلات خارجية