Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 21 из 31

(возможно, с пересадками)?
б) В городе нет ни мостов, ни туннелей, ни тупиков. Все перекрестки имеют крестообразную форму и образованы пересечением ровно двух улиц

Задачи по комбинаторной теории графов
303
Совершая инспекционную поездку по городу, губернатор на каждом перекрестке поворачивал либо направо, либо налево. Через некоторое время шофер губернатора заметил, что они едут по дороге, по которой уже проезжали. Докажите, что они едут в туже сторону, что ив первый разв Два альпиниста стоят на уровне моря на противоположных сторонах горного хребта (плоской ломаной с конечным числом звеньев),
расположенного целиком над уровнем моря. Докажите, что они смогут встретиться, оставаясь в процессе движения все время на одной высоте над уровнем моря. Теорема Турана. а) Пусть в некоторой компании среди любых трех человек найдутся два друга. Обязательно ли эту компанию можно разбить на две группы так, чтобы любые два человека из одной группы были друзьями?
б) Найдите наибольшее возможное количество ребер в графе с n вершинами, если известно, что среди любых трех его вершин есть две, не соединенные ребром.
в)* Тоже для четырех его вершина) Лемма о паросочетаниях. Пусть есть несколько (конечное число) юношей и девушек, причем каждый юноша знаком с некоторым
(возможно с нулевым) числом девушек.
Докажите, что всех юношей можно женить на (попарно различных)
девушках, если и только если для любого множества наших юношей число девушек, знакомых хотя бы с одним из них, не меньше числа этих юношей.
б)
Теорема Холла. Пусть X — непустое конечное множество,
а X
1
, . . . , X
n
— его подмножества.
Докажите, что в каждом из них можно выбрать по элементу x i
∈
∈ X
i так, чтобы все x были различны, если и только если для каждого k ∈ {1, . . . , n} объединение любых k из этих подмножеств имеет не меньше, чем k элементов. Теорема Уитни. Число P
G
(n) правильных раскрасок графа с V вершинами в n цветов есть многочлен от n степени V .
5. В турнире без ничьих участвовало n команд. Каждая команда сыграла с каждой ровно по одному разу. Докажите, что можно так занумеровать команды числами 1, . . . , n, чтобы (i + я команда выиграла у й (для любого i = 1, . . . , n − 1).
6. На выборах в городскую Думу каждый избиратель, если он приходит на выборы, голосует за себя (если он является кандидатом) и за всех тех кандидатов, которые являются его друзьями. Прогноз социо-

Гл. 12. Миникурс по теории графов логической службы мэрии считается хорошим, если в нем правильно предсказано количество голосов, поданных хотя бы за одного из кандидатов, и нехорошим в противном случае. Докажите, что при любом прогнозе избиратели могут так явиться на выборы, что этот прогноз окажется нехорошим. а) Нарисуйте гамильтоновы циклы в графах правильных много- гранников.
б) Никакой граф, гомеоморфный букве θ (те. графу K
3,2
), не является гамильтоновым.
в)* Если из любой вершины графа (без петель и кратных ребер) с вершинами выходит не менее V/2 ребер, то этот граф гамильтонов.
Зачетные задачи 1 а 2 баба, б 5; 7 а).
Изоморфизмы графов
2)
(10–11)
И. Н. Шнурников
1. а) Сколько существует изоморфизмов K
5
→ K
5
; K
3,3
→ б) Изоморфны ли графы и G
3
, вершины каждого из которых занумерованы числами от 1 до 7, вершины графа G
k соединены ребром,
если либо i − j ≡ 1 mod 7, либо i − j ≡ k mod в) Постройте граф с наименьшим числом n, n > 1, вершин, такой что никакая нетождественная перестановка его вершин не является изоморфизмом. Симметричные графы. Мы будем работать со связными ориентированными графами с петлями и кратными ребрами. Пусть из каждой вершины графа выходят два ребра ив каждую входят два ребра.
Такой граф назовем симметричным, если для любой пары ребер a, b существует перестановка вершин графа (а если есть кратные ребра, то и перестановка их между собой, при которой все ребра графа переходят в ребра этого же графа, а ребро a переходит в ребро b (направления всех ребрах сохраняются. При этом никакое ребро не должно остаться на месте.
а) Для каждого натурального n придумайте два (неизоморфных)
симметричных графа с n вершинами каждый.
б) Придумайте симметричные графы си вершинами (не изоморфные графам из а)).
2)
Определение изоморфизма графов можно посмотреть вначале заметки Вокруг критерия Куратовского планарности графов, см. с. 315.

Задачи по топологической теории графов
305
в) Найдите все симметричные графы, которые имеют хотя бы одну петлю или хотя бы однократное ребро.
г) Найдите все симметричные графы с вершинами (p — простое число).
д) Найдите все симметричные графы сне более чем 8 вершинами.
е) Найдите все симметричные графы, которые можно нарисовать
(без самопересечений) на плоскости так, что для каждой вершины входящие ребра чередуются с выходящими.
ж)* Найдите все плоские симметричные графы. У Васи есть несвязный граф. Он всеми возможными способами удалил из этого графа по одной вершине и каждый из полученных графов нарисовал на отдельном листочке бумаге, после чего все листочки отдал Коле. Докажите, что Коля может восстановить исходный граф. Нерешенные задачи о вершинной и реберной реконстру- ируемости. а) Пусть G и e
G — связные графы с V , V > 3, занумерованными вершинами. Для каждого k ∈ {1, . . . , V } рассмотрим графы − k и e
G − k, полученные из графов G и e
G удалением в каждом из них вершины с номером k и всех выходящих из нее ребер. Пусть для всех k ∈ {1, . . . , V } графы G
k и e
G
k изоморфны. Верно ли, что графы и e

G изоморфны?
б) Пусть G и e
G — связные графы с E, E > 5, ребрами. Для каждого k ∈ {1, . . . , E} рассмотрим графы G
k и e
G
k
, полученные из графов G и соответственно путем удаления в каждом из них ребра с номером Пусть для всех k ∈ {1, . . . , E} графы G
k и e
G
k изоморфны. Верно ли,
что графы G и e

G изоморфны?
Зачетные задачи 1 а)–в); 2 а)–е); Задачи по топологической теории графов
3)
(9–11)
А. Б. Скопенков, И. Н. Шнурников
1. а) Докажите формулу Эйлера V − E + F = 2 для плоского связного графа с ребрами-отрезками (V , E и F — число вершин, ребер игра- ней соответственно) б) Найдите аналог формулы Эйлера для несвязного плоского графа с k компонентами связности.
3)
Используемые здесь определения плоского графа, его грани, гомеоморфизма и изоморфизма графов можно посмотреть вначале заметки Вокруг критерия Ку- ратовского планарности графов (см. с. 315).

