Таблицы Брадиса

Подграфом данного графа называется граф,

Подграфом данного графа называется граф,

Элементы математики в задачах - Г. А. Мерзон

Заметим, что вершину В теперь можно единственным образом соединить с вершинами Б и Е так, чтобы не появилось пересече­ний. А после проведения ребер ВБ и ВЕ мы видим, что ребра АБ и СЕ теперь обязательно пересекутся либо друг с другом, либо с уже проведенными ребрами.

Существует и другой способ решения, использующий задачу 32. Заметим, что если граф К5 вложен в плоскость, то все грани обязаны быть треугольниками. Посчитав число граней и ребер графа К5 и сопоставив их с задачей 32а, приходим к противоречию. Аналогично, если двудольный граф К3,3 вложен в плоскость, то все грани обязаны быть четырехугольниками и можно применить задачу 32б.

Теория графов 2

Определение 7. Подграфом данного графа называется граф, кото­рый получается из данного выкидыванием некоторых вершин и ре­бер (дуг).

Два неориентированных графа называются гомеоморфными, если один можно получить из другого следующими операциями: взять ребро и добавить посередине этого ребра вершину; взять вершину степени 2 и заменить ее и выходящие из нее ребра на одно ребро (заметим, что эти две операции взаимно обратны).

Задача 34* (теорема Понтрягина — Куратовского). Докажите, что неориентированный граф планарен тогда и только тогда, когда у него нет подграфа, гомеоморфного К5 или К3,3.

Ш Последняя задача является очень сложной и одновременно очень замечательной. Красивое доказательство этого факта придумано Юрием Макарычевым (когда он был школьником 10 класса 57 шко­лы). См.: А. Б. Скопенков, Вокруг критерия Куратовского планарности графов // Математическое просвещение. Сер. 3. Вып. 9 (2005).

 

 

 

 

е