Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/s02/top1.ps Дата изменения: Thu Jan 23 16:43:49 2003 Дата индексирования: Sat Dec 22 11:46:23 2007 Кодировка: koi8-r Поисковые слова: спрайты

Листок 1. Планарные графы (11 февраля)
1. Используя "-ф определение непрерывности, докажите тот факт, что
композиция двух непрерывных функций непрерывна.
2. Докажите, что непрерывный образ связного топологического простран-
ства связен.
* * *
Граф G | это множество точек, называемых вершинами, причём неко-
торые пары рёбер соединены рёбрами.
Количество рёбер, выходящих из вершины графа, называют степенью
вершины. В том случае, когда из любой вершины графа можно пройти
по его рёбрам в любую другую вершину, граф называют связным. Граф
может иметь петли (рёбра, начало и конец которых совпадают) и двойные
рёбра (несовпадающие рёбра, имеющие одну и ту же пару вершин). Попарно
различные вершины v 1 , : : : , v n , соединённые рёбрами v 1 v 2 , v 2 v 3 , : : : , v n v 1 ,
называют циклом.
Граф G называют планарным, если его можно расположить на плоскости
так, чтобы его рёбра попарно не пересекались.
3. (Кусочно{линейная теорема Жордана) Пусть C | замкнутая несамо-
пересекающаяся конечнозвенная ломаная на плоскости R 2 . Докажите, что
R 2 n C состоит ровно из двух связных областей, причём границей каждой
из них служит C.
4. Пусть a; b; c; d | точки замкнутой несамопересекающейся ломаной C,
расположенные в указанном порядке. Предположим, что точки a и c со-
единены ломаной L 1 , а точки b и d соединены ломаной L 2 , причём обе эти
ломаные лежат в одной и той же из двух областей, образованных ломаной
C. Докажите, что ломаные L 1 и L 2 пересекаются в некоторой точке.
Пусть граф Kn состоит из n вершин, попарно соединённых рёбрами, а
граф K n;m состоит из n + m вершин, разбитых на два подмножества из
n вершин и из m вершин, причём рёбрами соединены все пары вершин из
разных множеств.
5. Докажите, что графы K 3;3 и K 5 непланарные.
6. Пусть G | дерево, т.е. связный граф без циклов. Докажите, что v(G) =
e(G) + 1, где v(G) | число вершин, e(G) | число рёбер графа G.
7. (Формула Эйлера) Пусть G | планарный граф, состоящий из s компо-
нент связности, среди которых нет изолированных вершин. Пусть, далее,
v | число вершин графа G, а e | число его рёбер. Тогда для любого
вложения графа G в плоскость число граней f одно и то же, а именно,
f = 1 + s v + e.
1

8. Выведите из формулы Эйлера для планарных графов формулу Эйлера,
связывающую число вершин, рёбер и граней выпуклого многогранника.
9. Докажите, что связный планарный граф (без петель и двойных рёбер)
содержит вершину, степень которой не превосходит 5.
10. Докажите, что вершины любого планарного графа (без петель и двой-
ных рёбер) можно раскрасить в пять цветов так, что любые две вершины,
соединённые ребром, будут разного цвета.
11. а) Пусть G | планарный граф без изолированных вершин, v i | число
его вершин, из которых выходит i рёбер, f j | число граней, ограниченных
j рёбрами (с учетом их кратностей). Докажите, что тогда P
i (4 i)v i +
P
j (4 j)f j = 4(1 + s) > 8, где s | число компонент связности графа G.
б) Докажите, что если все грани 4-угольные, то 3v 1 + 2v 2 + v 3 > 8.
в) Докажите, что если любая грань ограничена циклом, содержащим не
менее n рёбер, то e 6 n(v 2)
n 2
.
12. Воспользовавшись задачей 11 в), получите ещё одно доказательство
непланарности графов K 5
и K 3;3
.
13. а) Пусть G | планарный граф, все грани которого содержат чётное
число рёбер. Докажите, что вершины этого графа можно раскрасить в два
цвета.
б) Пусть | гладкая замкнутая кривая, все самопересечения которой
трансверсальны. Докажите, что разбивает плоскость на области, которые
можно раскрасить в два цвета так, что области, граничащие по некоторой
дуге, будут разного цвета.
2