| dbo:abstract
|
- First fit je algoritmus z teorie grafů. Je schopný najít obarvení libovolného grafu, není ale zaručeno, že půjde o obarvení minimální, tedy používající minimální potřebný počet různých barev. Jedná se o tzv. hladový algoritmus. (cs)
- In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible. Different choices of the sequence of vertices will typically produce different colorings of the given graph, so much of the study of greedy colorings has concerned how to find a good ordering. There always exists an ordering that produces an optimal coloring, but although such orderings can be found for many special classes of graphs, they are hard to find in general. Commonly used strategies for vertex ordering involve placing higher-degree vertices earlier than lower-degree vertices, or choosing vertices with fewer available colors in preference to vertices that are less constrained. Variations of greedy coloring choose the colors in an online manner, without any knowledge of the structure of the uncolored part of the graph, or choose other colors than the first available in order to reduce the total number of colors. Greedy coloring algorithms have been applied to scheduling and register allocation problems, the analysis of combinatorial games, and the proofs of other mathematical results including Brooks' theorem on the relation between coloring and degree.Other concepts in graph theory derived from greedy colorings include the Grundy number of a graph (the largest number of colors that can be found by a greedy coloring), and the well-colored graphs, graphs for which all greedy colorings use the same number of colors. (en)
- Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs. Différents choix pour la suite des sommets produisent généralement des colorations différentes du graphe donné. Une grande partie de l'étude des colorations gloutonnes porte donc sur la façon de trouver un bon ordre. Il existe toujours un ordre qui produit une coloration optimale, et même si l'on trouve aisément pour de nombreuses classes particulières de graphes, ils sont difficiles à trouver en général. Les stratégies couramment utilisées pour l'ordre des sommets impliquent de choisir les sommets de degré élevé avant les sommets de degré inférieur, ou de choisir des sommets avec moins de couleurs disponibles de préférence aux sommets qui sont moins contraints. Des variantes de coloration gloutonne consistent à choisir les couleurs par un algorithme online, donc sans connaissance de la structure de la partie non colorée du graphe, ou de choisir d'autres couleurs que la première couleur disponible afin de réduire le nombre total de couleurs. Des algorithmes de coloration gloutonne ont été appliqués à des problèmes d'ordonnancement et d'allocation de registres, à l'analyse de jeux combinatoires et aux preuves d'autres résultats mathématiques, notamment le théorème de Brooks sur la relation entre coloration et degré. D'autres concepts de théorie des graphes dérivés des colorations gloutonnes incluent le nombre de Grundy d'un graphe (le plus grand nombre de couleurs que l'on peut trouver dans une coloration gloutonne), et les graphes bien colorés, qui sont les graphes pour lesquels toutes les colorations gloutonnes utilisent le même nombre de couleurs. (fr)
- Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa (in inglese greedy coloring) è una colorazione dei vertici di un grafo formata da un algoritmo goloso (greedy algorithm) che considera i vertici del grafo in sequenza e assegna a ciascun vertice il suo primo colore disponibile. Le colorazioni golose in generale non usano il numero minimo di colori possibili; tuttavia, sono state usate in matematica come tecnica per dimostrare altri risultati sulle colorazioni e in informatica come euristica per trovare le colorazioni con pochi colori. (it)
- Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов. (ru)
- Жадібне розфарбування в теорії графів — розфарбування вершин неорієнтованого графа, створене жадібним алгоритмом, який проходить вершини графа в деякій визначеній послідовності та призначає кожній вершині перший доступний колір. Жадібні алгоритми, в загальному випадку, не дають мінімально можливе число кольорів, однак вони використовуються в математиці як техніка доказів інших результатів, що належать до розфарбування, а також у комп'ютерних програмах для отримання розфарбування з невеликим числом кольорів. (uk)
|
| rdfs:comment
|
- First fit je algoritmus z teorie grafů. Je schopný najít obarvení libovolného grafu, není ale zaručeno, že půjde o obarvení minimální, tedy používající minimální potřebný počet různých barev. Jedná se o tzv. hladový algoritmus. (cs)
- Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa (in inglese greedy coloring) è una colorazione dei vertici di un grafo formata da un algoritmo goloso (greedy algorithm) che considera i vertici del grafo in sequenza e assegna a ciascun vertice il suo primo colore disponibile. Le colorazioni golose in generale non usano il numero minimo di colori possibili; tuttavia, sono state usate in matematica come tecnica per dimostrare altri risultati sulle colorazioni e in informatica come euristica per trovare le colorazioni con pochi colori. (it)
- Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов. (ru)
- Жадібне розфарбування в теорії графів — розфарбування вершин неорієнтованого графа, створене жадібним алгоритмом, який проходить вершини графа в деякій визначеній послідовності та призначає кожній вершині перший доступний колір. Жадібні алгоритми, в загальному випадку, не дають мінімально можливе число кольорів, однак вони використовуються в математиці як техніка доказів інших результатів, що належать до розфарбування, а також у комп'ютерних програмах для отримання розфарбування з невеликим числом кольорів. (uk)
- In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible. (en)
- Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs. (fr)
|
