22. Планарные графы. Теорема Куратовского-Понтрягина о планарных графах.
К списку вопросов
Граф, который может быть начерчен таким образом, чтобы его ребра пересекались только в вершинах, называется планарным.
Задача: На одном участке земли построены три дома и вырыто три колодца для их обитателей.
Природа страны и её климат таковы, что колодцы часто пересыхают, поэтому важно, чтобы от каждого из домов имелся доступ к каждому из трёх колодцев.
Спустя некоторое время обитатели домов поссорились друг с другом и решили проложить дорожки к трём колодцам так, чтобы по пути к колодцу и обратно им не приходилось встречаться друг с другом
решение задачи невозможно.
А, В, С –дома; X, Y, Z – колодцы.
Условия планарности графа.
Элементарная цепь - цепь, у которой все внутренние вершины имеют степень 2 и множество этих вершин не пусто.
Операция сжатия элементарной цепи - удаление всех её внутренних вершин.
Теорема Куратовского-Понтрягина (о необходимом и достаточном условии планарности графа)
Для того, чтобы граф был планарным необходимо и достаточно, чтобы он не содержал в качестве подграфов никакого графа, который можно сжать до K3,3 или K5.
К списку вопросов
