| dbo:abstract
|
- Στη Θεωρία γράφων ο χρωματισμός ακμών ενός γραφήματος είναι η τοποθέτηση "χρωμάτων" στα άκρα του γραφήματος, έτσι ώστε να μην υπάρχουν δύο γειτονικές με το ίδιο χρώμα. Για παράδειγμα, η εικόνα στα δεξιά είναι ο χρωματισμός ακμών ενός γραφήματος με κόκκινο, μπλε και πράσινο χρώμα. Ο χρωματισμός ακμών είναι ένας από τους ποικίλους τρόπους χρωματισμού γραφημάτων. Το πρόβλημα χρωματισμού ακμών διερευνά αν είναι εφικτό να χρωματίσουμε τις ακμές ενός δοθέντος γραφήματος χρησιμοποιώντας μέχρι κ διαφορετικά χρώματα, όπου κ μια δεδομένη τιμή, ή με όσο το δυνατόν λιγότερα χρώματα. Ο ελάχιστος αριθμός χρωμάτων για τις ακμές ενός δοθέντος γραφήματος ονομάζεται χρωματικός δείκτης του γραφήματος. Για παράδειγμα, οι ακμές του γραφήματος της εικόνας μπορούν να χρωματιστούν με τρία χρώματα αλλά όχι με δύο,οπότε το εμφανιζόμενο γράφημα έχει χρωματικό δείκτη ίσο με τρία. Σύμφωνα με το , ο απαιτούμενος αριθμός χρωμάτων για το χρωματισμό ενός απλού γραφήματος είναι σε μέγιστο βαθμό είτε Δ ή Δ+1. Σε κάποια γραφήματα, όπως στα ή στα υψηλού βαθμού,ο αριθμός των χρωμάτων είναι πάντα Δ , και για τα πολλαπλά γραφήματα ο αριθμός των χρωμάτων μπορεί να είναι ως και 3Δ/2. Υπάρχουν πολυωνυμικοί αλγόριθμοι για το βέλτιστο χρωματισμό διμερών γραφημάτων και το χρωματισμό απλών μη διμερών γραφημάτων οι οποίοι χρησιμοποιούν μέχρι και Δ+1 χρώματα. Ωστόσο, το γενικό πρόβλημα ανεύρεσης του βέλτιστου χρωματισμού ακμών είναι το NP-complete και ακόμα και οι ταχύτεροι γνωστοί αλγόριθμοι χρειάζονται πολύ χρόνο για την αντιμετώπισή του. Έχουν μελετηθεί πολλές παραλλαγές του προβλήματος χρωματισμού ακμών, στις οποίες οι αναθέσεις χρωμάτων στα άκρα/ακμές πρέπει να πληρούν όρους/συνθήκες μη γειτνίασης (στις οποίες δεν μπορούν δύο κοντινές ακμές να έχουν το ίδιο χρώμα). Ο χρωματισμός ακμών έχει εφαρμογή σε προβλήματα προγραμματισμού και στην εκχώρηση συχνοτήτων για δίκτυα οπτικών ινών. (el)
- Eine Kantenfärbung ist eine Abbildung in der Graphentheorie, die jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Eine Kantenfärbung heißt gültig oder zulässig, wenn für jeden Knoten des Graphen gilt: Alle am Knoten anliegenden Kanten haben unterschiedliche Farben. Der Begriff ist eng verwandt mit der Knotenfärbung. (de)
- In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree Δ or Δ+1. For some graphs, such as bipartite graphs and high-degree planar graphs, the number of colors is always Δ, and for multigraphs, the number of colors may be as large as 3Δ/2. There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most Δ+1 colors; however, the general problem of finding an optimal edge coloring is NP-hard and the fastest known algorithms for it take exponential time. Many variations of the edge-coloring problem, in which an assignments of colors to edges must satisfy other conditions than non-adjacency, have been studied. Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks. (en)
- En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs. (fr)
- 그래프 이론에서 변 색칠(邊色漆, 영어: edge colo(u)ring은 그래프의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko)
- Kolorowanie krawędzi grafu – rozszerzenie klasycznego kolorowania grafu na krawędzie. Jest to przyporządkowywanie krawędziom grafu liczb naturalnych symbolizujących kolory. Odwzorowanie nazywamy kolorowaniem krawędzi grafu natomiast zbiór zbiorem kolorów. Niech oznacza zbiór kolorów krawędzi incydentnych z wierzchołkiem Prawidłowe pokolorowanie krawędzi (legalne, właściwe) to takie przyporządkowanie krawędziom kolorów, gdzie żadne dwie sąsiednie krawędzie nie są pokolorowane tak samo. (Krawędzie są sąsiednie jeśli mają wspólny jeden z końców). Czyli kolorowanie krawędzi nazywamy właściwym, jeżeli dla każdych dwóch sąsiednich krawędzi, w przeciwnym przypadku kolorowanie nazywamy niewłaściwym. k-kolorowaniem nazywamy kolorowanie czyli kolorujemy przy użyciu kolorów. Optymalne pokolorowanie krawędzi grafu to legalne pokolorowanie, przy którym zużyto najmniejszą możliwą liczbę kolorów. Indeks chromatyczny grafu to minimalna liczba kolorów wystarczająca do pokolorowania krawędzi grafu legalnie, oznaczamy go przez . Kolorowanie krawędzi jest równoważne kolorowaniu wierzchołków grafu krawędziowego. Kolorowanie krawędzi grafu nazywamy kolorowaniem krawędzi rozróżniającym wierzchołki, jeśli dla każdej pary wierzchołków i zbiory są różne. Niech będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania, jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast będzie najmniejszą liczbą kolorów potrzebnych do niewłaściwego kolorowania rozróżniającego wierzchołki. P.N. Balister, B. Bollobás oraz R.H. Schelp udowodnili następujące twierdzenie: Twierdzenie 1. Niech graf G będzie grafem dwuregularnym, wówczas (pl)
- Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor. Por exemplo, a figura à direita mostra uma coloração de arestas de um grafo com as cores vermelha, azul e verde. Coloração de arestas é um dos vários tipos de coloração de grafos. O Problema da coloração de arestas pergunta se é possível colorir um dado grafo usando no máximo n cores. O número mínimo exigido de cores para um grafo é chamado de índice cromático. Por exemplo, o grafo à direita pode ser colorido com três cores, mas não pode ser colorido por duas cores, e, portanto, tem o índice cromático três. (pt)
- Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в различных цветов для заданного значения или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3. По теореме Визинга число цветов, необходимых для рёберной раскраски простого графа, либо равно максимальной степени вершин , либо . Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно , а для мультиграфов число цветов может быть вплоть до . Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов . Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время. Изучались много вариантов задачи рёберной раскраски, в которых условия назначения цвета ребру должны удовлетворять другим условиям, а не сопряжённости. Задачи рёберной раскраски имеют приложения в задачах расписания и в назначении частоты в оптоволоконных сетях. (ru)
- Розфарбовування ребер — в теорії графів, це присвоєння кольорів ребрам графу, при якому не існує суміжних ребер однакового кольору. Таке розфарбування графу називають правильним розфарбуванням. Проблема розфарбовування ребер полягає в з'ясуванні, чи можливо розфарбувати даний граф використовуючи не більше кольорів. Мінімально потрібна кількість кольорів для правильного розфарбування даного графу називається хроматичним індексом графу. Наприклад, граф праворуч може бути розфарбований трьома кольорами, але двох буде замало (існуватимуть суміжні ребра однакового кольору). Таким чином, його хроматичний індекс дорівнює три. (uk)
|
| rdfs:comment
|
- Eine Kantenfärbung ist eine Abbildung in der Graphentheorie, die jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Eine Kantenfärbung heißt gültig oder zulässig, wenn für jeden Knoten des Graphen gilt: Alle am Knoten anliegenden Kanten haben unterschiedliche Farben. Der Begriff ist eng verwandt mit der Knotenfärbung. (de)
- En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs. (fr)
- 그래프 이론에서 변 색칠(邊色漆, 영어: edge colo(u)ring은 그래프의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (ko)
- Розфарбовування ребер — в теорії графів, це присвоєння кольорів ребрам графу, при якому не існує суміжних ребер однакового кольору. Таке розфарбування графу називають правильним розфарбуванням. Проблема розфарбовування ребер полягає в з'ясуванні, чи можливо розфарбувати даний граф використовуючи не більше кольорів. Мінімально потрібна кількість кольорів для правильного розфарбування даного графу називається хроматичним індексом графу. Наприклад, граф праворуч може бути розфарбований трьома кольорами, але двох буде замало (існуватимуть суміжні ребра однакового кольору). Таким чином, його хроматичний індекс дорівнює три. (uk)
- Στη Θεωρία γράφων ο χρωματισμός ακμών ενός γραφήματος είναι η τοποθέτηση "χρωμάτων" στα άκρα του γραφήματος, έτσι ώστε να μην υπάρχουν δύο γειτονικές με το ίδιο χρώμα. Για παράδειγμα, η εικόνα στα δεξιά είναι ο χρωματισμός ακμών ενός γραφήματος με κόκκινο, μπλε και πράσινο χρώμα. Ο χρωματισμός ακμών είναι ένας από τους ποικίλους τρόπους χρωματισμού γραφημάτων. Το πρόβλημα χρωματισμού ακμών διερευνά αν είναι εφικτό να χρωματίσουμε τις ακμές ενός δοθέντος γραφήματος χρησιμοποιώντας μέχρι κ διαφορετικά χρώματα, όπου κ μια δεδομένη τιμή, ή με όσο το δυνατόν λιγότερα χρώματα. Ο ελάχιστος αριθμός χρωμάτων για τις ακμές ενός δοθέντος γραφήματος ονομάζεται χρωματικός δείκτης του γραφήματος. Για παράδειγμα, οι ακμές του γραφήματος της εικόνας μπορούν να χρωματιστούν με τρία χρώματα αλλά όχι με δύο (el)
- In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. (en)
- Kolorowanie krawędzi grafu – rozszerzenie klasycznego kolorowania grafu na krawędzie. Jest to przyporządkowywanie krawędziom grafu liczb naturalnych symbolizujących kolory. Odwzorowanie nazywamy kolorowaniem krawędzi grafu natomiast zbiór zbiorem kolorów. Niech oznacza zbiór kolorów krawędzi incydentnych z wierzchołkiem k-kolorowaniem nazywamy kolorowanie czyli kolorujemy przy użyciu kolorów. Optymalne pokolorowanie krawędzi grafu to legalne pokolorowanie, przy którym zużyto najmniejszą możliwą liczbę kolorów. Kolorowanie krawędzi jest równoważne kolorowaniu wierzchołków grafu krawędziowego. (pl)
- Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor. Por exemplo, a figura à direita mostra uma coloração de arestas de um grafo com as cores vermelha, azul e verde. Coloração de arestas é um dos vários tipos de coloração de grafos. (pt)
- Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в различных цветов для заданного значения или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3. (ru)
|
