Лапы и минимальные по включению барьеры в графе — различия между версиями
| Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|definition='''Центр лапы''' {{---}} вершина степени 3 в лапе | |definition='''Центр лапы''' {{---}} вершина степени 3 в лапе | ||
| + | }} | ||
| + | |||
| + | {{Теорема | ||
| + | |id=th1 | ||
| + | |statement=Пусть <tex>B</tex> - минимальный по включению [[Декомпозиция Эдмондса-Галлаи#def1 | барьер]] <tex>G</tex>, тогда каждая вершина <tex>B</tex> - центр лапы в <tex>G</tex>. | ||
| + | |proof=Пусть <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя компонентами связности графа <tex>G \setminus B</tex> | ||
}} | }} | ||
Версия 01:16, 12 декабря 2017
| Определение: |
| Лапой называется индуцированный подграф графа , изоморфный двудольному графу |
| Определение: |
| Центр лапы — вершина степени 3 в лапе |
| Теорема: |
Пусть - минимальный по включению барьер , тогда каждая вершина - центр лапы в . |
| Доказательство: |
| Пусть не является центром лапы. Тогда смежна не более чем с двумя компонентами связности графа |
