![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Задание 5.Произвести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа. Решение:Необходимо исходить из того, что граф называется правильно раскрашенным, если его смежные вершины( связи) раскрашены в разные цвета. Примечание: Обозначим цвета через числа натурального ряда. Номер рядом с каждой вершиной (связью) обозначает определенный цвет. Вершинная раскраска:
1 2Хроматическое число равно 3.
2 3 1 Реберная раскраска: 1Хроматическое число равно 4.
2 3 2 3
1 4 Задание 6. Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди. Решение:В основе алгоритма упорядочивания лежит матрица смежности.
L00 3 0 3 1 L1* 1 * 1 0 L2* 1 * 0 * L3* 0 * * * Изоморфный упорядоченный граф выглядит следующим образом:
Уровни Функция Гранди:
3 2 1 0 Порядковая функция: 3 0
0 2 1
|