More Related Content
Viewers also liked (14)
More from Alex Dainiak (19)
Автоморфизмы графов. Перечисление графов.
- 1. Дискретные структуры МФТИ, осень 2013 Александр Дайняк www.dainiak.com
- 2. Графы и их представления
- 3. Графы и их представления
- 6. Изоморфизм графов • Упражнение. Данное выше формальное определение изоморфных графов «работает» только для графов без петель и кратных рёбер. Дайте формальное определение изоморфизма, пригодное для мульти- и псевдографов.
- 7. Изоморфизм графов • Поскольку изоморфные графы с точки зрения структуры идентичны, мы часто будем считать их одним и тем же графом • Любая характеристика графа (числовая или качественная), зависящая лишь от структуры графа (т.е. равная у любой пары изоморфных графов), называется инвариантом графа • Пример: количества вершин и рёбер графа являются инвариантами
- 8. Изоморфизм графов Если требуется определить, являются ли два данных графа изоморфными, то • для доказательства неизоморфности графов надо указать инвариант, значение которого различается у этих графов • для доказательства изоморфности нужно указать, какая вершина первого графа соответствует какой вершине второго
- 9. Автоморфизмы Автоморфизм графа — это изоморфизм графа с самим собой (перестановка вершин, переводящая граф сам в себя). Пример автоморфизмов:
- 10. Автоморфизмы
- 11. Различные графы vs. Неизоморфные графы
- 22. Количество неизоморфных деревьев Пример: Видно, что оценка теоремы неточна: «код» дерева получится другим, например, при другом упорядочении поддеревьев.
- 23. Формула Кэли для числа различных деревьев
- 24. Доказательство формулы Кэли: кодирование Прюфера • Последовательно проделываем: • Берём лист дерева с наименьшим номером, удаляем его, а его соседа выписываем • Поступаем так, пока в дереве не останется всего две вершины • Выписанный вектор и будет кодом дерева
- 25. Доказательство формулы Кэли: кодирование Прюфера Алгоритм кодирования дерева: • Берём лист дерева с наименьшим номером, удаляем его, а его соседа выписываем • Поступаем так, пока в дереве не останется всего две вершины
- 26. Доказательство формулы Кэли: кодирование Прюфера
- 27. Доказательство формулы Кэли: кодирование Прюфера A B ребро