Найдите число компонент связности для каждого из трёх графов, изображённых на рисунке 80.
а) Вверху три вершины соединены двумя рёбрами. Ниже одна часть из четырёх вершин: треугольник и ребро, выходящее из одной его вершины; отдельно расположены две пары вершин, соединённых рёбрами. Пересечения линий без отмеченных точек вершинами не являются.
б) Все отмеченные вершины связаны в одну сеть рёбер.
в) Четыре отдельных ребра, отдельная цепочка из трёх рёбер и одна изолированная вершина. Пересечения без отмеченных точек не являются вершинами.
По определению из §
а) В верхней части рисунка три вершины соединены двумя рёбрами в один путь. Это первая компонента.
Ниже слева имеется вершина с тремя выходящими рёбрами: одно идёт вверх вправо, одно вправо, одно вниз вправо. Две её нижние правые соседние вершины также соединены между собой. Эти четыре вершины образуют вторую компоненту.
Отдельное наклонное ребро из верхней средней вершины к средней левой образует третью компоненту. Ещё одно ребро внизу слева образует четвёртую. Пересечения отрезков не соединяют эти части, так как в них нет отмеченных вершин. Всего
б) От левых вершин можно дойти до правой средней вершины, а от неё — до нижних вершин. Через нижнюю левую вершину и восходящее ребро достигаем правой верхней части, а затем самой верхней пары. Значит, все части соединены путями. Граф имеет одну компоненту.
в) Четыре отдельных ребра дают четыре компоненты по две вершины. Справа три ребра соединены через две отмеченные вершины в одну цепочку из четырёх вершин — это пятая компонента. В остальных местах пересечений точек нет, поэтому перейти с одной части на другую нельзя. Отдельная точка справа — шестая компонента.
Итак, числа компонент равны
а)
б)
в)
