| dbo:abstract
|
- En teoria de grafs, la coloració de grafs és un cas especial d', una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix a assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix a assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú. El punt de partida del tema és la coloració de vèrtexs, ja que la resta de problemes de coloració es poden reduir a una de vèrtexs. Per exemple, la coloració d'arestes d'un graf és tan sols una coloració de vèrtexs del seu i la coloració de cares d'un graf pla és simplement una coloració de vèrtexs del seu dual. Tanmateix, els problemes que no són de coloració de vèrtexs solen estudiar-se tal com són. Això és per una part per la perspectiva i per l'altra perquè certs problemes són més fàcils d'estudiar amb un sistema diferent —la coloració d'arestes n'és un exemple. La convenció d'utilitzar colors prové de la cartografia, on els països o regions s'acoloreixen diferent per distingir-se. Aquest sistema es generalitzà acolorint les cares d'un graf en el pla. Per dualitat planar esdevingué coloració de vèrtexs i d'aquesta forma es generalitza a tots els grafs. En les representacions matemàtiques i computacionals, és habitual usar els primers enters positius o no negatius com a «colors». Més generalment, es pot usar qualsevol conjunt finit com a «conjunt de colors». La coloració de grafs té diverses utilitats pràctiques així com reptes teòrics. A part dels tipus clàssics de problemes, també es poden aplicar diferents limitacions al graf, a l'assignació del color o fins i tot al color en si. Entre el públic general ha assolit popularitat a través del trencaclosques numèric sudoku. La coloració de grafs segueix sent un camp actiu de recerca. (ca)
- تلوين الرسوم أو تلوين المخطط هو أحد أكثر المسائل شهرة وبحثا في نظرية المخططات، ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات. وهذه المسألة هي تخصيص «لون» لأحد عناصر المخطط بحيث تتحقق مجموعة شروط محددة، لعل ابسط الصيغ هذه المسألة هي تلوين رؤوس المخطط بحيث لا يوجد رأسان متجاوران لهما نفس اللون. وهذا النوع من التلوين يسمى «تلوين الرؤوس»، وبشكل مشابه نعرف «تلوين الاضلاع» وهو تلوين الاضلاع بحيث لا يوجد ضلعان يشتركان في رأس لهما نفس اللون، و«تلوين الوجوه» في مخطط مستو هو تخصيص لون لكل وجه أو منطقة بحيث لا يوجد منطقتين تشتركان بنفس الحدود لهما نفس اللون. تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الأخرى يمكن تحويلها إلى مسألة تلوين الرؤوس، مثلا «تلوين الأضلاع» هي «تلوين الرؤوس» في الملائم لهذا المخطط، و«تلوين الوجوه» هو «تلوين الرؤوس» للمخطط الثنائي الملائم. ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة أسباب منها أنَّ بعض هذه المسائل يُفضل أن تدرس كما هي لبساطة التعاطي معها كما هي. في الأصل استخدام مصطلح الألوان كان لأجل تلوين الخارطة، ولكن في علم الحاسوب والرياضيات بشكل عام يستخدم الأعداد الصحيحة للدلالة على الألوان. مسألة التلوين هي حالة خاصة من مسألة وسم المخطط. مسألة تلوين المخطط مسألة لها كثير من التطبيقات العملية وتمتد على كل علم الحاسوب، يمكن إضافة شروط على المخطط وأيضا على الألوان، ولعل أكثر نسخة من هذه المسألة شيوعا بين الناس هي لعبة السودوكو. (ar)
- Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést. (cs)
- Αν G είναι ένα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση είναι χρωματισμός του G όταν δηλαδή όταν αντιστοιχεί χρώματα στους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις. (el)
- En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual. La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales se utilizan típicamente enteros no negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son. (es)
- Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse. (de)
- In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring. The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non-negative integers as the "colors". In general, one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are. Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research. Note: Many terms used in this article are defined in Glossary of graph theory. (en)
- Grafo teorian, grafo baten koloreztaketa grafoko elementuak (erpinak edo ertzak) hainbat baldintzapean koloreztatu edo bereizteko erabiltzen da. Erpinen koloreztaketan ondokoak diren erpinak kolore ezberdinez margotu behar dira. Ertzen koloreztaketan berriz ondokoak diren ertzak dira kolore ezberdinez margotu beharrekoak. Grafo bateko aldeei buruz ere koloreztaketa ebazkizunak planteatzen dira. Erpinen koloreztaketa da ordea ebazkizun nagusia, beste koloreztaketa guztiak erpinen koloreztaketaz ebatzi ahal izaten baitira. Grafo koloreztaketak aplikazio zabalak ditu plangintza arloan. Koloreen ordez, zenbakiak edo bestelako ikurrak ere jarri daitezke, baina koloreak erabili ohi dira, historian zehar grafo koloreztaketak mapak koloreztatzeko lau koloreen teoremarekin lotu zirelako. (eu)
- En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. (fr)
- 그래프 이론에서 그래프 색칠(graph色漆, 영어: graph colo(u)ring)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko)
- グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 (ja)
- Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di ; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore. La colorazione dei vertici è il punto di partenza dell'argomento, e gli altri problemi di colorazione possono essere trasformati in una versione dei vertici. Ad esempio, una colorazione degli spigoli di un grafo è solo una colorazione dei vertici del suo , e una colorazione delle facce di un grafo planare è solo una colorazione dei vertici del suo duale. Tuttavia, i problemi di colorazione dei vertici sono spesso dichiarati e studiati come sono. Questo è in parte per la prospettiva, e in parte perché alcuni problemi si studiano meglio in forma diversa dai vertici, com'è ad esempio la colorazione degli spigoli. La convenzione di usare i colori trae origine dalla colorazione dei paesi di una mappa, dove ogni faccia è colorata in senso letterale. Questo fu poi generalizzato alla colorazione delle facce di un grafo nel piano. A causa della dualità planare si passò alla colorazione dei vertici, e in questa forma si generalizza a tutti i grafi. Nelle rappresentazioni matematiche e informatiche, è tipico usare i primi interi positivi o non negativi come "colori". In generale, si può usare qualsiasi insieme finito come "insieme dei colori". La natura del problema della colorazione dipende dal numero dei colori, ma non da quali sono. La colorazione dei grafi gode di molte applicazioni pratiche come pure di molte sfide teoriche. Oltre ai problemi di tipo classico, si possono anche porre diverse limitazioni sul grafo, o sul modo in cui un colore è assegnato, o perfino sul colore stesso. L'argomento ha raggiunto popolarità anche presso il grande pubblico sotto la forma del popolare rompicapo sudoku. La colorazione dei grafi è ancora un campo di ricerca molto attivo. Nota: molti termini usati in questo articolo sono definiti in Glossario di teoria dei grafi. (it)
- Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent. "Kleur" kan men hier vervangen door "natuurlijk getal"; de term vindt zijn oorsprong in het historische probleem van de kleuring van landkaarten: hoeveel kleuren zijn er minimaal nodig om een kaart te kleuren zodanig dat landen die aan elkaar grenzen steeds een verschillende kleur hebben? (nl)
- Graffärgning är ett begrepp inom grafteorin i matematiken, som beskriver en tilldelning av färger till antingen kanterna eller noderna uppfyllandet ett visst villkor. Om det är en färgläggning av noderna, kallad en nodfärgning, får inte två noder som har en kant mellan sig vara av samma färg. Om det är en färgläggning av kanterna så får två kanter som möts i en nod inte ha samma färg. (sv)
- Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет. Раскраска вершин — главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска рёбер графа — это раскраска вершин его рёберного графа, а раскраска областей планарного графа — это раскраска вершин его двойственного графа. Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это даёт лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска рёбер). Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования. (ru)
- Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru. (pl)
- Em teoria dos grafos, coloração de grafos é um caso especial de ; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor. A coloração de vértices é o ponto de partida para o assunto, e outros problemas de coloração podem ser transformados em uma versão de vértices. Por exemplo, uma coloração de arestas de um grafo é simplesmente uma coloração de vértices do seu , e uma coloração de face de um grafo planar é apenas uma coloração de vértices do seu dual planar. No entanto, problemas de coloração de não-vértices são muitas vezes referidos e estudado como são. Isso se deve em parte à perspectiva, e em parte porque alguns problemas são mais bem estudados na forma não-vértice, como por exemplo, a coloração de arestas. A convenção do uso de cores provém de colorir os países de um mapa, onde cada face é literalmente colorida. Este foi generalizado para coloração das faces de um grafo no plano. Pela dualidade planar se passou a colorir os vértices, e desta forma se generalizou a todos os grafos. Em representações matemáticas e na informática é comum usar os primeiros números inteiros positivos ou não negativos como as "cores". Em geral pode-se usar qualquer conjunto finito como "conjunto de cores". A natureza do problema de coloração depende do número de cores, mas não sobre o que são. A coloração de grafos goza de muitas aplicações práticas, bem como desafios teóricos. Ao lado dos tipos clássicos de problemas, limitações diferentes também podem ser definidas no grafo, ou na forma como uma cor é atribuída, ou mesmo sobre a própria cor. Ela chegou até a se popularizar com o público em geral na forma da popular série de quebra-cabeças Sudoku. A coloração de grafos ainda é um campo de pesquisa muito ativa. (pt)
- Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору.Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом. (uk)
- 图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图，其中为顶点集合，为边集合，图着色问题即为将分为个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的值。 (zh)
|
| rdfs:comment
|
- Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést. (cs)
- Αν G είναι ένα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση είναι χρωματισμός του G όταν δηλαδή όταν αντιστοιχεί χρώματα στους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις. (el)
- Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse. (de)
- Grafo teorian, grafo baten koloreztaketa grafoko elementuak (erpinak edo ertzak) hainbat baldintzapean koloreztatu edo bereizteko erabiltzen da. Erpinen koloreztaketan ondokoak diren erpinak kolore ezberdinez margotu behar dira. Ertzen koloreztaketan berriz ondokoak diren ertzak dira kolore ezberdinez margotu beharrekoak. Grafo bateko aldeei buruz ere koloreztaketa ebazkizunak planteatzen dira. Erpinen koloreztaketa da ordea ebazkizun nagusia, beste koloreztaketa guztiak erpinen koloreztaketaz ebatzi ahal izaten baitira. Grafo koloreztaketak aplikazio zabalak ditu plangintza arloan. Koloreen ordez, zenbakiak edo bestelako ikurrak ere jarri daitezke, baina koloreak erabili ohi dira, historian zehar grafo koloreztaketak mapak koloreztatzeko lau koloreen teoremarekin lotu zirelako. (eu)
- En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. (fr)
- 그래프 이론에서 그래프 색칠(graph色漆, 영어: graph colo(u)ring)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko)
- グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 (ja)
- Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent. "Kleur" kan men hier vervangen door "natuurlijk getal"; de term vindt zijn oorsprong in het historische probleem van de kleuring van landkaarten: hoeveel kleuren zijn er minimaal nodig om een kaart te kleuren zodanig dat landen die aan elkaar grenzen steeds een verschillende kleur hebben? (nl)
- Graffärgning är ett begrepp inom grafteorin i matematiken, som beskriver en tilldelning av färger till antingen kanterna eller noderna uppfyllandet ett visst villkor. Om det är en färgläggning av noderna, kallad en nodfärgning, får inte två noder som har en kant mellan sig vara av samma färg. Om det är en färgläggning av kanterna så får två kanter som möts i en nod inte ha samma färg. (sv)
- Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru. (pl)
- Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору.Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом. (uk)
- 图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图，其中为顶点集合，为边集合，图着色问题即为将分为个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的值。 (zh)
- تلوين الرسوم أو تلوين المخطط هو أحد أكثر المسائل شهرة وبحثا في نظرية المخططات، ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات. تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الأخرى يمكن تحويلها إلى مسألة تلوين الرؤوس، مثلا «تلوين الأضلاع» هي «تلوين الرؤوس» في الملائم لهذا المخطط، و«تلوين الوجوه» هو «تلوين الرؤوس» للمخطط الثنائي الملائم. ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة أسباب منها أنَّ بعض هذه المسائل يُفضل أن تدرس كما هي لبساطة التعاطي معها كما هي. (ar)
- En teoria de grafs, la coloració de grafs és un cas especial d', una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix a assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix a assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú. (ca)
- In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. (en)
- En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justa (es)
- Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di ; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore. (it)
- Em teoria dos grafos, coloração de grafos é um caso especial de ; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor. (pt)
- Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет. (ru)
|
