Раскраска графа что это

В силу его двудольности, это число будет равняться сумме степеней вершин одной из долей. А по лемме о нижней оценки, меньше цветов использовать нельзя. Материал из Викиконспекты. Перейти к: навигация , поиск.

Основы теории графов 09: раскраски планарных графов, совершенные графы

Правильная вершинная реберная раскраска - это раскраска вершин ребер графа, при к-рой любые смежные вершины ребра окрашены в разные цвета. Правильную вершинную раскраску часто наз. Граф наз. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. Если , то граф Gназ.

У каждого ребра есть вес — положительное целое число. Каждая пара вершин из одной и той же тройки соединена ребром. Ни одно ребро не соединяет две вершины из разных троек. Вершины этого графа надо раскрасить в два цвета, красный и синий.

Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то есть присвоение цветовых меток вершинам графа так, чтобы любые две вершины, имеющие общее ребро, имели разные цвета. Так как графы, в которых есть петли, не могут быть раскрашены таким образом, они не являются предметом обсуждения. Полный граф - такой граф, у которого есть путь из каждой вершины в каждую. Очевидно, что хроматическое число полного графа совпадает с количеством вершин. Пусть дан граф и дана его раскраска. Чтобы проверить её корректность, нужно обойти все ребра и проверить, если одинаковые цвета на концах.

Похожие статьи

• Строим дом своими руками поэтапный показ строительства на видео
• Рисовать кошку красиво поэтапно - Учимся рисовать животных - Учимся рисовать - Рисование
• Связать сумку кукле - Вязание из полиэтиленовых пакетов и поделки из мешков для
• Букеты с фотографиями