Гл. 12. Миникурс по теории графов. Применения формулы Эйлера. а) Графы и не пла- нарны.
б) На плоскости отмечено n точек. Разрешается соединять некоторые две из них ломаной, не проходящей через другие точки. Два игрока по очереди соединяют ломаной какие-то две еще не соединенные точки. При этом требуется, чтобы эти ломаные не самопересекались и не пересекались нигде, кроме отмеченных точек. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре (в зависимости отв Выпуклых правильных многогранников (все грани — правильные многоугольники с одинаковым числом сторон, степени всех вершин равны) ровно 5 (с точностью до изоморфизма их графов).
Указание. Если не получается решить пункты а, б) ив, то решайте следующие пункты.
г) Для любого плоского связного графа без петель и кратных ребер,
имеющего более двух вершин, 2E > 3F и E 6 3V − д) В любом плоском графе есть вершина степени не более е) В любом выпуклом многограннике есть либо треугольная грань,
либо вершина степени ж) Если каждая вершина плоского связного графа имеет степень а в границе каждой грани ровно k ребер, то d 6 из) В любом планарном графе с хотя бы четырьмя вершинами найдется хотя бы четыре вершины степени не более пяти. Раскраска граней плоского графа в несколько цветов называется правильной, если любые две грани, имеющие общее ребро, окрашены в разные цвета.
а) Грани эйлерова плоского графа можно правильно раскрасить в 2
цвета.
б) Грани гамильтонова плоского графа можно правильно раскрасить в 4 цвета.
в) Вершины (или грани) любого плоского графа можно правильно раскрасить в 5 цветов. Гомологии и когомологии графов. а) В дереве нет подгра- фов без изолированных вершину которых степень каждой вершины четна.
б) Для данного графа обозначим через a число его подграфов без изолированных вершину которых степень каждой вершины четна. Тогда степень двойки. Выразите a через количества V вершин, E ребер и C компонент связности графа

Задачи по топологической теории графов
307
в) На ребрах дерева стоят знаки «+» и «−». Разрешается менять знаки на всех ребрах, выходящих из одной вершины. Тогда из любого узора можно получить любой другой.
г) Пусть b — наибольшее количество узоров из «+» и «−» на ребрах данного графа, ни один из которых нельзя получить из другого описанными выше операциями. Тогда b — степень двойки. Выразите b через V ,
E и д Операция стягивания ребра (отличного от петли) удаляет из графа это ребро и заменяет вершины A и B этого ребра на одну вершину а все ребра, выходящие из вершин A ив некоторые вершины, заменяет на ребра, выходящие из вершины C в те же вершины. Например,
если граф — простой цикл с четырьмя вершинами, то при стягивании любого его ребра получится простой цикл стремя вершинами. Докажите, что a и b инвариантны при стягивании ребра, и выведите отсюда,
что a = b.
5. связные графы. а) Из любого связного графа можно удалить вершину (вместе со всеми выходящими из нее ребрами) так, что он останется связным.
б) Для любых двух вершин выпуклого многогранника существуют три непересекающихся (нигде, кроме этих вершин) пути по его ребрам из одной вершины в другую.
в) В графе есть хотя бы одно ребро и при удалении любого ребра найдется путь между вершинами A и B. Докажите, что в этом графе между вершинами A и B найдутся два путине имеющих общих ребер.
г)*
Теорема Менгера. Граф остается связным после удаления любой вершины тогда и только тогда, когда любые две его вершины можно соединить k путями, пересекающимися только в этих двух вершинах. Изотопии в пространстве. а) Любой узел S
1
⊂ можно непрерывно и без самопересечений продеформировать в узел, лежащий в книжке стремя листами T × I ⊂ б) Любой графили даже поверхность с краем) N ⊂ можно непрерывно и без самопересечений продеформировать в граф, лежащий в книжке стремя листами T × I ⊂ R
3 7. В плоском графе с треугольными гранями выкинули вершину вместе с выходящими из нее ребрами.

а) Верно ли, что получившаяся грань ограничена простым циклом?
б) Верно ли, что если выкинуть еще одну вершину, то все грани опять будут ограничены простыми циклами

Гл. 12. Миникурс по теории графов в) Пусть в полученном графе степень каждой вершины не менее Верно ли, что любую вершину нового графа можно удалить и получить граф, все грани которого будут ограничены простыми циклами. а) Дан невыпуклый многоугольник с непрозрачными сторонами.
Назовем его ядром множество его внутренних точек, из которых видны все вершины многоугольника. Докажите, что если ядро многоугольника непусто, то его можно разрезать прямой на два многоугольника с непустым ядром, чтобы число сторону новых многоугольников было меньше, чему исходного.
б)
Теорема Фари. Плоский граф можно нарисовать на плоскости без самопересечений так, что все ребра будут отрезками.
в) Любой связный граф с g ребрами можно так нарисовать внутри правильного угольника, диаметрально противоположные стороны которого склеены, что некоторые ребра являются отрезками, а остальные ребра являются объединениями двух непересекающихся отрезков,
у каждого из которых один конец — вершина графа, а другой конец лежит на стороне 2g-угольника.
Зачетные задачи 1 а, б, 2 б, где а, б, 4 б, 5 а, 7 а, 8 а).
Указания
2. а) Приведем доказательство непланарности графа K
5
, основанное на формуле Эйлера. Пусть граф нарисован на плоскости без са- мопересечений. Тогда по формуле Эйлера 5 − 10 + F = 2. Значит, F = Нарисуем около каждого ребра графа K
5
, нарисованного на плоскости,
стрелку вправо и стрелку влево. Тогда число стрелок равно 2E = 20. Но поскольку граница каждой грани состоит не менее чем из трех ребер,
то число стрелок не меньше 3F = 21 > 20. Противоречие. Основываясь на этой идее, можно доказать непланарность графа г) Нарисуем около каждого ребра графа стрелку вправо и стрелку влево. Тогда число стрелок равно 2E. Поскольку граница каждой грани состоит не менее чем из трех ребер, то 3F 6 2E. По формуле Эйлера − E + F = 2. Значит, 6 = 3(V − E + F ) 6 3V − E, откуда E 6 3V − д) Если степень каждой вершины не меньше 5, то 2E > 6V . А это противоречит предыдущему пункту.
е) Допустим, что в некотором многограннике нет вершины степени и нет треугольной грани. Так как это многогранник, то степень каждой вершины не менее 4. Значит, 2E > 4V . Так как нет треугольных граней, то каждая грань содержит не менее чем 4 ребра. Значит, 2E > 4F Следовательно, 2 = V − E + F 6 0. Противоречие

Метод минимального контрпримера и спуск в графах
309
Метод минимального контрпримера и спуск в графах (А. Я. Канель-Белов
При решении многих задач используется так называемый метод минимального контрпримера (разновидность принципа крайнего, который заключается в следующем.
Предположим, что надо доказать, что объекта, удовлетворяющего некоторым свойствам, не существует. Предположим противное — тогда найдется (в некотором смысле) минимальный контрпример. После чего строят еще меньший контрпример и получают противоречие.
Понятие меньше подбирается в процессе доказательства. Особенно распространен такой метод решения в задачах на графы. При этом обычно ведется индукция сперва по числу вершин, потом по числу ре- бер.
Начнем с простейшего примера.
Доказательство теоремы Эйлера о плоских графах (формулировку см. нас и 316). Пусть граф G не удовлетворяет условиям теоремы Эйлера. Рассмотрим ребро графа G и пойдем по ребрам. В этом случае мы либо попадем в висячую вершину V , либо пройдем цикл.
В первом случае уничтожим вершину V и входящее в нее ребро При этом количества вершин и ребер уменьшатся на 1, а количество граней не изменится.
Во втором случае уничтожим ребро r из цикла. В этом случае количества граней и ребер уменьшатся на 1, а количество вершин не из- менится.
В обоих случаях граф остается связными мы получаем меньший контрпример.
Более содержательный пример — знаменитая теорема Дилуорса о частично упорядоченных множествах. Множество A с отношением ≺ называется частично упорядоченным, если отношение ≺ удовлетворяет следующим свойствам) a 6≺ a,
2) a 6≺ b либо b 6≺ a,
3) если a ≺ b и b ≺ c, то a ≺ Если a ≺ b или b ≺ a, то элементы a и b называются сравнимыми.
Если же a 6≺ b и b 6≺ a, то они называются несравнимыми. Цепью называется множество попарно сравнимых элементов, а антицепью — по

