Банк задач по математике

Задача 2.4.1

(1)(2)(3)

Дан плоский граф с треугольными гранями, имеющий более трёх вершин. Удалили вершину вместе с выходящими из нее рёбрами.

?

(1)

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

(2)

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

(3)

Пусть в полученном графе степень каждой вершины не менее 3. Верно ли, что любую вершину нового графа можно удалить и получить граф, все грани которого будут ограничены несамопересекающимися циклами?

Примечание.

?

Плоским графом называется изображение графа на плоскости, для которого любые два ребра пересекаются только по их общим вершинам (в частности, если таких вершин нет, то не пересекаются). Плоский граф делит плоскость на части, называемые гранями графа; одна из таких частей является «бесконечной».

Задача 2.4.2

(1)(2)

?

(1)

Формула Эйлера. Для любого связного плоского графа с $f$ гранями имеет место равенство $n - e + f = 2$ .

(Доказательство см., например, в [Р]. Далее этим результатом можно пользоваться без доказательства. Эта формула часто записывается в виде $V - E + F = 2$ .)

(2)

Найдите аналог формулы Эйлера для плоского графа с $k$ компонентами связности.

Задача 2.4.3

?

(1)

Ни один из графов $K_{5}$ и $K_{3,3}$ невозможно без самопересечений нарисовать на плоскости.

Рис. 5. Непланарные графы

(2)

На плоскости отмечено $n$ точек. Разрешается соединять некоторые две из них ломаной, не проходящей через другие точки. Два игрока по очереди соединяют ломаной какие-то две ещё не соединённые точки. При этом требуется, чтобы эти ломаные не самопересекались и не пересекались нигде, кроме отмеченных точек. Проигрывает тот, кто не может сделать ход. Для каких $n$ при правильной игре выигрывает тот, кто ходит первым?

(3)

Перечислите все связные плоские графы (с точностью до изоморфизма), у которых степени всех вершин равны и «степени» всех граней равны (т.е. граница каждой грани состоит из одного и того же числа рёбер).

Замечание. Если пункты (1), (2) или (3) не получаются, решайте следующие пункты. Определение изоморфизма см. в п. 2.3.

(4)

Выпуклых правильных многогранников (все грани — правильные многоугольники с одинаковым числом сторон, степени всех вершин равны) ровно 5 (с точностью до изоморфизма их графов). Конструкцию соответствующих многогранников нужно привести, она не предполагается известной.

(5)

Для любого плоского связного графа без петель и кратных рёбер, имеющего более двух вершин, $2e \geq 3f$ и $e \leq 3n - 6$ .

(6)

В любом плоском графе есть вершина степени не более 5.

(7)

Если каждая вершина плоского связного графа имеет степень $d$ , а граница каждой грани состоит из ровно $k \geq 3$ рёбер, то

\frac{1}{d} + \frac{1}{k} = \frac{1}{2} + \frac{1}{e}.

Задача 2.4.4

(1)(2)(3)

Картой на плоскости называется разбиение плоскости на конечное число многоугольников (возможно, «бесконечных»). Раскраска карты называется правильной, если разные многоугольники, имеющие общий граничный отрезок, имеют разные цвета. Докажите, что любую карту можно правильно раскрасить в

?

(1)

6 цветов;

(2)

5 цветов;

(3)

Примечание.

?

Замечание. Используя конструкцию двойственного графа, можно доказать, что правильная раскрашиваемость любой карты на плоскости в $d$ цветов равносильна правильной раскрашиваемости любого плоского графа в $d$ цветов (п. 3.1).

Задача 2.4.5

(1)(2)

Придумайте алгоритм

?

(1)

распознавания планарности графа (здесь можно использовать без доказательства теорему Куратовского);

(2)

рисования без самопересечений заведомо планарного графа на плоскости.

Найдите асимптотику сложности вашего алгоритма в зависимости от числа $n$ рёбер графа, т.е. асимптотику максимума по графам с $n$ рёбрами от числа шагов в алгоритме, применённом к данному графу. См. «определение» нахождения асимптотики в п. 6.1.

Теорема Хопкрофта — Тарджана. Существует линейный по количеству рёбер алгоритм распознавания планарности графа.

Примечание.

?

Операция подразделения ребра графа: ребро $(A,B)$ удаляется, вместо него добавляется новая вершина $D$ и два новых ребра $(A,D)$ и $(D,B)$ .

Два графа называются гомеоморфными, если от одного можно перейти к другому при помощи операций подразделения ребра и обратных к ним; или, эквивалентно, если существует граф, полученный из каждого из данных графов операциями подразделения ребра.

Ясно, что гомеоморфные графы являются или не являются планарными одновременно.

Теорема Куратовского. Граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного графу $K_{5}$ или $K_{3,3}$ . (Доказательство этой теоремы см., например, в [S5].)

Задача 2.4.6

(1)(2)

?

(1)

Теорема Фари. Плоский граф можно нарисовать без самопересечений на плоскости так, что все рёбра будут отрезками.

(2)

Дан невыпуклый многоугольник с непрозрачными сторонами. Назовем вершину $A$ видимой из точки $X$ , если внутренность отрезка $AX$ не пересекается с границей многоугольника. Назовем ядром многоугольника множество его внутренних точек, из которых видны все вершины многоугольника. Докажите, что если точку из ядра соединить отрезками с произвольно выбранными несколькими (не менее чем с двумя, и не обязательно со всеми) вершинами исходного многоугольника, то многоугольник разобьется на многоугольники с непустыми ядрами.

Задача 2.4.7

Нарисуйте без самопересечений на торе граф

?

(1)

$K_{5}$ ;

(2)

$K_{3,3}$ ;

(3)

$K_{6}$ ;

(4)

$K_{3,4}$ ;

(5)

$K_{7}$ ;

(6)

$K_{4,4}$ .

Примечание.

?

Тор и лента Мёбиуса предполагаются прозрачными, т.е. точка (или подмножество), «лежащая на одной стороне поверхности», «лежит и на другой стороне». Это аналогично тому, что при изучении геометрии мы говорим, например, о треугольнике на плоскости, а не о треугольнике на верхней (или нижней) стороне плоскости.

Задача 2.4.8

(1)(2)(3)(4)

Нарисуйте без самопересечений на ленте Мёбиуса граф

?

(1)

$K_{5}$ ;

(2)

$K_{3,3}$ ;

(3)

$K_{6}$ ;

(4)

$K_{3,4}$ .

Задача 2.4.9

(1)(2)(3)

Картой на торе называется разбиение тора на конечное число (криволинейных и изогнутых) многоугольников. Раскраска карты на торе называется правильной, если разные многоугольники, имеющие общую граничную кривую, имеют разные цвета. Любую ли карту на торе можно правильно раскрасить

?

(1)

в 5 цветов;

(2)

в 6 цветов;

(3)

в 7 цветов?

Подробнее см. [S1, 2].

Примечание.

?

Замечание. Любой связный граф с $g$ рёбрами можно так нарисовать «на сфере с $g$ ручками» (т.е. внутри правильного $2g$ -угольника, диаметрально противоположные стороны которого «склеены»), что некоторые рёбра являются отрезками, а остальные рёбра являются объединениями двух непересекающихся отрезков, у каждого из которых один конец — вершина графа, а другой конец лежит на стороне $2g$ -угольника.

Плоские графы