Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
46. ХРОМАТИЧЕСКОЕ ЧИСЛО ГРАФА. КРИТЕРИЙ 2-ХРОМАТИЧНОСТИ ГРАФА Сама р-раскраска графа - это разбиение вершин графа на несколько подмножеств, причём две вершины одного и того же подмножества не могут быть соединены ребром, а две вершины из разных подмножеств – могут. Можно привести аналогию с темой отношений эквивалентности. Любые две вершины одного цвета ребром не соединяются, а любые две вершины разного цвета – соединяются. Если продолжать аналогию, то хроматическое число Х(G) – это число, которое равно минимальному количеству цветов, на которые можно разбить вершины графа, чтобы любые две вершины одного цвета не соединялись ребром, а любые две вершины разных цветов – соединялись. ТЕОРЕМА. Если граф 𝐺 = (𝑉, 𝑈) - неориентированный связный граф без петель, то Х(G) = 2 тогда и только тогда, когда граф не содержит циклов нечётной длины. ДОКАЗАТЕЛЬСТВО. Доказывается в обе стороны. 1) Если Х(G) = 2, то граф не содержит циклов нечётной длины. 2) Если граф не содержит циклов нечётной длины, то Х(G) = 2. 1. Допустим, что всё-таки содержит. Тогда, раз цикл – нечётной длины (рёбер нечётное количество), то в нём участвует чётное количество вершин (например, если только одно ребро, то будет две вершины, т.е. как отрезок; если 3 ребра, то 4 вершины и тд). Пусть это цикл 𝐶 = 𝑣𝑖1 𝑣𝑖2 … 𝑣𝑖2𝑝 (p здесь с раскраской никак не связано). Причём здесь имеется в виду, что вершины 𝑣𝑖1 и 𝑣𝑖2𝑝 совпадают как начало и конец цикла. Так как любые две соседние вершины в цикле соединены ребром, то их раскраска в цвета будет чередоваться. Пусть вершины с чётными индексами покрашены в один цвет, с нечётными – в другой цвет. Тогда вершины 𝑣𝑖1 и 𝑣𝑖2𝑝 будут покрашены в разные цвета (из-за того, что разные по чётности индексы), но с другой стороны, опять же, эти вершины совпадают как начало и конец цикла. Противоречие. 2. Здесь мы просто строим разбиение всех вершин графа на два разных подмножества и доказываем, что вершины одного подмножества не соединены ребром, а разных – соединены. Алгоритм разбиения такой: берём первую вершину и соотносим её в любое из подмножеств (пусть в V1), потом соседние с этой вершиной – в V2, потом соседние с новыми вершинами из V2 – в V1, и тд. Теперь покажем, что такое разбиение удовлетворяет определению раскраски. От противного: пусть вершины 𝑣1 и 𝑣2, например, из V1 соединены ребром. Эти вершины включаются в V1 на одном и том же шаге. Иначе если бы были включены на разных шагах, то была бы примерно такая ситуация: Но тогда получается, что из 𝑣1 и 𝑣2 связывает целый путь длины 2, а не одно ребро, что довольно-таки плохо. Поэтому в этом случае на месте вершины 𝑣 должна быть вершина 𝑣2, а значит, 𝑣1 и 𝑣2 покрашены в разные цвета, а не в один. Несостыковка. Тогда по построению разбиений в вершины 𝑣1 и 𝑣2 (в конспектах они 𝑎 и 𝑏) ведут одинаковые пути 𝑤1 и 𝑤2. Тогда рассматриваем цикл 𝐶 = 𝑣0𝑎𝑏𝑣0. Но это цикл нечётной длины, так как здесь 3 ребра: (𝑣0, 𝑎), (𝑎, 𝑏) и (𝑏, 𝑣0), противоречие. Вопросы к экзамену по ДМ (I курс ФПМ) 1 семестр (2020-21 уч. г) 1. Отображения. Обратные отображения. + 2. Мощность множеств. + 3. Отношения. Представление и операции над отношениями. + 4. Бинарные отношения на множестве. + 5. Отношения эквивалентности. + 6. Отношения порядка. + 7. Основные комбинаторные правила. + 8. Размещения. - 9. Сочетания без повторений. + 10. Сочетания с повторениями. + 11. Разбиения множеств на части. + 12. Формула включений – исключений. - 13. Ф.А.Л. Существенность переменных. + 14. Формулы. Представление функций формулами. 15. Эквивалентность формул. Теорема о замене равных. Соотношения эквивалентности. - 16. Теорема о разложении ФАЛ. - 17. Минимизация ДНФ. + 18. Геометрическая интерпретация минимальной ДНФ. + 19. Максимальные конъюнкции. + 20. Полные системы функций. Теорема редукции. + 21. Полиномы Жегалкина. + 22. Классы Т0 и Т1. + 23. Двойственные функции. + 24. Класс S. Лемма о не самодвойственной функции. + 25. Класс M. Замкнутость. + 26. Лемма о немонотонной функции. + 27. Класс L. Лемма о нелинейной функции. + 28. Критерий полноты в P2. 29. Предполные классы и их свойства. 30. Схемы из функциональных элементов. 31. Двоичный сумматор 32. Графы. Представление графов. 33. Пути и циклы в графах. 34. Транзитивное замыкание графов. 35. Представление графов в трёхмерном пространстве 36. Не планарность графов K33 и A5. 37. Критерий планарности графов. 38. Деревья и их свойства. 39. Циклы Эйлера. Теорема Эйлера (необходимость). 40. Циклы Эйлера. Теорема Эйлера(достаточность). 41. Циклы Гамильтона. Переборный алгоритм. 42. Достаточное условие существования циклов Гамильтона. 43. Суммы графов. Представление циклов графами. 44. Фундаментальное семейство циклов (построение). + 45. Фундаментальное семейство циклов (доказательство фундаментальности) + 46. Хроматическое число графов. Критерий 2-хроматичности. + |