решения. База P*
решения. База P* конденсации G* графа G состоит из таких вершин графа G*, в которые не заходят ребра. Следовательно, базы графа G можно строить так: из каждой сильной компоненты графа G, соответствующей вершине базы P* конденсации G*, надо взять по одной вершине - это и будет базой графа G.
3.4.3. Двусвязность
Иногда недостаточно знать, что граф связен. Может возникнуть вопрос, насколько “сильно связен” связный граф. Например, в графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения, или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком.
Пример. Разделимый граф и его двусвязные компоненты. Точки сочленения вершины с номерами 4, 5 и 7.
Точку сочленения можно определить иначе. Вершина t является
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
