1632
правки
Изменения
м
rollbackEdits.php mass rollback
Вагнер опубликовал теорему в 1937, после публикации в 1930 [[Теорема_Понтрягина-Куратовского|теоремы Куратовского]], согласно которой граф планарен тогда и только тогда, когда он не содержит в качестве подграфа разукрупнение одного из тех же самых запрещённых графов подграфов [[Укладка_графа_на_плоскости|гомеоморфных]] <tex> K_{5} </tex> и <tex> K_{3, 3} </tex>. [[Теорема_Понтрягина-Куратовского|Теорема Куратовского ]] сильнее теоремы Вагнера — разукрупнение [[Укладка_графа_на_плоскости|гомеоморфный]] подграф может быть преобразовано преобразован в минор того же типа путём стягивания всех, кроме одного, рёбер в каждом пути, полученном при разукрупненииразбиении ребра путем добавления вершины, а вот обратное преобразование из минора в разукрупнение [[Укладка_графа_на_плоскости|гомеоморфный]] подграф того же типа не всегда возможно. Аналогия теоремы Вагнера может быть распространена на теорию матроидов. В частности, те же самые <tex> K_{5} </tex> и <tex> K_{3, 3} </tex> появляются в описании [[Примеры_матроидов:_графовый_матроид|графовых матроидов]] запрещёнными матроидными минорами.
__TOC__
'''Минором графа''' (англ. ''Graph minor'') <tex>G</tex> будем называть граф <tex>H</tex>, если <tex>H</tex> может быть образован из <tex>G</tex> удалением рёбер и вершин или стягиванием рёбер.
}}
Миноры графов часто изучаются в более общем контексте миноров [[Примеры_матроидов:_графовый_матроид|графовых матроидов]]. В этом контексте обычно полагается, что графы связны, могут иметь петли и кратные рёбра (то есть, рассматриваются [[Основные_определения_теории_графов|псевдографы]], а не простые графы). Стягивание петли и удаление разрезающего ребра запрещены. При таком подходе удаление ребра оставляет ранг графа неизменным, а стягивание ребра всегда уменьшает ранг на единицу.
== Пример ==
