Есть ли в графе, изображённом на рисунке 30, путь: а) из вершины А в вершину С; б) из вершины В в вершину F? Связный ли это граф?

Решение:

а) Путь из вершины А в вершину С:

Рассмотрим граф на рисунке 30. Вершины А и С соединены рёбрами через вершину D. Путь может быть следующим: A → D → C.

б) Путь из вершины В в вершину F:

В графе на рисунке 30 нет вершины F. В графе присутствуют вершины A, B, C, D, E. Вершины B и F есть на рисунке 31, но не на рисунке 30. Поэтому пути из вершины В в вершину F в графе на рисунке 30 нет.

Связный ли это граф?

Граф называется связным, если любые две его вершины соединены путём. В данном графе (рисунок 30) все вершины (A, B, C, D, E) соединены между собой. Например, из A можно попасть в E через D (A-D-E). Из B можно попасть в E через C и D (B-C-D-E).

Ответ:

а) Да, путь из А в С существует (например, A-D-C).

б) Нет, в графе на рисунке 30 нет вершины F.

Граф на рисунке 30 связный.