Точка сочленения: различия между версиями

47 байт добавлено ,  2 года назад
м
Нет описания правки
(→‎Поиск шарниров: Именно метка входа; есть ещё метка выхода!)
м
Метки: визуальный редактор правка с мобильного устройства правка из мобильной версии
{{значения|Шарнир (значения){{!}}Шарнир}}
 
'''Шарниром''' в [[Теория графов|теории графов]] называется вершина [[Граф (математика)|графа]], при удалении которой количество [[Компонента связности графа|компонент связности]] возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».
 
== Определения ==
Вершина <math>v</math> графа <math>G</math> называется '''шарниром''', если [[Глоссарий теории графов#П|подграф]] <math>G_1</math>, полученный из графа <math>G</math> удалением вершины <math>v</math> и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф <math>G</math>.
[[Файл:Sample_graph.svg|frame|Граф, содержащий два шарнира (вершины 2 и 5) и три блока (12, 2345, 56).]]