Рёберная раскраска
задача «раскраски» рëбер таким образом, что смежные рёбра не могут быть «закрашены» в один цвет / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Рёберная раскраска?
Кратко изложите эту статью для 10-летнего ребёнка
Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в различных цветов для заданного значения или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.
По теореме Визинга число цветов, необходимых для рёберной раскраски простого графа, либо равно максимальной степени вершин , либо . Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно , а для мультиграфов число цветов может быть вплоть до . Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов . Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время. Изучались много вариантов задачи рёберной раскраски, в которых условия назначения цвета ребру должны удовлетворять другим условиям, а не сопряжённости. Задачи рёберной раскраски имеют приложения в задачах расписания и в назначении частоты в оптоволоконных сетях.