Гл. 12. Миникурс по теории графов парно несравнимых. Диаметром частично упорядоченного множества называется максимальный размер антицепи.
а) Количество цепей, на которые можно разбить частично упорядоченное множество, не меньше его диаметра.
б)
Теорема Дилуорса. Минимальное количество цепей, на которые разбивается частично упорядоченное множество, совпадает сего диаметром. Пусть G — граф, A и B — его вершины, не соединенные ребром.
а) Если есть k путей, соединяющих A и B и не имеющих промежуточных общих вершин, то при удалении любых k − 1 вершин вершины и B остаются водной связной компоненте.
б)
Теорема Менгера. Если вершины A и B не соединены ребром и при удалении любых k − 1 вершин вершины A и B остаются водной связной компоненте, то имеются k путей, соединяющих A и B и не имеющих промежуточных общих вершин. В каждый город ведет 3 дороги красная, синяя и белая. В зависимости от цветов входящих дорог, считая почасовой стрелке, города разделяются на два типа КСБ и КБС. Докажите, что разность количеств городов разных типов делится на 4. (Задача зонального этапа
Всероссийской олимпиады 1994 г. IMO, 2004, Shortlist. С конечным графом разрешается производить следующую операцию выбрать произвольный цикл длины и выбросить из него произвольное ребро. Дан полный граф из n вершин. Какое минимальное число ребер можно оставить с помощью этой операции. IMO, 2001, Shortlist. клика есть подмножество из k попарно знакомых людей. Известно, что каждые две клики имеют общего члена и нет клик. Докажите, что можно, удалив двух людей, все клики разрушить. IMO, 1992, Longlist. Дан граф G с n вершинами, m < n. Докажите, что G содержит подмножество из m + 1 вершины, степени которых отличаются не больше, чем на m − 1.
7. Докажите, что каждую конечную карту на плоскости можно правильно раскрасить в 5 цветов. (См. необходимые определения выше.)
См. также доказательство теоремы Куратовского (см. с. Указания к задачам. а) Ясно, что цепь и антицепь могут пересекаться по не более чем одному элементу. Поэтому количество цепей, на которые можно разбить частично упорядоченное множество, не меньше его диаметра

Метод минимального контрпримера и спуск в графах
311
б) Доказательство теоремы Дилуорса. Рассмотрим минимальный контрпример — множество M . Пусть C — цепь диаметра D. Тогда каждый элемент множества M \ D либо больше некоторого элемента из либо строго его меньше. Таким образом, M \ D есть несвязное объединение двух частей выше D) и ниже Если M
′
∪ D и M
′′
∪ D разбиваются на d цепей, то и все M разбивается на d цепей (каждая цепь склеивается из верхней и нижней половин).
Если M
′
6= ∅ и M
′′
6= ∅, то #(M
′
∪ D) < #M и #(M
′′
∪ D) < Мы осуществили спуск. В противном случае имеется не более двух максимальных антицепей: верхняя (если M
′
= ∅) и нижняя (если M
′′
= Рассмотрим случай наличия только верхней антицепи (случай наличия только нижней антицепи симметричен).
Пусть имеется единственная максимальная антицепь D и x ∈ D. Тогда имеет диаметр d − 1 ив силу минимальности контрпримера разбивается на d − 1 цепь C
1
, . . . , C
d−1
. Поэтому x ∪ есть искомое разбиение на d цепей.
Пусть имеются две максимальные антицепи и D
2
. Легко показать, что найдется пара таких элементов x ∈ и y ∈ D
2
, что x ≺ Тогда диаметр множества M \ {x, y} строго меньше диаметра M, и доказательство завершается аналогично. Доказательство теоремы Менгера. Доказательство основано на методе минимального контрпримера и похоже на доказательство теоремы Дилуорса.
Пусть G — минимальный контрпример. Назовем менгеровой цепочкой набор из минимального числа k вершин, разделяющих A и B. Назовем такое k = k(G) менгеровостью графа G. Выберем контрпример для минимально возможного k. Невозможность спуска накладывает на граф G условия, приводящие к противоречию.
Прежде всего, каждая вершина V ∈ G входит в менгерову цепочку,
т. к. иначе k(G − V ) = Более того, удаление любого ребра уменьшает менгеровость. Это значит, что если ребро r соединяет две вершины и C
2
, отличные от A и B, то найдется такой набор N из k − 1 вершин, что N ∪ и N ∪ {C
2
} — менгеровы цепочки.
Если некоторая вершина V соединена и си сто можно выбросить вместе с выходящими из нее ребрами и осуществить спуск.
Поэтому нет вершин, соединенных си одновременно.
Пусть M — менгерова цепочка из k вершин. Построим граф G
A
, оставив как есть вершины компоненты и цепочки M и ребра между этими вершинами, выбросив все другие компоненты и соединив вершину A напрямую со всеми вершинами из M . Аналогично строим граф G
B
. Если

Гл. 12. Миникурс по теории графов есть k непересекающихся путей, соединяющих A ив графах и, то также будет в G (путь строится из двух половинок).
Если количество вершин в каждом графе и меньше, чем в G, тов каждом из графов и G
B
, а значит, ив графе G, найдется k непересекающихся путей.
В противном случае либо G = G
A
, либо G = Так как приведенные рассуждения верны для любой менгеровой цепочки, то любая менгерова цепочка либо напрямую соединена с либо напрямую соединена с B. Следовательно, каждая вершина графа соединена либо с A, либо с B, ноне си одновременно.
Тогда есть две вершины, соединенные ребром e, одна из которых смежна с A, а другая с B. В силу минимальности k в графе G \ e найдется непересекающихся путей от A до B. Каждый из этих путей можно выбрать состоящим из трех ребер, и вместе с трехреберным путем, проходящим через ребро e, они дают k непересекающихся путей.
Случайные графы (А. М. Райгородский
Зафиксируем натуральное число n, а также p ∈ [0, 1] и q = 1 − p. Рассмотрим множество V = {1, . . . , n}. Вероятностью графа G = (V , без петель и кратных ребер назовем P (G) := p
|E|
q
C
2
n
−|E|
. Вероятностью произвольного семейства (или, что тоже самое, свойства) графов с множеством вершин V называется сумма вероятностей входящих в него графов. Если Ω — множество всех графов с n вершинами, то P (Ω) = Говоря научно, ребра графа выбираются с помощью схемы испытаний Бернулли, те. каждое ребро независимо от остальных имеется в графе с вероятностью p ∈ [0, 1]; поэтому с вероятностью q = 1 − p его нет в графе. В результате возникает случайный граф, множество вершин которого фиксировано, а множество ребер случайно. Всякое событие строится из элементарных, как из кирпичиков, и считается произошедшим, коль скоро случайный графему как множеству — принадлежит.
Имея понятие случайного графа, можно судить о том, с какой степенью достоверности граф обладает тем или иным свойством. Например,
можно определить вероятность связности графа и т. д.)
Любая функция X, определенная на множестве графов, будет называться случайной величиной. Например, количество ребер графа — слу-
4)
Сказать, что для графа выполнено некоторое свойство, это все равно, что отнести граф к семейству графов, указанным свойством обладающих

Случайные графы
313
чайная величина. Пусть X принимает k различных значений y
1
, . . . , y Тогда математическим ожиданием величины X называется ее взвешенное среднее M X =
k
P
i=1
y i
P (X
−1
(y i
)), где X
−1
(y i
) — семейство таких графов G, для которых X(G) = y i
. Для краткости последнюю вероятность можно обозначать P (X = y i
).
1. а) Докажите линейность математического ожидания (c
1
X
1
+ . . . + c s
X
s
) = c
1
M X
1
+ . . . + c s
M X
s для любых случайных величин X
1
, . . . , X
s и констант c
1
, . . . , c s
∈ б) Докажите, что если X принимает неотрицательные целые значения, то P (X = 0) > 1 − MX.
2. Найдите MX для графов G с n вершинами и случайной величины, равной числу а) треугольников в б) циклов длины k в в) полных подграфов на k вершинах (клик) в г) различных вершинных деревьев в д) вершинных древесных компонент в е) вершин на древесных компонентах ж) вершин на циклических компонентах G.
Древесная/циклическая компонента — компонента связности графа,
являющаяся деревом/простым циклом.
Пусть f и g — некоторые функции натурального аргумента n, причем g
(n) 6= 0 для всех n. Скажем, что f = o(g) (читается «f — о малое от если f (n)
g
(n)
→ 0 при n → ∞. Например, 1 = o(
√
n) или o

1
n

3. Пусть P
a и P
b
— многочлены степеней a и b соответственно, a < Докажите, что P
a
= Полезно бывает изучать различные вероятности при n → ∞. Пусть теперь n меняется и величина p = p вероятность появления ребра случайного графа) зависит от n. (В этом есть глубокий смысл, который прояснится далее) Свойство B называется исключительно достоверным, если P (B
n
) → 1 при n → ∞, где B
n
— семейство графов сверши- нами, удовлетворяющих свойству B. Говорят даже, что в таком случае это свойство выполнено почти наверное. Докажите, что если p n
= o

1
n

, тов случайном графе почти наверное нет треугольников. Пусть k > 2 — константа. Докажите, что если p n
= o n
−
k k−1


, тов случайном графе почти наверное нет компонент связности, являющихся деревьями на k вершинах

Гл. 12. Миникурс по теории графов. Докажите, что если p n
= o

1
n

, то случайный граф почти наверное является лесом. Докажите, что если p n
= o

1
n

, то случайный граф почти наверное двудолен.
8. Определим число независимости α(G) графа G как размер максимального подмножества вершин в G, которые попарно не соединены ребрами. Пусть p n
=
1 2
. Докажите, что почти наверное) < 2 log
2
n + 10 Хроматическое число χ(G) графа G — минимальное количество цветов, в которое можно раскрасить вершины графа G правильным образом. Докажите, что если p n
=
1 2
, то хроматическое число случайного графа почти наверное больше, чем n
2 log
2
n
+ o

n log
2
n

. Более строго:
для некоторой функции f n
= o

n почти наверное выполнено свойство зависящее от n).
10. Докажите, что если p n
>
3ln n n
, то почти наверное случайный граф связен. Пусть p n
= n
−α
, где α >
5 6
. Докажите, что ∀ S ⊂ V , |S| 6
√
n : χ(G|
S
) 6 3


→ 1, при n → Здесь G|
S
— порожденный, или индуцированный, подграф графа G =
= (V , E), те. графу которого e = (x, y) ∈ F тогда и только тогда, когда x, y ∈ S и e ∈ E. Иными словами, H получается из G удалением всех вершин, не принадлежащих S, вместе со всеми выходящими из них ребрами. Граф расстояний на плоскости — граф, вершины которого являются точками плоскости и ребрами соединены пары вершин, находящиеся на расстоянии 1. Докажите, что если p n
= o

1
n

, то случайный граф почти наверное может быть реализован как граф расстояний на плоскости, а если p n
>
1000
n
, то почти наверное выполнено обратное свойство.
5)
Лес — это граф, являющийся набором несвязанных между собой деревьев

