Консультация № 187115
18.01.2013, 09:41
199.26 руб.
0 1 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Орграф задан матрицей смежности. Необходимо:
а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).
[table]
[row][col]1 [/col][col]0 [/col][col]0 [/col][col]0 [/col][col]0 [/col][col]1 [/col][/row]
[row][col]1 [/col][col]1 [/col][col]1 [/col][col]0 [/col][col]1 [/col][col]0 [/col][/row]
[row][col]0 [/col][col]0 [/col][col]1 [/col][col]1 [/col][col]1 [/col][col]0 [/col][/row]
[row][col]0 [/col][col]0 [/col][col]1 [/col][col]0 [/col][col]1 [/col][col]0 [/col][/row]
[row][col]0 [/col][col]0 [/col][col]0 [/col][col]1 [/col][col]0 [/col][col]0 [/col][/row]
[row][col]1 [/col][col]0 [/col][col]0 [/col][col]0 [/col][col]0 [/col][col]0 [/col][/row]
[/table]

Обсуждение

давно
Мастер-Эксперт
17387
18345
19.01.2013, 03:54
общий
это ответ
Здравствуйте, Посетитель - 395932!

По матрице смежности нарисуем граф:


Пары вершин V3 и V4, V4 и V5 связаны парами дуг. Значит, вершины V3, V4, V5 взаимодостижимы. Они образуют первую компоненту сильной связности {V3, V4, V5}. Из этих вершин нельзя попасть ни в вершину V2, ни в вершину V1, ни в вершину V6. Вершина V2 недостижима ни из одной из остальных вершин орграфа и образует компоненту сильной связности {V2}. Вершины V1 и V6 связаны парами дуг и образуют тоже компоненту сильной связности {V1, V6}.

Заменив дуги рёбрами, получим такой неориентированный граф:


В этом графе вершины V1 и V2 имеют нечётные степени, равные 5, поэтому эйлерова цикла нет. Число вершин с нечётными степенями равно двум, поэтому эйлеров путь есть, например: V1 - V1 - V6 - V1 - V2 - V2 - V3 - V3 - V4 - V3 - V5 - V4 - V5 - V2.

С уважением.
Об авторе:
Facta loquuntur.
Форма ответа