133
правки
Изменения
Нет описания правки
{{Определение
|id = pawclaw
|neat = 1
|definition = '''Лапой''' (англ. ''pawclaw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный ]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>.
}} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]]
{{Определение
|id = paw_centerclaw_center
|neat = 1
|definition ='''Центром лапы''' (англ. ''paw claw center'') называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени ]] три в лапе.
}}
{{Определение
|id = minimum_barrier
|neat = 1
|definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimum barrier'') называется барьер минимальной мощности.
}}
{{Теорема
|id = theorem_about_pawtheorem_about_claw
|statement = Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>, тогда каждая вершина <tex>B</tex> {{---}} центр лапы в <tex>G</tex>.
|proof = Предположим, что <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя [[Отношение связности, компоненты связности#def2 | компонентами связности]] графа <tex>G \setminus B</tex>. <br>
