Представление о связности графа. Обход графа (эйлеров путь)

Задание 1. Изучить предложенный материал и основные понятия выписать в тетрадь.

Две вершины в графе связны, если существует соединяющая их цепь (отличаем от смежных!)

Граф называется связным, если для любых двух его вершин имеется путь, соединяющий эти вершины (из любой вершины можно попасть в любую)

Обходы графа

Часто требуется обойти все вершины графа в определённом порядке, например, для проверки его на связность или упорядочения задач при планировании (топологическая сортировка графа). Существует два стандартных метода обхода графа - обход в глубину и обход в ширину.

Обход в глубину.

Обход в глубину можно описать так: представьте, что вы в лабиринте. Идите всегда прямо, а на всех развилках выбирайте самый левый путь. Упёршись в тупик, возвращайтесь обратно до последней развилки и выбирайте следующий путь слева. Продолжайте, пока не обойдёте весь лабиринт.

Обход в ширину.

Обход в ширину можно наглядно представить себе так: в какой-то стартовой точке лабиринта разливается жидкость, и она начинает равномерно заполнять все его помещения, продвигаясь все дальше. При этом в каждый момент времени все точки края разливающейся воды находятся на одном расстоянии от начала.

Этот обход, как и обход в глубину, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Задание 2

Укажите эйлеров путь в предложенных графах

Решение:

А) Эйлеров путь: А-В-Г-Д-Б-В-Д-А-Г-Б-А

В)   

Г)

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте