Изменения

Перейти к: навигация, поиск

Теорема Вагнера

2 байта убрано, 23:02, 3 декабря 2016
Нет описания правки
Вагнер опубликовал теорему в 1937, после публикации в 1930 [[Теорема_Понтрягина-Куратовского|теоремы Куратовского]], согласно которой граф планарен тогда и только тогда, когда он не содержит подграфов [[Укладка_графа_на_плоскости|гомеоморфных]] <tex> K_{5} </tex> и <tex> K_{3, 3} </tex>. [[Теорема_Понтрягина-Куратовского|Теорема Куратовского]] сильнее теоремы Вагнера — [[Укладка_графа_на_плоскости|гомеоморфный]] подграф может быть преобразовано преобразован в минор того же типа путём стягивания всех, кроме одного, рёбер в каждом пути, полученном при разукрупнении, а вот преобразование из минора в разукрупнение того же типа не всегда возможно.
__TOC__
Анонимный участник

Навигация