Вокруг критерия Куратовского планарности графов
315
Зачетные задачи все, кроме задач со звездочкой и еще любых двух.
Решение.
0. P (Ω) =
C
2
n
P
k=0
C
k
C
2
n p
k
(1 − p)
C
2
n
−k
= (p + (1 − p))
C
2
n
= Вокруг критерия Куратовского планарности графов
6)
А. Б. Скопенков
Формулировка критерия Куратовского планарности графов хорошо известна (все необходимые понятия и эта формулировка сформулированы далее. Однако его классическое доказательство сложно и приводится не во всех книгах по теории графов. В настоящем тексте приводится доказательство Макарычева [17] (с дальнейшими упрощениями, сделанными Заславским, Прасоловым, Телишевым и автором. По-видимому,
оно является наиболее простым (ср. [24, § 5]; Юрий Макарычев придумал свое доказательство, еще будучи школьником. Перед доказательством критерия Куратовского приводятся необходимые определения и факты теории графов, а после, — близкие результаты.
Планарные графы
Граф называется планарным, если его можно нарисовать на плоскости так, чтобы внутренности ребер (те. ребра без их концов) не пересекались и не самопересекались.
Например, любое дерево и любой граф, образованный вершинами и ребрами некоторого выпуклого многогранника, — планарные.
K
5
K
3,3
Рис. 1. Графы Куратовского
6)
Обновляемый текст см. на http://arxiv.org/abs/0802.3820. Настоящий текст является дополненной версией статьи [7]. Благодарю МН. Вялого, А. А. Заслав- ского, ДА. Пермякова, В. В. Прасолова и А. А. Телишева за полезные замечания и обсуждения, МН. Вялого и издательство МЦНМО за подготовку рисунков, атак- же Б. Мохара и СВ. Матвеева за предоставленные ссылки

Гл. 12. Миникурс по теории графов
Еще в XVIII веке Леонард Эйлер доказал, что графы и K
3,3
(см.
рис. 1) не являются планарными. Это можно доказать [5, § 1, Теорема путем небольшого перебора с использованием следующей теоремы.
(Доказательство непланарности графа K
5
, основанное на понятии коэффициента пересечения, см. в [2], [7], [5, § Теорема Жордана. Замкнутая несамопересекающаяся кривая
(т. е. цикл) делит плоскость ровно на две части. (При этом одна часть ограничена, другая неограничена, причем две точки плоскости,
не принадлежащие кривой, лежат водной части тогда и только тогда, когда их можно соединить ломаной, не пересекающей кривой.)
Обсуждение и доказательство этой теоремы см, например, в Плоским графом называется изображение графа на плоскости без самопересечений. Иногда такое изображение называют просто графом,
но это неточно, поскольку один и тот же планарный граф можно нарисовать (без самопересечений) на плоскости разными способами (см.
рис. Рис. 2. Различные вложения графа в плоскость
Из теоремы Жордана следует, что любой плоский граф разбивает плоскость наконечное число связных частей. Эти части называются гранями плоского графа.
Формула Эйлера. Для связного плоского графа с V вершинами ребрами и F гранями выполнено равенство V − E + F = Доказательство и применения этой теоремы см, например, в Грубо говоря, подграф данного графа — это его часть. Формально,
граф G называется подграфом графа H, если множество вершин графа содержится в множестве вершин графа H и каждое ребро графа является ребром графа H. При этом две вершины графа G, соединенные ребром в графе H, необязательно соединены ребром в графе Ясно, что любой подграф планарного графа планарен.
Коротко говоря, графы изоморфны, если они одинаковы (при этом их изображения на плоскости могут быть разными. Формально, графы
G
1
и без петель и кратных ребер) называются изоморфными, если существует взаимно однозначное отображение f : V
1
→ V
2
, называемое

Вокруг критерия Куратовского планарности графов
317
изоморфизмом графов, множества вершин графа на множество вершин графа G
2
, удовлетворяющее условию вершины A, B ∈ соединены ребром в томи только в том случае, если вершины f(A), f(B) ∈
∈ соединены ребром.
Рис. 3. Подразделение ребра
Операция подразделения ребра графа показана на рис. 3. Два графа называются гомеоморфными, если от одного можно перейти к другому при помощи операций подразделения ребра и обратных к ним. Или,
эквивалентно, если существует граф G, полученный из обоих данных графов операциями подразделения ребра. Ясно, что гомеоморфные графы являются или не являются планарными одновременно.
Теорема Куратовского. Граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного графу K
5
или
K
3,3
Эта теорема объявлена также замечательным советским математиком Львом Семеновичем Понтрягиным (доказательство не опубликовано, а также Фринком и Смитом. Поэтому иногда ее называют теоремой Понтрягина—Куратовского. До публикации теоремы Куратовского
Карл Менгер объявил, что граф, степень каждой вершины которого равна 3, является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного графу K
3,3
. Читатель может попытаться самостоятельно доказать этот факт (вытекающий из теоремы Куратов- ского). Кроме теоремы Куратовского существует много других критериев планарности графов [24]. Огромный интерес к поиску критерия планарности графов объясняется, в частности, наличием одной из величайших математических гипотез — гипотезы четырех красок [5, § Она утверждает, что вершины любого плоского графа можно правильно раскрасить в 4 цвета. Раскраска вершин (граней) плоского графа называется правильной, если любые две соседние вершины (грани) окрашены в разные цвета.
Простое доказательство критерия Куратовского
О необходимости в теореме Куратовского сказано выше. Приведем доказательство достаточности. Будем рассматривать графы с петлями и кратными ребрами. Предположим, напротив, что существует неплоский граф, не содержащий подграфов, гомеоморфных или K
3,3
. Сре-

Гл. 12. Миникурс по теории графов ди всех таких графов выберем граф G с минимальным числом ребер,
не содержащий изолированных вершин.
Введем операции удаления ребра, стягивания ребра и удаления вершины, показанные на рис. 4. Стягивание ребра означает удаление ребра с последующим объединением его концов в одну вершину. Удаление вершины подразумевает также удаление всех выходящих из нее ребер. Графы, получающиеся из графа G удалением ребра (xy), стягиванием ребра (xy) и удалением вершины x, будем обозначать G − рис. 4 слева, G/xy (рис. 4 в центре) ирис справа) соответ- ственно.
Лемма об удалении ребра. Для любого ребра xy графа а) из каждой вершины графа G − x − y выходит не менее двух ребер;
б) граф G − x − y не содержит графа, те. графа, гомеоморфного букве θ (графу Рис. 4. Удаление ребра G − e, стягивание ребра G/e и удаление вершины − Лемма о графах Куратовского. Для произвольного графа K следующие три условия равносильны) для любого ребра xy графа K граф K − x − y не содержит θ-графа,
изолированных вершин и висячих вершин) для любого ребра xy графа K граф K − x − y является циклом
(содержащим n > 3 вершин) граф K изоморфен или K
3,3

Вокруг критерия Куратовского планарности графов
319
Из леммы об удалении ребра вместе с импликацией 1) ⇒ 3) леммы о графах Куратовского вытекает, что граф G изоморфен или Полученное противоречие завершает доказательство.
В сформулированных леммах нетривиальна только часть б) леммы об удалении ребра, которую мы докажем в самом конце. Импликации) ⇒ 2) ⇒ 1) в лемме о графах Куратовского очевидны и не используются в доказательстве теоремы Куратовского.
Доказательство части а) леммы об удалении ребра. Изолированных вершин в графе G − x − y нет, поскольку от изолированной вершины графа G − x − y в графе G отходит не более двух ребер, что невозможно.
В графе G − x − y нет и висячих вершин. Действительно, если p висячая вершина, то она соединена и си с y, поскольку в графе G из каждой вершины выходит не менее трех ребер. Граф G − xy планарен по минимальности графа G (поскольку G не содержит ни K
5
, ни Нарисуем граф G − xy на плоскости без самопересечений и подрисуем ребро xy вдоль ребер px и py. Получим изображение графа G на плоскости без самопересечений. Противоречие.
Рис. 5. Дерево из циклов
Доказательство импликации 1) ⇒ 2) в лемме о графах Куратов- ского. Из 1) следует, что граф K − x − y представляет собой одно или несколько деревьев, вершинами которых служат циклы (рис. Поэтому в графе K − x − y существует висячий цикл, те. цикл имеющий с остальным графом только одну общую вершину v. В этом цикле K есть еще по крайней мере две вершины p и q. Так как в графе нет вершин, из которых выходит менее трех ребер, каждая из этих вершин p и q соединена либо с x, либо с y. Поэтому в объединении цикла и ребер, соединяющих вершины x, y, p, q, можно выделить θ-подграф.
Значит, по условию 1) каждое ребро графа K − x − y имеет конец на цикле C. Поскольку по условию 1) граф K − x − y не содержит висячих вершин, то он совпадает с циклом C.

Гл. 12. Миникурс по теории графов
Доказательство импликации 2) ⇒ 3) в лемме о графах Куратов- ского. При n = 3 для любых двух вершин b и c цикла K − x − y граф K − b − c является циклом, поэтому оставшаяся вершина цикла соединена (ребром) вис вершиной x, и с вершиной Поэтому K = При n > 4 возьмем любые четыре соседние вершины a, b, c, d цикла − x − y. Поскольку граф K − b − c является циклом, тов одна из вершин a и d соединена сине соединена с y), другая соединена сине соединена с x), а отличные от a, b, c, d вершины цикла K − x − которых нет при n = 4) не соединены ни с x, ни с y. При n > 5 получаем противоречие. При n = 4 получаем, что четыре вершины цикла − x − y соединены си попеременно, откуда K = K
3,3

x y
x y
x Рис. 6. Растягивание ребра в графах Куратовского
Доказательство части б) леммы об удалении ребра. Докажем сначала, что граф G/xy планарен. Утверждение граф G содержит под- граф, гомеоморфный графу H» будем сокращенно записывать в виде ⊃ H». Если G/xy ⊃ K
3,3
, то G ⊃ K
3,3
, а если G/xy ⊃ K
5
, то G ⊃
⊃ или G ⊃ рис. 6). Поэтому планарность графа G/xy следует из минимальности графа Нарисуем без самопересечений на плоскости граф G/xy (рис. 7). Покрасим в белый цвет ребра графа G/xy, выходящие из вершины Изображение графа G − x − y = G/xy − xy на плоскости получается стиранием белых ребер. Покрасим в черный цвет границу B той грани
(изображения) графа G/xy − xy, которая содержит вершину xy графа
G/xy.
Заметим, что граница грани не может содержать θ-подграфа. Это утверждение можно вывести из теоремы Жордана. Другое доказатель-

