Найти число точек сочленения в графе

Предмет: Математика
Раздел: Теория графов

Задание: Найти число точек сочленения в графе.

Определение:
Точка сочленения (или точка артикуляции) в графе — это вершина, удаление которой увеличивает число связных компонент графа. Иными словами, если удалить эту вершину и все ребра, инцидентные ей, граф распадется на большее количество связных частей.

Анализ графа по изображению:

На изображении представлен граф, состоящий из следующих элементов:

• Вершина слева, из которой выходит ребро вверх к "висячей" вершине (сторожок),
• Ребро ведет в круг, внутри которого есть структура с вершинами и ребрами,
• Внутри круга есть вершина, от которой отходят три ребра (в форме "веток"),
• Есть ребро, соединяющее левую вершину с вершиной внутри круга.

Шаги решения:

1. Рассмотрим вершину слева, из которой выходит ребро вверх и ребро направо (к кругу). Если удалить эту вершину, то "висячая" вершина сверху отсоединится, а также граф разделится на две части (левая и круг). Значит, эта вершина — точка сочленения.

2. Рассмотрим вершину внутри круга, от которой отходят три ребра (в форме "веток"). Если удалить эту вершину, то три "ветки" внутри круга станут несвязными между собой. Значит, эта вершина — точка сочленения.

3. Остальные вершины либо "висячие" (сторожки), либо не разделяют граф на части при удалении.

Итог:
Число точек сочленения в графе равно 2.

Ответ:
2