Рассмотрите граф на рисунке. а) Является ли граф связным? б) Запишите кратчайший путь из А в В. в) Запишите два простых пути из Д в Г.

а) Да. Из каждой вершины можно попасть в любую другую по рёбрам графа.

б) Между А и В есть два пути длины 2: А—Б—Е—В имеет длину 3, а А—Д—Е—В также длину 3. По рисунку рёбра А—Б, Б—Е, Е—В; А—Д, Д—Е, Е—В. Поэтому кратчайшая длина равна 3.

в) Два простых пути: Д—Е—Г и Д—А—Б—Е—Г.

Ответ: а) да; б) А—Д—Е—В (или А—Б—Е—В); в) Д—Е—Г и Д—А—Б—Е—Г.