Алгоритм раскраски графов c
Алгоритм раскраски графа с перекраской двуцветных компонент
О проекте. Расширенный поиск. На главную. Помощь экспертов - репетиторов.
Отправьте статью сегодня! Журнал выйдет 23 декабря , печатный экземпляр отправим 27 декабря. Автор : Моторина Екатерина Алексеевна. Дата публикации : Статья просмотрена: раз. Моторина, Е.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа , при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета [1]. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
