Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 87, §20
№131. Есть ли в графе, изображённом на рисунке 30, путь:
а) из вершины A в вершину C; б) из вершины B в вершину F?
Связный ли это граф?
Дано:
граф на рисунке 30: вершины A, B, C, D, E, F
Найти:
есть ли путь из A в C; есть ли путь из B в F; связный ли граф
Путь из вершины в вершину — это последовательность рёбер, идя по которой можно добраться из первой вершины во вторую (п. 20). Найдём рёбра графа: AB, BC, BD, CD, AD и EF.
а) Из A можно пойти по ребру AB в вершину B, а из B по ребру BC — в вершину C. Путь ABC существует (на рисунке он красный). Есть и другие, например ADC. Ответ: да.
б) Вершина F соединена только с вершиной E (ребро EF), а вершина E — только с F. Из вершины B можно попасть в A, C и D (и по ним больше никуда), но ни одно ребро не ведёт от вершин A, B, C, D к E или F. Значит, пути из B в F нет. Ответ: нет.
Связный ли граф? Граф называют связным, если любые две его вершины соединены путём. Здесь вершины B и F путём не соединены, поэтому граф не связный: он состоит из двух отдельных частей — «четырёхугольника» ABCD и ребра EF (см. рисунок 29, б — несвязный граф).
Ответ: а) Да; б) нет. Граф не связный: он состоит из двух отдельных частей.
