Содержание
- 2. Интегральная микросхема состоит из слоев миниатюрных микросхем, впечатанных в пластину. Важно исключить пересечение проводов в местах,
- 3. Примеры.
- 4. Задача. Предоставление двух видов коммунальных услуг двум домам или трех видов коммунальных услуг двум домам
- 5. Определения. Планарным графом называется граф, который может быть изображен в плоскости так, что его ребра не
- 6. Теорема. Если G - связный планарный граф, содержащий v вершин, e ребер и f граней, то
- 7. Теорема. Каждый планарный граф G содержит вершину степени 5 или менее. Теорема. Если два связных графа
- 8. Пример. Граф является планарным
- 9. Пример. Графы являются планарными
- 10. Пример. Граф Петерсена не является планарным. Граф содержит подграф, гомеоморфный K3,3
- 11. Раскраска графов
- 12. Проблема 4-хкрасок. Карту необходимо раскрасить, используя только 4 цвета так, чтобы любые две граничащие страны были
- 13. Пример. Карта Возможная окраска Граф – ребра в качестве границ, грани – в качестве стран.
- 14. Пример. Двойственный граф G' формируется путем замены граней (стран) вершинами и соединения их ребрами, если грани
- 15. Пример. Граф Двойственный граф G' Грани графа G стали вершинам графа G'. Исходная проблема раскрашивания стран
- 16. Задача (Г.Д. Бирхгоф)(G.D. Birkhoff). Зафиксируем для графа количество цветов. Сколько существует способов раскрашивания вершин при условии,
- 17. Пример. Имеются 4 цвета и необходимо раскрасить граф G Для раскрашивания 1-ой вершины a имеется 4
- 18. Пример (предыдущий). Имеется λ цветов для раскрашивания графа G. Имеется λ цветов для раскрашивания вершины a,
- 19. Определение. Пусть G – граф. Раскраской графа G называется окрашивание вершин графа G такое, что никакие
- 20. Пример. Пусть граф G состоит из пяти изолированных вершин, так что в нем нет ребер, нет
- 21. Пример. Пусть G - граф K5 . Каждая из пяти вершин является смежной с остальными 4-мя
- 22. Пример. Пусть G - граф Kn . СG(λ) = λ (λ - 1) (λ - 2)
- 23. Теорема. Если G = G1 ∪ G2 ∪ G3 ∪ … ∪ Gn , где G1
- 24. Раскрашивание только связных графов. Граф G( V, E). e = {a, b} - ребро. Граф Ge
- 25. Пример. Пусть G -граф Граф Ge Граф G/e
- 26. Пример. Пусть G -граф Граф Ge Граф G/e
- 27. Теорема. Для произвольного планарного графа G с ребром e имеет место равенство CGe (λ) = CG
- 28. Теорема. Для произвольного планарного графа G с n вершинами функция СG (λ) представляет собой многочлен n
- 29. Теорема. Для произвольного непустого связного графа G постоянный член в СG (λ) равен 0. Если граф
- 30. Теорема. Произвольный планарный граф G можно раскрасить, используя только пять цветов.
- 32. Скачать презентацию