Точка - сочленение
Cтраница 1
Точки сочленения можно обнаружить с помощью грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из наших алгоритмов обхода графа для проверки связности оставшейся части. Если оставшийся граф связен, то удаленная вершина не является точкой сочленения. При таком подходе мы должны выполнить N обходов графа с N вершинами, что потребует 0 ( 7V2) операций. Однако сохраняя незначительное количество дополнительной информации при обходе графов, можно обнаружить все точки сочленения и компоненты двусвязности при единственном обходе. [1]
 |
Связный граф с тремя компонентами двусвязности. [2] |
Точками сочленения в связном графе служат такие вершины, удаление которых превращает граф в несвязный. Точки сочленения - это такие вершины, которые принадлежат сразу двум компонентам двусвязности. Определение точек сочленения и компонент двусвязности тесно связаны между собой. [3]
Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент; ребро с таким же свойством называется мостом. Таким образом, если v - точка сочленения связного графа G, то граф G-v не связен. Неразделимым графом называется связный, непустой, не имеющий точек сочленения граф. [4]
Каждая точка сочленения резисторов на схеме (16.22) характеризуется своим потенциалом, причем все точки связаны между собой соответствующими сопротивлениями. Некоторые из этих сопротивлений могут иметь бесконечно большое значение, что соответствует отсутствию реакции по данному маршруту. [5]
Наличие точек сочленения и, следовательно, блоков в графе уменьшает число разрезаний, порождаемых на каждом шаге, до числа, прямо пропорционального числу разрезаний, генерируемых в каждом блоке, если блок разрезается независимо от других. [6]
 |
Осговное дерево, построенное поиском в глубину. 208. [7] |
Если а - точка сочленения, то удаление ребра а и всех ребер, инцидентных ему, расщепляет граф G по крайней мере на две части. [8]
Пусть х - точка сочленения графа О, принадлежащая В. [9]
Кубический граф имеет точку сочленения тогда и только тогда, когда он имеет мост. [10]
 |
Разделимый граф ( а и его двусвязные компоненты ( Ь. Точки сочлене ния. b, f и i. [11] |
Такая вершина называется точкой сочленения или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Например, вершины Ь, / и i на рис. 8.7 ( а) являются точками сочленения, при этом других точек сочленения нет. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком. Отыскание точек сочленения и двусвяз-ных компонент данного графа важно при изучении надежности коммуникационных и транспортных сетей. Это важно также и при определении других свойств графа G, таких, например, как пла-нарность, так как часто полезно разложить G на его двусвязные компоненты и изучать каждую из них в отдельности ( разд. Это соображение позволяет нам использовать поиск в глубину для нахождения точек сочленения и двусвязных компонент графа за операций. [12]
Вершина графа называется точкой сочленения, если ее удаление приводит к увеличению числа компонент связности. [13]
Если v является точкой сочленения, то удаление ее из связного графа разбивает последний, по крайней мере, на две компоненты и, следовательно, все цепи, связывающие любую пару вершин, взятых из различных компонент, должны проходить через и. С другой стороны, если все цепи, связывающие некоторую пару вершин, проходят через и, то удаление v делает граф несвязным, и, следовательно, v есть точка сочленения. [14]
Вершина и является точкой сочленения связного графа G, если граф HG-v, получаемый удалением v и всех ребер, инцидентных с v, несвязен. [15]
Страницы: 1 2 3 4