Вокруг критерия Куратовского планарности графов x Рис. 7. Изображение на плоскости графов G/xy и G
ство получается от противного если граница грани содержит под- граф, то возьмем точку внутри этой грани и соединим ее тремя ребрами стремя точками на трех дугах θ-подграфа. Получим изображение графа на плоскости без самопересечений. Противоречие.
Поэтому достаточно доказать, что в графе G/xy все ребра либо белые, либо черные. Пусть это не так. Тогда непокрашенные ребра находятся в грани графа G/xy − xy, не содержащей вершины xy. Значит граф B из черных ребер разбивает плоскость. Поэтому найдется цикл из черных ребер, относительно которого вершина xy лежит (не уменьшая общности) внутри, а некоторое еще не покрашенное ребро — вне.
Покрасим в красный цвет все ребра графа G/xy, лежащие вне цикла. Заметим, что при этом могут остаться непокрашенные ребра.
Построенная раскраска графа G/xy порождает раскраску (части)
графа G (ребро xy красится в белый цвет. Граф G − R, полученный из графа G удалением красных ребер, можно нарисовать на плоскости без самопересечений (рис. 7). Можно считать, что белые ребра лежат внутри черного цикла C. Поскольку объединение B черных ребер граница грани, то оно не содержит θ-подграфа. Значит каждая компонента связности графа B − C пересекается сне более чем по одной точке. Поэтому можно перекинуть каждую компоненту связности графа (вместе с непокрашенными ребрами) внутрь цикла C. Будем считать далее, что B − C и все непокрашенные ребра лежат внутри цикла. Нарисовав красные ребра вне C, как для вложения графа рис. 7), получим вложение графа G в плоскость. Полученное противоречие доказывает, что G − x − y есть граница грани и поэтому не содержит θ-подграфа.

Другое доказательство того, что G изоморфен или без использования импликации 2) ⇒ 3) в лемме о графах Куратовского).
Поскольку граф G не имеет вершин степени 1 или 2, то любая вершина

Гл. 12. Миникурс по теории графов цикла G − x − y соединена либо с x, либо с y. Если вершина u цикла − x − y соединена сине соединена сто соседняя с u вершина v цикла не соединена с x (поскольку в противном случае граф G − vx планарен по минимальности графа G, значит, мы можем добавить ребро к вложенному в плоскость графу G − vx и получить вложение в плоскость графа G). Поэтому либо любая вершина цикла G − x − y соединена виси с y, либо вершины цикла G − x − y, соединенные си соединенные c y, чередуются вдоль этого цикла. В первом случае = K
5
, во втором — G = Задача. Придумайте алгоритм распознавания планарности графа,
основанный на приведенном доказательстве, и оцените его сложность
7)
Запрещенные подсистемы
Если некоторая подсистема системы N нереализуема в другой системе, то и N нереализуема в M . Естественная идея — попытаться найти список запрещенных систем N
1
, . . . , N
k
, нереализуемых в M со следующим свойством.
Для того чтобы система N была реализуема в M, необходимо и достаточно, чтобы N не содержал ни одной из этих запрещенных подсистем.
Классический пример теоремы такого рода — теорема Куратовско- го. Так можно описать графы, вложимые в любую данную поверхность, а также много других классов графов или более общих объектов
(например, графы и даже пеановские континуумы, базисно вложимые в плоскость [22], [16])
8)
. Приведем формулировки некоторых результатов (доказательства оставляем читателю в качестве задач. Те фор-
7)
Для этого может пригодиться следующее изменение приведенного доказательства, не содержащее предположения о противном и поэтому не включающее работы с несуществующими объектами. Граф, полученный из графа G произвольной последовательностью операций удаления ребра или вершины или стягивания ребра,
называется минором графа G. Ясно, что минор плоского графа является плоским.
Можно доказывать теорему Куратовского в эквивалентной формулировке, полученной из следующего факта граф не содержит подграфа, гомеоморфного K
5
или
K
3,3
⇐⇒
граф не имеет минора, изоморфного K
5
или
K
3,3
Пусть G — неплоский граф,
любой минор которого плоский. Достаточно доказать, что G изоморфен или, что делается аналогично приведенным выше рассуждениям.
8)
Заметим, что список запрещенных подграфов для вложимости графа в лист
М¨
ебиуса содержит целых 103 графа [14]. Даже существование такого конечного списка для произвольной поверхности доказывается сложно [10], [20]. Список запрещенных полиэдров бесконечен для вложимости двумерных полиэдров вили мерных полиэдров в R
2n
, где n > 2 [21]. Поэтому интересны другие препятствия к вложимости. Заметим, что одно из самых полезных препятствий строится с помощью конфигурационного пространства упорядоченных пар различных точек данного пространства [6], [23].

Вокруг критерия Куратовского планарности графов
323
мулировки, в которых встречаются неизвестные читателю объекты, он может игнорировать.
Теорема Шартрана—Харари. Граф G можно нарисовать на плоскости без самопересечений так, чтобы он был границей некоторой одной грани тогда и только тогда, когда G не содержит θ-подграфа.
Назовем несамопересекающийся цикл C в связном графе G граничным, если существует изображение без самопересечений графа G на плоскости, при котором цикл C изображается границей некоторой грани. Следующий результат можно вывести из теоремы Куратовского,
ср. Рис. 8. Цикл C не может быть границей внешней грани
Относительная версия теоремы Куратовского. Цикл C является граничным тогда и только тогда, когда граф G планарен и цикл не содержится в подграфе графа G, как на рис. А вот следующий результат проще доказывать, не используя теорему Куратовского (подробнее см. [8, гл. Теорема о 8 и θ. Граф G с заданными циклами ребер, выходящих из каждой вершины, можно изобразить без самопересечений на плоскости, чтобы указанные циклы шли почасовой стрелке, тогда и только тогда, когда G не содержит восьмерки или буквы с циклами, изображенными на рис. Рис. 9. Графы с циклическими порядками, не реализуемыми на плоскости

Гл. 12. Миникурс по теории графов
Два вложения (те. изображения без самопересечений) f , g одного итого же графа в плоскость называются изотопными, если одно можно так непрерывно продеформировать в другое, чтобы в процессе деформации мы все время имели бы вложение (формальное определение см.,
например, в Теорема Маклейна—Адкиссона [19]. Два вложения связного графа в плоскость изотопны тогда и только тогда, когда их сужения на любой триод T и на любой несамопересекающийся цикл изотоп- ны (те. не таковы, как на рис. 10).
1 2
3 1
3 2
2 3
1 1
3 Рис. 10. Различные вложения окружности и триода в плоскость
Эту теорему удобно сначала доказать для деревьев, а потом свести общий случай к доказанному путем выделения максимального дерева.
Теорема Маклейна—Адкиссона справедлива также для полиэдра или даже пеановского континуума Теорема Маклейна—Адкиссона (без утверждения в скобках) справедлива для вложений в сферу, тори другие сферы с ручками (доказательство аналогично. Заметим, что любая изотопия графа на поверхности объемлема СВ. Матвеев, частное сообщение].
Теорема Баэра—Эпштейна [13]. Две замкнутые несамопе- ресекающиеся кривые на двумерном многообразии гомотопны тогда и только тогда, когда они изотопны.
Теорема Баэра—Эпштейна сводит вопрос о классификации вложений окружности в двумерное многообразие N (и, тем самым, произвольного графа в сферу с ручками и дырками) к вопросу о реализуемости элементов фундаментальной группы π
1
(N ) вложенными окружностями. Но последний вопрос очень сложен.
Задача. Граф называется (вершинно) связным, если он остается связным после удаления любой k − 1 вершины и распадается после удаления некоторых k вершин. Выведите из теоремы Маклейна—Ад- киссона следующие утверждения.
а) Любое вложение произвольного трехсвязного графа в сферу может быть получено из любого другого композицией изотопии и осевых симметрий

Вокруг критерия Куратовского планарности графов
325
б) Любое вложение двусвязного графа в сферу может быть получено из любого другого композицией изотопии и «переворачиваний блоков»
(рис. Рис. 11. Переворачивание блока
Определите операции, при помощи которых можно получить любое вложение связного (⇐⇒ связного) графа в сферу из любого другого. Сделайте тоже и для связного (⇐⇒ произвольного) графа. Таким образом получится другое описание вложений графов в плоскость с точностью до изотопии Приложение планарность полиэдров и континуумов
Полиэдр (синоним тело симплициального комплекса) — это многомерный аналог графа. Определение см, например, в [5, § 8], [4]. Уже двумерные полиэдры — интересные и сложные объекты, про которые имеется несколько знаменитых и трудных нерешенных проблем [4]. Поэтому удивительно, что имеется следующий результат.
Теорема Халина—Юнга [15], [18]. Связный полиэдр вложим в сферу тогда и только тогда, когда он не содержит графов или зонтика рис. Рис. 12. Зонтик
В этом результате интересна лишь часть тогда и лишь для двумерных полиэдров. Следующее доказательство (видимо, являющееся фольклорным) проще представленного в [15] и тем более в Набросок доказательства части тогда. Пусть связный полиэдр 6∼
= не содержит ни графов K
5
, K
3,3
, ни зонтика U
2
. Так как N не содержит зонтика, то окрестность любой точки в N является объединением дисков и отрезков, склеенных за одну точку (рис. 13 слева. Если этих дисков больше одного, то заменим эту окрестность на изображенную на рис. 13 справа

Гл. 12. Миникурс по теории графов
Рис. 13. Преобразование окрестности точки
При этом преобразовании не появится подграфов и K
3,3
. Обратное преобразование является стягиванием звезды с несколькими лучами и поэтому сохраняет планарность. Значит, достаточно доказать теорему для полученного полиэдра. Рассмотрим объединение его двумерных граней. Тогда окрестность любой точки в ¯¯
N является диском. Значит, по теореме классификации поверхностей ¯¯
N является сферой с ручками, пленками Мебиуса и дырками. Поскольку каждый из графов и вложим ив торс дыркой, ив лист Мебиуса, то есть несвязное объединение дисков с дырками. Заменим каждый из этих дисков с дырками на граф с рис. Рис. 14. Преобразование диска с дырками
Полученный граф планарен. По вложению этого графа в плоскость легко построить вложение полиэдра N в плоскость.
В терминах запрещенных подсистем можно также описать компактно бесконечные графы (те. локально связные континуумы), вло- жимые в плоскость. Континуум — компактное связное метрическое пространство. Континуумы естественно появляются при изучении динамических систем (даже гладких. Континуум называется локально связным (или континуумом Пеано), если для любой его точки x и ее окрестности U существует такая меньшая окрестность V точки x, что

Вокруг критерия Куратовского планарности графов
327
любые две точки из V соединяются некоторым путем, целиком лежащим вили, эквивалентно, если он является непрерывным образом дуги. Локально связные континуумы могут быть очень сложно устроены. Поэтому удивительно, что имеется следующий результат.
Теорема Клейтора [11], [12]. Пеановский континуум вложим в сферу тогда и только тогда, когда он не содержит континуу- мов K
5
, K
3,3
, ирис Рис. 15. Континуумы Куратовского
Построение континуумов и C
K
3,3
. Возьмем ребро ab графа и отметим на нем новую вершину a
′
. Пусть P = K
5
− (aa
′
). Пусть P
n копия графа P . Обозначим через a и a
′
n вершины графа P
n
, соответствующие и a
′
. Положим где {P
n
} — последовательность графов на плоскости со стремящимися к нулю диаметрами, сходящаяся к точке x /
∈
∞
⊔
n=1
P
n
. Точно также можно определить континуум C
K
3,3
, взяв вначале вместо Доказательство невложимости в теореме Клейтора. Докажем невложимость доказательство невложимости C
K
3,3
аналогично).
Пусть, напротив, f : C
K
5
→ R
2
— вложение. Обозначим через S :=
= P − a − окружность в P , составленную из ребер, не содержащих вершин a и a
′
. Аналогично определим S
n
⊂ Так как S
n сходится кто лежит вне f S
n для достаточно большого n.

Гл. 12. Миникурс по теории графов
Так как f I — путь между f 0 и f 1, лежащий вне f S
n
, то f 0 лежит вне f Так как S
n сходится кто лежит вне f S
n и f S
l лежит вне f S
m для достаточно больших m < l. Но тогда f a и f a
′
m лежат вне f S
m
. Это противоречит тому, что для любого вложения g : P → точки ga и лежат по разные стороны от образа Отметим, что в теореме Куратовского можно заменить плоскость на сферу S
2
. В теоремах Халина—Юнга и Клейтора можно заменить на R
2
, только добавив запрещенный подполиэдр или подконтинуум Литература Аносов Д. В. Отображения окружности, векторные поля и их применения. М МЦНМО, 2003.
[2] Болтянский В. Г, Ефремович В. А. Наглядная топология. М Наука Куратовский К. Топология. Т. 1, 2. М Мир, 1969.
[4] Матвеев СВ. Алгоритмическая топология и классификация трехмерных многообразий. М МЦНМО, 2007.
[5] Прасолов В. В. Элементы комбинаторной и дифференциальной топологии. М МЦНМО, 2004.
[6] Реповш Д, Скопенков А. Новые результаты о вложениях полиэдров и многообразий в евклидовы пространства // Успехи матем.
наук. 1999. Т. 54, № 6. С. 61–108.
[7] Скопенков А. Вокруг критерия Куратовского планарности графов Мат. просвещение. 2005. Вып. 9. С. 116 –128; 2006. Вып. С. 276–277; http://www.mccme.ru/free-books/matprosa.html.
[8] Скопенков А. Алгебраическая топология с элементарной точки зрения. М МЦНМО, в печати arxiv://math/0801.1568.
[9] Скопенков А, Телишев АИ вновь о критерии Куратовского пла- нарности графов // Матем. просвещение. 2007. Вып. 11.
[10] Archdeacon D., Huneke P. A Kuratowski theorem for non-orientable surfaces // J. Comb. Th. Ser. B. 1989. V. 46. P. 173–231.
[11] Claytor S. Topological immersions of peanian continua in a spherical surface // Ann. of Math. 1934. V. 35. P. 809–835.
[12] Claytor S. Peanian continua not embeddable in a spherical surface //
Ann. of Math. 1937. V. 38. P. 631–646.
[13] Epstein D. B. A. Curves on 2-manifolds and isotopies // Acta Math.
1966. V. 115. P. 83–107.

Вокруг критерия Куратовского планарности графов Glover H. H., Huneke J. P., Wang C. S. 103 graphs that are irreducible for the projective plane // J. Comb. Th. 1979. V. 27, № 3. P. 332–370.
[15] Halin R., Jung H. A. Charakterisierung der Komplexe der Ebene und der 2-Sph¨are // Arch. Math. 1964. V. 15. P. 466–469.
[16] Kurlin V. A. Basic embeddings into products of graphs // Topol. Appl.
2000. V. 102. P. 113–137.
[17] Makarychev Yu. A short proof of Kuratowski’s graph planarity criterion
// J. of Graph Theory. 1997. V. 25. P. 129–131.
[18] Mardeˇsi´c S., Segal J. ε-mappings and generalized manifolds //Michigan
Math. J. 1967. V. 14. P. 171–182.
[19] McLane S., Adkisson V. W. Extensions of homeomorphisms on the spheres // Michig. Lect. Topol. Ann Arbor, 1941. P. 223–230.
[20] Robertson N., Seymour P. D. Graph minors. VIII. A Kuratowski graph theorem for general surfaces // J. Comb. Theory. Series B. 1990. V. 48.
P. 255–288.
[21] Sarkaria K. S. Kuratowski complexes //Topology. 1991. V. 30. P. 67–76.
[22] Skopenkov A. Б. A description of continua basically embeddable in R
2
// Topol. Appl. 1995. V. 65. P. 29–48.
[23] Skopenkov A. Embedding and knotting of manifolds in Euclidean spaces // Surveys in Contemporary Mathematics. Ed. N. Young and
Y. Choi. London Math. Soc. Lect. Notes. 2008. V. 347. P. 248 – 342.
(arxiv:math/0604045.)
[24] Thomassen C. Kuratowski’s theorem // J. Graph. Theory. 1981. V. 5.
P. 225–242.
[25] Whitney H. Planar graphs // Fund. Math. 1933. V. 21. P. 73–84.

ГЛАВА АЛГОРИТМЫ, КОНСТРУКЦИИ,
ИНВАРИАНТЫ
Инвариант (А. В. Шаповалов
Несвобода конструкции может быть в некотором свойстве целого,
которого нету частей. При попытке построения примера это обнаруживается в том, что концы с концами не сходятся только в самый последний момент. Это явный признак, что стоит поискать инвариант, т. е.
какое-то неизменное число или свойство конструкции, полученной разрешенными действиями. Типичные инварианты четность, делимость на какое-то число, остаток по какому-то модулю, произведение или сумма всех чисел или остатков, периметр, площадь, ориентация, рациональность или иррациональность и т. п. Если разрешенные действия не меняют инвариант, то конструкцию сего значением, отличным от начального, получить невозможно. Например, нельзя доехать на поезде от Нью-Йорка до Москвы, поскольку поезда из Америки ходят только в Америку.
Вот два примера, где инвариантом служит четность. Дана пустая таблица размера (2n + 1) × (2n + 1). Двое по очереди ставят в нее фишки первый может поставить фишку в клетку (x, если в столбце с номером x ив строке с номером y до его хода поставлено в сумме четное число фишек, второй — если нечетное. В каждую клетку можно поставить не более одной фишки. Проигрывает тот, кто не может сделать ход. Докажите, что один из игроков, как бы он сам не играл,
выигрывает.
2. По кругу стоит нечетное количество целых чисел. На каждом шаге между каждой парой соседних чисел пишется их полусумма, после чего все старые числа стираются. Докажите, что если все получающиеся числа целые, то первоначальные числа равны.
В следующих двух примерах инвариант — делимость. Есть три одинаковых больших сосуда. Водном л сиропа,
в другом — N л воды, третий — пустой. Можно выливать из одного сосу

Инвариант
331
да всю жидкость в другой или в раковину. Можно выбрать два сосуда и доливать в один из них из третьего, пока уровни жидкости в выбранных сосудах не сравняются. При каких целых N можно получить 10 л разбавленного го сиропа. Есть три кучки камней впервой камень, во второй — а в третьей — 5. Разрешается объединять любые кучки в одну, атак- же разделять кучку, состоящую из четного количества камней, на две равные. Можно ли получить 105 кучек по одному камню в каждой?
А здесь инвариант — остаток. Ион используется не только для доказательства невозможности, но и для поиска оптимальной конструкции. В банке 500 долларов. Разрешаются две операции взять из банка долларов или положить в него 198 долларов. Эти операции можно проводить много раз, при этом, однако, никаких денег, кроме тех, что первоначально лежат в банке, нет. Какую максимальную сумму можно извлечь из банка и как это сделать?
В следующей задаче инвариант — ориентация, те. порядок обхода поили против часовой стрелки. На полях A, B ив левом нижнем углу шахматной доски стоят белые ладьи (см. рис. Разрешается делать ходы по обычным правилам, однако после любого хода каждая ладья должна быть под защитой какой-нибудь другой ладьи. Можно ли за несколько ходов переставить ладьи так, чтобы каждая попала на обозначенное той же буквой поле в правом верхнем углу?
И наконец, геометрические инварианты — длины и площади. Пусть F
1
, F
2
, F
3
, . . . — последовательность выпуклых четырехугольников, где при k = 1, 2, 3, . . .) получается так F
k разрезают по диагонали, одну из частей переворачивают и склеивают по линии разреза с другой частью. Какое наибольшее количество различных четырехугольников может содержать эта последовательность (Различными считаются многоугольники, которые нельзя совместить движением Гл. 13. Алгоритмы, конструкции, инварианты
Но неужели инвариант можно найти, только перебирая известные
«отмычки» из списка Конечно, нет Сравните начальную и конечную позиции, а еще лучше группу позиций, получаемую изначальной, и группу, получаемую из конечной. Посмотрите внимательнее на узкое место где возникает основная трудность. На главной диагонали квадрата 101 × 101 стоят пять ладей. Каждым ходом можно переставить одну из ладей в любом направлении по вертикали или горизонтали вплотную к ближайшей ладье или стенке квадрата (перепрыгивать через ладьи нельзя. Может ли в итоге одна ладья оказаться в центральной клетке квадрата, а остальные четыре в клетках, соседних по стороне с центральной?
И наконец, очень трудная задача. Ладья, делая ходы по вертикали или горизонтали на соседнее поле, захода обошла все поля шахматной доски и вернулась на исходное поле. Докажите, что число ходов по вертикали неравно числу ходов по горизонтали.
Зачетные задачи все, кроме любых 3 пунктов.
Решения и ответы. Посчитаем количество пар клеток, стоящих водном столбце или строке, одна из которых занята фишкой, а другая нет. Это количество перед ходом первого всегда четное, значит первый всегда может пойти. Ответ. При любом N, некратном 3 и большем 7.
5. Ответ. 498 долларов.
Указание. Определите минимальную сумму, которую можно снять за несколько операций, и повторите соответствующую группу операций много раз. Ответ. Нет.
Предположим, что это возможно. Рассмотрим центральный крест
(из центральной вертикали и горизонтали. Изначально не все 5 ладей стоят в этом кресте, а в конечном итоге там должны оказаться все ладьи. Рассмотрим момент, когда последняя (пятая) ладья впервые попала в крест. Нетрудно понять, что когда 4 ладьи стоят в центральном кресте, пятая в нем остановиться не может, противоречие. Указание. Рассмотрим граф, вершины которого — узлы шахматной доски, в которых сходятся по 4 клетки, а ребра — всевозможные стороны клеток. Пусть G — часть этого графа, расположенная внутри ломаной, по которой двигалась ладья. Постарайтесь найти ответы на

Полуинвариант
333