Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Наибольшее  первыми.

(v4, v1, v2, v3, v5, v6)

Н
аименьшее  последними.
(v4, v3, v5, v2, v1, v6)


3. Раскраска ребер
Пусть есть G = (V, E), где |V| = p, |E| = q. Тогда реберной k-раскраской называется некоторая функция , задающая отображения множества E, т. е. : E  A = {a1, … ak}
Граф называется k-раскрашиваемым, если существует правильная раскраска ребер.
Минимальное число k, при котором существует правильная реберная k-раскраска называется реберным хроматическим числом или индексом.
Граф G называется реберно k-хроматическим, если хроматический индекс равен k.



Хроматический индекс для полного графа с четным числом вершин равен:
(K2n) = 2n –1
и с нечетным числом вершин
(K2n + 1) = 2n +1
Пример можно проиллюстрировать:





Контрольные вопросы.

1. 
   Какой граф называется плоским, планарным?
   
2. 
   Сформулировать теорему Эйлера для плоского графа, критерии планарности.
   
3. 
   Дать определение жордановой кривой, теоремы Жордана, грани плоского графа.
   
4. 
   Какая раскраска называется правильной?
   
5. 
   Сформулировать определение хроматического числа, хроматического индекса
   
6. 
   Сформулировать теорему Кенига
   
7. 
   Раскраска. Последовательно раскрасить граф G1 и G2; найти хроматическое число, хроматический индекс. Привести пример графа, у которого число красок будет зависеть от порядка обхода вершин.
   

Лекция 19. Граф-дерево и граф-лес. Связность. Цикломатическое число графа (2 часа)
План:
1. Основные понятие
2. Задачи о кратчайших расстояниях на графах.
3. Алгоритм Крускала
4. Алгоритм Прима
Ключевые слова: дерево, лес, корень, корневая дерева, поток.