Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Раскраска графов




Читайте также:
  1. Алгоритм нахождения полных подграфов
  2. Глава II. Теория графов
  3. Изоморфизм графов.
  4. Ими были созданы предпосылки для достоверных и обоснованных представлений о Севере. С эпохи Ренессанса сведения русских картографов становились известными на Западе.
  5. Компьютерная томография. Виды компьютерных томографов. Диагностические возможности и области применения метода. Противопоказания к проведению КТ.
  6. Матричные способы задания графов. Упорядочение элементов орграфа
  7. Основные объекты графов
  8. Основные определения теории графов
  9. Основные определения теории графов
  10. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Пусть - некоторый граф и - разбиение на внутренне устойчивых множеств (разбиение означает, что и , если ). В этом случае говорят, что вершины графа допускают раскраску в цветов (цвета по номерам ). Хроматическое число - минимальное значение , которое допускает раскраску графа.

Хроматическое число пустого графа равно 1.
Хроматическое число .
Хроматическое число .

Алгоритм нахождения раскраски (хроматического числа)

1) Выделить все пустые подграфы графа.
2) Построить таблицу покрытий вершин графа пустыми подграфами.
3) Найти минимальное покрытие вершин графа пустыми подграфами (мощность минимального покрытия – это , а само покрытие определяет раскраску).

Пример


 

 
     
     
     
     
     
       


Дата добавления: 2015-02-10; просмотров: 6; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты