More Related Content
Viewers also liked (13)
More from Alex Dainiak (19)
Основные определения теории графов. Деревья.
- 1. Дискретные структуры МФТИ, осень 2013 Александр Дайняк www.dainiak.com
- 2. Что такое граф? • Неформально, граф — набор объектов и связей между парами этих объектов Bob John Alice
- 3. Что такое граф? vertices edges
- 5. Какие бывают графы граф орграф мультиграф псевдограф
- 11. Маршруты
- 12. Пути, цепи и циклы • Цикл — это замкнутый маршрут (т.е. начало совпадает с концом) без повторяющихся рёбер • Простой цикл — это цикл без повторяющихся вершин • Путь — это незамкнутый маршрут без повторений рёбер • Цепь — путь без повторяющихся вершин • Длина цикла/цепи — это количество рёбер
- 13. Связность • Связный граф — это граф, в котором между любыми двумя вершинами существует путь • Компонента связности графа — это его максимальный связный подграф связный граф несвязный граф компоненты связности
- 14. Связность • Мост — льшим числом компонент связности • Точка сочленения — вершина, удаление которой льшим числом компонент связности мост
- 15. Полные и пустые графы
- 16. Независимые множества и клики • Клика в графе — это полный подграф • Независимое множество — это подмножество вершин, порождающее пустой подграф
- 17. Независимые множества и клики
- 18. Двудольные графы
- 21. Деревья • Дерево — это связный граф без циклов • Это дерево: • А это не деревья:
- 22. Деревья
- 23. Деревья
- 26. На заметку • Метод двойного подсчёта • Индукция в теории графов возможна по самым разным параметрам • У одного объекта может быть много разных определений, разными определениями удобно пользоваться в разных контекстах