«С. В. Мациевский ВЫСШАЯ МАТЕМАТИКА ДЛЯ ГУМАНИТАРИЕВ Учебное пособие Издательство Российского государственного университета им. И. Канта 2010 УДК 51(075) ББК 22.11я73 М 367 Рецензенты: доцент кафедры высшей математики ...»

2.3. Какое из следующих правил позволяет заменить связку «и»?

3) (x) (¬(¬x)).

5) (x), (x y) (y).

2.4. Какое из следующих правил используется при доказательстве от противного?

3) (x) (¬(¬x)).

5) (x), (x y) (y).

2.5. Какое из следующих правил является законом двойного отрицания?

3) (x) (¬(¬x)).

5) (x), (x y) (y).

§ 8. Логический резолютивный вывод Пусть n — номер варианта от 1 до 16.

Выполните упражнение с номером Вашего варианта с помощью резолютивного вывода. Все упражнения Льюиса Кэрролла. Образцы доказательства приведены в разделе 2.

(При подготовке текстов этих задач автору пришлось исправлять многочисленные ошибки, содержащиеся в русском издании.) 1. Малые дети неразумны. Тот, кто может укрощать крокодилов, заслуживает уважения. Неразумные люди не заслуживают уважения. Верно ли, что малые дети не могут укрощать крокодилов?

2. Мои кастрюли — единственные из принадлежащих мне вещей, которые сделаны из олова. Все ваши подарки чрезвычайно полезны. Ни от одной из моих кастрюль нет никакой пользы. Верно ли, что ваши подарки сделаны не из олова?

3. Ни одна из молодых картофелин не была поджарена. Все картофелины на этой тарелке съедобны. Ни одна не жареная картофелина не съедобна.

Верно ли, что все картофелины на этом блюде старые?

4. Ни одна утка не танцует вальс. Ни один офицер не откажется протанцевать вальс. У меня нет другой птицы, кроме уток. Верно ли, что среди моей домашней птицы нет офицеров?

5. Всякий, кто находится в здравом уме, может заниматься логикой. Ни один лунатик не может быть присяжным заседателем. Ни один из ваших сыновей не может заниматься логикой. Верно ли, что ни один из ваших сыновей не годится в присяжные заседатели?

6. В этой коробке нет моих карандашей. Ни один из моих леденцов — не сигара. Вся моя собственность, не находящаяся в этой коробке, состоит из сигар. Верно ли, что ни один из моих карандашей не леденец?

7. Ни одного опытного человека нельзя считать некомпетентным. Дженкинс всегда допускает грубые ошибки в работе. Ни один компетентный человек не допустит грубых ошибок в работе. Верно ли, что Дженкинс неопытен?

8. Ни один терьер не блуждает среди знаков Зодиака. То, что не блуждает среди знаков Зодиака, не может быть кометой. Только у терьера хвост колечком. Верно ли, что ни у одной кометы нет хвоста колечком?

9. Никто не станет выписывать газету «Таймс», если он не получил хорошего образования. Ни один дикобраз не умеет читать. Те, кто не умеют читать, не получили хорошего образования. Верно ли, что ни один дикобраз не выписывает газету «Таймс»?

10. Все пудинги вкусны. Приготовленное блюдо — пудинг. Ни одно вкусное блюдо не полезно. Верно ли, что приготовленное блюдо не полезно?

11. Когда мой садовник рассуждает на военные темы, его стоит послушать.

Никто не может помнить битву при Ватерлоо, если он не очень стар. Того, кто не помнит битвы при Ватерлоо, не стоит слушать, когда он рассуждает на военные темы. Верно ли, что мой садовник очень стар?

12. Все колибри имеют яркое оперение. Ни одна крупная птица не питается нектаром. Птицы, которые не питаются нектаром, имеют неяркое оперение. Верно ли, что все колибри очень малы?

13. Все утки в этой деревне, имеющие метку «Б», принадлежат миссис Бонди. Утки в этой деревне не носят кружевных воротничков, если не имеют метки «Б». У миссис Бонди в этой деревне нет серых уток. Верно ли, что ни одна серая утка в этой деревне не носит кружевных воротничков?

14. Вся старая посуда на этой полке имеет трещины. Ни один горшок на этой полке не новый. Все, что стоит на этой полке и имеет трещины, не пригодно для хранения воды. Верно ли, что ни один горшок на этой полке не пригоден для хранения воды?

15. Все незрелые фрукты неполезны. Все эти яблоки полезны. Ни один фрукт, выросший в тени, не зрелый. Верно ли, что эти яблоки выросли на солнце?

16. Щенок, не желающий лежать спокойно, всегда будет вам благодарен, если предложите ему скакалку. Хромой щенок не скажет вам спасибо, если вы предложите ему скакалку. Никто, кроме хромых щенят, не станет ткать. Верно ли, что щенки, которые не могут лежать спокойно, не станут ткать?

Для чего, в самом деле, полюса, параллели, Теория графов и топология 132 Глава 3. Теория графов и топология § 9. Теория графов Болтянский В. Г., Савин А. П. Беседы о математике. Книга 1. Дискретные объекты.— М.: ФИМА, МЦНМО, 2002.

Романовский И. В. Дискретный анализ.— СПб.: Невский Диалект; БХВПетербург, 2003.

Харари Ф. Теория графов. М.: Едиториал УРСС, 2003.

Акимов О. Е. Дискретная математика: логика, группы, графы.— М.: Лаборатория Базовых Знаний, 2003.

Гарднер М. От мозаик Пенроуза к надежным шифрам / Пер. с англ.— М.:

Мир, 1993.

Граф, вершина, ребро, изоморфизм графов, порядок графа, степень вершины, (p, q)-граф, инвариант графа, четная и нечетная вершины, связность графа, компонента связности, маршрут, замкнутый и открытый маршруты, цепь, цикл, дерево, задача о кёнигсбергских мостах, абстрагирование, мультиграф, эйлеров граф.

§ 9. Теория графов 1°. Определение графа. Изоморфизм графов Граф определить очень просто.

Граф — это точки, некоторые пары из которых соединены одной линией.

Графы рисуют на плоскости.

Примеры.

Некоторые графы изображены на рисунке 1.

Рис. 1. Примеры изоморфных графов: все графы изоморфны друг другу Точки и линии, из которых состоит граф, носят специальные названия.

Вершина, ребро.

Точки, из которых состоит граф, называются вершинами графа, а линии — ребрами графа.

В теории графов не различают одинаковых, то есть изоморфных, графов. В каком бы виде ни рисовали граф на плоскости, это будет один и тот же граф.

Изоморфизм графов.

Два графа изоморфны, если их можно наложить друг на друга до полного совпадения вершин и ребер. При этом, конечно, можно и нужно передвигать их вершины и растягивать и сжимать их ребра.

Все четыре графа на рисунке 1 изоморфные друг другу!

Действительно, изображение графа 1б получается из изображения 1а поворотом на 90°, изображение 1в — из изображения 1б изгибанием вправо вертикального ребра, изображение 1г — из 1б поднятием нижней вершины вверх до центра треугольника (или из 1в сдвигом влево правой вершины и выпрямлением обратно в вертикаль изогнутого ребра).

Разумеется, у всех графов на рисунке 1 по 4 вершины, а из каждой вершины выходит по 3 ребра.

Порядок графа, степень вершины.

Порядок графа — это количество его вершин, а степень вершины — это количество ребер, выходящих (или входящих) из нее.

Итак, на рисунке 1 изображен граф порядка 4, все вершины которого имеют степень 3.

(p, q)-граф.

Граф, имеющий p вершин и q ребер, называется (p, q)-графом.

Чем могут отличаться разные, неизоморфные графы одного порядка? Естественно, количеством ребер. Нарисуем все графы низших порядков.

1. Очевидно, что существует только один граф порядка 1: это точка (рис. 2).

У графа порядка 1 количество ребер равно 0, сумма степеней вершин равна 0, количество вершин четной степени равно 1, а нечетной степени — 0.

2. Графов порядка 2 уже больше: их два (рис. 3). Первый граф порядка 2 не имеет ни одного ребра, второй — имеет единственное ребро. Таким образом, изображения графов порядка 2 можно упорядочить по количеству ребер (рис. 3).

Рис. 3. Два графа порядка 2: (2, 0)-граф (слева) и (2, 1)-граф (справа) У первого графа порядка 2 (рис. 3 слева) количество ребер равно 0, сумма степеней вершин равна 0, количество вершин четной степени равно 2, а нечетной степени — 0.

У второго графа порядка 2 (рис. 3 справа) количество ребер равно 1, сумма степеней вершин равна 2, количество вершин четной степени равно 0, а нечетной степени — 2.

3. Если графы одного порядка различаются только по количеству ребер, то графов порядка 3 должно быть четыре. Так оно и есть, и снова графы порядка 3 легко упорядочить по количеству ребер (рис. 4).

Рис. 4. Все четыре графа порядка 3: слева направо: (3, 0)-, (3, 1)-, (3, 2)- и (3, 3)-графы У первого графа порядка 3 количество ребер равно 0, сумма степеней вершин равна 0, количество вершин четной степени равно 3, а нечетной степени — 0.

Второй граф порядка 3 имеет 1 ребро, сумму степеней вершин 2, а также вершину четной степени и 2 — нечетной.

Третий граф имеет 2 ребра, сумму степеней вершин 4, а также 1 вершину четной степени и 2 — нечетной.

Наконец, у четвертого 3 ребра, сумма степеней вершин 6, 3 вершины четной степени и 0 — нечетной.

§ 9. Теория графов Составим таблицу 5 из полученных нами данных о всех графах первых трех порядков.

Инвариант графа.

Инвариант графа — это число, связанное с графом и одинаковое для всех изоморфных графов Ясно, что порядок графа, количество его ребер, количество его вершин четной степени и количество его вершин нечетной степени не меняются, как бы граф ни нарисовали на плоскости. Поэтому эти числа являются инвариантами любого графа.

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

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

Теорема 6. Сумма степеней вершин графа.

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

Доказательство. Каждое ребро графа соединяет две вершины и поэтому считается в сумме степеней вершин два раза.

Четная и нечетная вершины.

Назовем четной вершиной вершину графа, имеющую четную степень, а нечетной вершиной — вершину графа, имеющую нечетную степень.

Рассмотрим таблицу 5 и изучим количество нечетных вершин, то есть количество вершин нечетной степени.

Теорема 7. Количество нечетных вершин.

Количество нечетных вершин графа четно.

Доказательство*. Сумма степеней вершин графа разбивается на две части:

на сумму степеней четных вершин и на сумму степеней нечетных вершин.

Вся сумма четна по теореме 6. Сумма степеней четных вершин тоже четна как сумма четных чисел. Следовательно, должна быть четна и вторая сумма:

сумма степеней нечетных вершин,— как разность четных чисел.

Чтобы последняя сумма нечетных чисел была четна, необходимо, чтобы количество нечетных чисел было четно, то есть количество нечетных вершин всегда четно.

Теорема 8. Теорема Рамсея.

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

Доказательство*. Построим модель задачи в виде графа, шесть вершин которого соответствуют шести людям. Тогда требуется доказать, что в любом графе порядка 6 найдутся либо три вершины, попарно соединенные ребрами, либо три вершины, попарно не соединенные ребрами.

Возьмем любую вершину X. Она либо соединена не менее чем с тремя вершинами из пяти других вершин, либо не соединена не менее чем с тремя вершинами из пяти других вершин. Не умаляя общности предположим для простоты, что выбранная вершина соединена по крайней мере с тремя вершинами A, B и C (см. рис. 9) (если не соединена с тремя вершинами, то доказательство то же самое, только надо слово «соединены» заменять на «не соединены» и наоборот,— это и означают слова «не умаляя общности»).

На рисунке 9 показано, как выбранная вершина X соединена с тремя вершинами A, B и C. Пунктиром соединены пары вершин, про которые неизвестно, соединены ли они ребром.

X B X B X B

Возможны два случая.

1. Какая-нибудь пара из трех вершин A, B и C соединена ребром. Не умаляя общности, пусть это вершины A и B (см. рис. 9 в центре). Тогда имеем три вершины X, A и B, попарно соединенные ребрами.

2. Никакие две вершины из A, B и C не соединены ребром (см. рис. 9 справа). Тогда получаем три вершины A, B и C, попарно не соединенные ребрами.

§ 9. Теория графов На графах просто ввести универсальное понятие связности.

Связность графа.

Граф связен, если с любой его вершины на любую другую можно перейти по ребрам.

Примеры.

Посмотрим, какие из семи графов порядка 1—3 связны, а какие нет.

Очевидно, что (1, 0)-граф порядка 1 связен (см. рис. 2).

(2, 0)-граф несвязен, а (2, 1)-граф связен (см. рис. 3).

(3, 0)- и (3, 1)-графы несвязны, а (3, 2)- и (3, 3)-графы связны (см. рис. 4).

Компонента связности.

Любой граф состоит из связных подграфов, или компонент связности.

Ясно, что связный граф имеет одну компоненту связности.

Примеры.

Несвязный (2, 0)-граф имеет две компоненты связности — два графа порядка 1 (см. рис. 3).

Несвязный (3, 0)-граф имеет три компоненты связности — три графа порядка 1 (см. рис. 4).

Несвязный (3, 1)-граф имеет две компоненты связности — один графа порядка 1 и один граф порядка 2(см. рис. 4).

Уточним понятие связности.

Маршрут.

Маршрут на графе — цепочка ребер, соединяющая две вершины так, что окончание предыдущего ребра совпадает с началом следующего.

Нарисуем какой-нибудь граф и обозначим буквами его вершины (рис. 10). Тогда маршруты просто обозначать метками вершин.

Некоторые маршруты, которыми можно соедиРис. 10. Граф с поме- нить вершины A и B:

A—B, A—C—B, A—D—B, A—D—C—B, A—C—D—B.

Некоторые маршруты, которыми можно вернуться в вершину A:

A—B—A, A—B—C—A, A—C—B—A, A—B—C—D—A, A—B—D—C—A.

Теперь можно дать более правильное определение связного графа.

Связность графа.

Граф связен, если любые две его вершины можно соединить маршрутом.

Рассмотрим различные виды маршрутов.

Замкнутый и открытый маршруты.

Маршрут замкнут, если его начальная вершина совпадает с коечной, и открыт в противном случае.

Примеры.

Маршруты на графе на рисунке 10, которые приведены как примеры соединения вершины A с самой собой, замкнуты:

A—B—A, A—B—C—A, A—C—B—A, A—B—C—D—A, A—B—D—C—A.

Маршруты на графе на рисунке 10, которые приведены как примеры соединения вершин A и B, открыты:

A—B, A—C—B, A—D—B, A—D—C—B, A—C—D—B.

Маршрут может проходить по разным ребрам, а может по одинаковым.

Для замкнутого маршрута все равно, где его начальная вершина, а где — конечная.

Цепь, цикл.

Маршрут называется цепью, если все его ребра различны.

Если в замкнутой цепи все вершины различны, то это цикл.

Примеры.

В предыдущем примере все маршруты — цепи, кроме маршрута A—B—A.

В предыдущем примере из девяти цепей четыре являются циклами:

A—B—C—A, A—C—B—A, A—B—C—D—A, A—B—D—C—A.

На рисунке 10 можно насчитать семь различных циклов. Насчитайте.

Приведем понятие, которое часто встречается в разных разделах математики и информатики.

Дерево.

Дерево — это связный граф без циклов.

Очевидна следующая теорема.

Теорема 11. Количество ребер дерева.

Дерево порядка n имеет n 1 ребро.

Перечислим все деревья порядков 1—5 (рис. 12):

§ 9. Теория графов Впервые решение задачи о кёнигсбергских мостах опубликовал великий математик Леонард Эйлер в Санкт-Петербурге в 1736 году. Приведем перевод начала этой статьи. Кстати, Эйлер никогда не был в Кёнигсберге.

1. В дополнение к той части геометрии, которая имеет дело с количествами и которая всегда возбуждала особый интерес, существует другая — фактически все еще неизвестная — часть, которую впервые упомянул ЛЕЙБНИЦ и которую он назвал геометрией положения. Эта часть геометрии занимается именно тем, что может быть определено только положением, а также исследованием свойств положения; в этом смысле она не будет касаться ни количеств, ни их вычисления. Однако виды задач, относящихся к этой геометрии положения, и методы, используемые для их решения, были недостаточно точно определены. Из-за этого в последнее время, когда возникала задача, которая казалась в основе своей геометрической, но по своей природе не требовала определения количеств и не допускала решения с помощью вычисления количеств, я был убежден, что она принадлежит геометрии положения главным образом из-за того, что только положение можно было использовать для ее решения, в то время как вычисления были совсем бесполезны. Поэтому я решил объяснить здесь метод, который разработал для решения задач подобного вида, как пример геометрии положения.

2. Эта задача, как мне сказали, довольно хорошо известна и связана вот с чем.

В городе Кёнигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке (фиг. 1). Рукава этой реки пересекают семь мостов a, b, c, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причем ровно по одному разу.

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

3. Конечно, можно решить кёнигсбергскую задачу о семи мостах, составив полный список всех маршрутов, какие только можно себе представить, и тогда станет ясно, годится ли некоторый маршрут или подходящего маршрута нет. Однако из-за большого числа комбинаций этот способ решения задачи представляется слишком трудным и громоздким. Кроме того, его нельзя было бы применить к другим задачам со значительно большим числом мостов. И даже если при таком способе решения работу можно было бы довести до конца, возникли бы многие не относящиеся к делу обстоятельства; здесь, без сомнения, лежит основная причина трудностей. Поэтому, отказавшись от этого метода, я стал искать другой, который позволил бы только решить, возможен ли маршрут, который удовлетворяет нашим требованиям; я подозревал, что такой метод был бы значительно проще.

Для любознательных приведем также начало этой статьи Эйлера на том языке, на котором она была опубликована — на латинском.

1. Praeter illam geometriae partem, quae circa quantitates versatur et omni tempore summo studio est exculta, alterius partis etiamnum admodum ignotae primus mentionem fecit LEIBNITZIUS, quam Geometriam situs vocavit.

2°. Определение задачи о кёнигсбергских мостах Рассмотрим задачу, с которой начиналась теория графов.

Задача о кёнигсбергских мостах.

Задача о кёнигсбергских мостах — задача о прохождении по одному разу по мостам города Кёнигсберга XVIII века.

На гравюре на рисунке 13 показан город Кёнигсберг в 1736 году.

Рис. 13. Город Кёнигсберг в 1736 г. и схема его частей и мостов Так и будем понимать эту задачу в дальнейшем.

Однако за границей задача о кёнигсбергских мостах — это родовое имя целого класса задач.

Задача о кёнигсбергских мостах.

На Западе задача о кёнигсбергских мостах — любая задача о прохождении по одному разу по мостам любой конфигурации, или об обводе рисунка, не отрывая карандаша от бумаги и не проводя одной линии дважды, или об обходе по одному разу ребер любого связного графа.

§ 9. Теория графов Абстрагирование.

Смоделируем русскую задачу о кёнигсбергских мостах с помощью графа.

Мосты ведут в четыре разных части города, разделенных рекой Преголя, которые абстрагируем вершинами. Получаем четыре вершины, как показано на рисунке 14 слева.

Абстрагируя мосты ребрами, окончательно получаем граф задачи о кёнигсбергских мостах, изображенный на рисунке 14 справа. Но получился не совсем граф: некоторые вершины соединены более чем одним ребром.

Теперь наша задача о кёнигсбергских мостах формулируется так.

Задача о кёнигсбергских мостах.

Можно ли обойти граф задачи о кёнигсбергских мостах, пройдя по его ребрам по одному разу?

Граф, у которого две вершины могут соединять несколько ребер, носит специальное название.

Мультиграф.

Мультиграф — это граф, у которого вершины могут соединяться более чем одним ребром.

В дальнейшем мультиграф будем для краткости называть просто графом.

Тем более что развиваемая теория верна и для мультиграфов, и для обычных графов как их частного случая.

Теорема 15. Теорема Эйлера.

Связный граф можно обойти по одному разу по ребрам тогда и только тогда, когда он имеет либо две нечетные вершины, либо ни одной.

При двух нечетных вершинах эти вершины — конечные вершины маршрута обхода. Когда нет нечетных вершин, то граф можно обойти, начиная с любой вершины, на той же вершине маршрут и закончится.

Доказательство. Докажем только необходимость.

Пусть граф уже обойден по какому-то маршруту. Докажем, что тогда он либо имеет две нечетные вершины, либо не имеет ни одной.

Маршрут, которым обойден граф, имеет конечные вершины и не конечные, промежуточные.

Рассмотрим степени промежуточных вершин. В каждую из них наш маршрут входит и сразу выходит, поэтому промежуточные вершины — четные.

Итак, только конечные вершины могут быть нечетными, то есть количество нечетных вершин не более двух. Следовательно, по теореме 7, всего нечетных вершин либо две, либо ни одной.

Посмотрим на граф кёнигсбергских мостов на рисунке 14. Он имеет четыре нечетные вершины, поэтому его обойти нельзя.

Но построены еще 3 моста. На рисунке 16 слева показана спутниковая съемка современного Калининграда, которую можно найти на Рис. 16. Спутниковая съемка мостов города Калининграда в 2009 году (слева) и схема центра города Калининграда в 2009 году (справа) Следующий вид графов назвали в честь Эйлера.

Эйлеров граф.

Связный граф эйлеров, если все его вершины четные.

Нарисуем все эйлеровы графы порядков 1—4.

§ 9. Теория графов 1.1. Сколько вершин у всех представленных графов?

1.2. Сколько ребер у всех представленных графов?

1.3. Какой по порядку граф не имеет изоморфного графа среди представленных графов?

1.4. Сколько компонент имеет несвязный граф, представленный на рисунке?

1.5. Какая минимальная степень вершины у несвязного графа, представленного на рисунке?

2.1. Сколько ребер имеют деревья порядка 4?

1) 0.

2) 1.

3) 2.

4) 3.

5) 4.

2.2. Сколько всего деревьев порядка 3?

1) 0.

2) 1.

3) 2.

4) 3.

5) 4.

2.3. Сколько циклов может иметь дерево?

1) 0.

2) 1.

3) 2.

4) 3.

5) 4.

2.4. Сколько всего деревьев порядка 4?

1) 0.

2) 1.

3) 2.

4) 3.

5) 4.

2.5. Сколько ребер имеют деревья порядка 5?

1) 0.

2) 1.

3) 2.

4) 3.

5) 4.

§ 9. Теория графов 3.1. Можно ли обойти мосты центра Кёнигсберга 1736 г., а если можно, то как (см. рис. справа)?

1) Нельзя обойти.

2) Можно обойти, начиная только из одного места.

3) Можно обойти, начиная только из двух мест.

4) Можно обойти, начиная только из трех мест.

5) Можно обойти, начиная из всех четырех мест.

3.2. Можно ли обойти мосты центра Кёнигсберга 1910 г., а если можно, то как (см. рис. справа)?

1) Нельзя обойти.

2) Можно обойти, начиная только из одного места.

3) Можно обойти, начиная только из двух мест.

4) Можно обойти, начиная только из трех мест.

5) Можно обойти, начиная из всех четырех мест.

3.3. Можно ли обойти мосты центра послевоенного Кёнигсберга, а если можно, то как (см. рис. справа)?

1) Нельзя обойти.

2) Можно обойти, начиная только из одного места.

3) Можно обойти, начиная только из двух мест.

4) Можно обойти, начиная только из трех мест.

5) Можно обойти, начиная из всех четырех мест.

3.4. Можно ли обойти мосты центра Кёнигсберга начала XXI века, а если можно, то как (см. рис. справа)?

1) Нельзя обойти.

2) Можно обойти, начиная только из одного места.

3) Можно обойти, начиная только из двух мест.

4) Можно обойти, начиная только из трех мест.

5) Можно обойти, начиная из всех четырех мест.

3.5. Можно ли обойти мосты центра Кёнигсберга недалекого будущего, а если можно, то как (см. рис. справа)?

1) Нельзя обойти.

2) Можно обойти, начиная только из одного места.

3) Можно обойти, начиная только из двух мест.

4) Можно обойти, начиная только из трех мест.

5) Можно обойти, начиная из всех четырех мест.

Пусть n — номер варианта от 1 до 16. Выполните упражнение с номером Вашего варианта.

1. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите количество ребер.

2. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите сумму степеней вершин.

3. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите количества и метки четных вершин.

4. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите количества и метки нечетных вершин.

5. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите количество компонент связности.

6. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Для каждого графа выпишите все его различные циклы, если они есть.

7. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Определяются ли полностью графы порядка 4 количеством ребер и почему?

8. Нарисуйте все одиннадцать графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Определяются ли полностью графы порядка 4 количеством ребер и связностью и почему?

9. Выпишите все тринадцать цепей, соединяющих в графе на рисунке вершины A и B.

10. Нарисуйте все шесть деревьев порядка 6.

11. Нарисуйте все четыре эйлерова графа порядка 5.

12. Можно ли обойти по одному разу мосты современного г. Калининграда? Если можно, нарисуйте один из обходов.

13. Исключите из обхода один из мостов старого Кёнигсберга так, чтобы по оставшимся шести можно было пройти по одному разу. Сделайте это всеми возможными семью способами.

14. Нарисуйте все шесть связных графов порядка 4 с метками вершин, упорядочив их по количеству ребер. Можно ли обойти по одному разу их ребра? Если можно, нарисуйте по одному из обходов.

15. Нарисуйте все шесть деревьев порядка 6 с метками вершин. Можно ли обойти по одному разу их ребра? Если можно, нарисуйте по одному из обходов.

16. Нарисуйте все четыре эйлерова графа порядка 5 с метками вершин.

Можно ли обойти по одному разу их ребра? Если можно, нарисуйте по одному из обходов.

§ 10. Планарные, раскрашенные и ориентированные графы 2°. Двудольный граф. Теорема Понтрягина — Куратовского................

1°. Определение орграфа. Изоморфизм орграфов.........................

Болтянский В. Г., Савин А. П. Беседы о математике. Книга 1. Дискретные объекты.— М.: ФИМА, МЦНМО, 2002.

Романовский И. В. Дискретный анализ.— СПб.: Невский Диалект; БХВПетербург, 2003.

Харари Ф. Теория графов. М.: Едиториал УРСС, 2003.

Акимов О. Е. Дискретная математика: логика, группы, графы.— М.: Лаборатория Базовых Знаний, 2003.

Гарднер М. Математические головоломки и развлечения: 2-е изд., испр. и дополн. / Пер. с англ.— М.: Мир, 1999.

Гарднер М. Математические досуги: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Плоский граф, планарный граф, полный граф, двудольный граф, изоморфизм двудольных графов, полный двудольный граф, теорема Понтрягина — Куратовского, задача об электро-, газо- и водоснабжении, правильная раскраска графа, хроматическое число графа, карта стран, страна, соседние страны, задача о четырех красках, теорема о двуцветных картах, ориентированный граф, орграф, ориентированное ребро, орребро, дуга, исход, заход, (p, q)-орграф, антипараллельные дуги, изоморфизм орграфов, остовный граф, слабая связность орграфа, ормаршрут, сильная связность орграфа, замкнутый ормаршрут, орцикл, эйлеров орграф.

§ 10. Планарные, раскрашенные и ориентированные графы 1°. Плоский и планарный граф. Полный граф В предыдущем параграфе мы рисовали графы на плоскости, и физически, и мысленно. И не задумывались, а на чем еще можно рисовать графы?

Например, графы можно размещать в трехмерном пространстве. Например, трехмерная модель химической молекулы — это граф. Трехмерная реберная модель многогранника — это граф. Представлять графы в трехмерном пространстве можно также мысленно.

Некоторые графы можно нарисовать на плоскости так, что их ребра не будут пересекаться.

Плоский граф.

Плоский граф — изображение графа, нарисованное на плоскости без пересечения ребер.

Ясно, что любой граф, имеющий хотя бы два ребра, можно нарисовать с пересечением ребер. Но не каждый граф можно нарисовать на плоскости без пересечения ребер.

Примеры.

На рисунке 1 показаны:

1) (3, 2)-граф, который нарисован без пересечения ребер и с пересечением двух своих ребер;

2) (4, 6)-граф, который нарисован с пересечением своих шести ребер и без их пересечения;

3) (5, 10)-граф, который можно нарисовать только с пересечением ребер.

Рис. 1. Слева направо: (3, 2)-граф без пересечения ребер; (3, 2)-граф с пересечением;

(4, 6)-граф с пересечением ребер; (4, 6)-граф без пересечения; (5, 10)-граф Быть нарисованным на плоскости без пересечения ребер — это важное свойство, которым может обладать или не обладать конкретный граф.

Планарный граф.

Если граф можно нарисовать на плоскости без пересечения ребер, то он планарный.

Другими словами, планарный граф — граф, изоморфный плоскому.

Безусловно, графы маленьких порядков все являются планарными.

Теорема 2. Планарность маленьких графов.

Все графы до четвертого порядка включительно — планарные.

Доказательство. Для доказательства достаточно нарисовать все эти графы.

Это легко. Некоторая трудность может возникнуть только с графом порядка 4 с самым большим числом ребер 6. На рисунке 3 показан этот граф, нарисованный слева в виде двух неплоских графов, а справа — двух плоских.

Рис. 3. (4, 6)-граф: слева — два неплоских его изображения; справа — два плоских Среди графов порядка 5 все плоские, кроме (5, 10)-графа — самого большого с максимальным количеством вершин (см. рис. 3).

Для графов каждого порядка имеется только один граф с максимальным количеством ребер.

Полный граф.

Граф с максимальным количеством ребер называется полным.

Другими словами, в полном графе каждая пара вершин соединена ребром.

Обозначение полного графа: Kn, где n — порядок графа.

Как уже было сказано, имеется только один полный граф для любого фиксированного количества вершин n. Поэтому полный граф полностью определяется одним инвариантом — количеством вершин, и ему можно присвоить такое простое обозначение — Kn.

Графы K1 — K4 планарны.

Граф K5 непланарен.

Граф K6 содержит K5, поэтому он тоже непланарен (см. рис. 4 справа).

Примеры.

На рисунке 4 нарисованы полные графы порядков от 1 до 6.

Рис. 4. Полные графы, слева направо: K1, K2, K3, K4, K5, K § 10. Планарные, раскрашенные и ориентированные графы 2°. Двудольный граф. Теорема Понтрягина — Куратовского Двудольный граф.

Граф называется двудольным, если его вершины можно разбить на два класса таким образом, чтобы вершины каждого класса не соединялись ребрами друг с другом.

Понятно, что минимальный порядок двудольного графа таков, чтобы были хотя бы две вершины, то есть 2.

Примеры.

Нарисуем все двудольные графы порядков 2 и 3 (см. рис. 5). Вершины одного класс обозначим белыми точками, второго — черными.

Рис. 5. Двудольные графы: слева — все два двудольных графа порядка 2;

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

Изоморфизм двудольных графов.

Два двудольных графа изоморфны, если их можно наложить друг на друга до полного совпадения вершин и ребер. При этом, конечно, можно и нужно передвигать их вершины и растягивать и сжимать их ребра.

Примеры.

Нарисуем на рисунке 6 графы, изоморфные двудольному (3, 2)-графу.

Рис. 6. Изоморфные модификации двудольного (3, 2)-графа Важен случай двудольного графа с максимальным количеством ребер.

Полный двудольный граф.

Если в двудольном графе каждая вершина одного класса соединена ребром с каждой вершиной другого, то это полный двудольный граф.

Обозначение: Kn,m, где n — количество вершин в одном классе двудольного графа, m — количество вершин в другом.

Достаточно очевидно, что порядок полного двудольного графа Kn,m равен n + m.

Примеры.

Нарисуем все полные двудольные графы до порядка 6 включительно. Как и раньше, вершины одного класс обозначим белыми точками, второго — черными. Для каждого двудольного графа указано количество вершин в каждом классе, а также количество вершин и ребер.

Все графы рисунка 7, кроме K3,3, планарные. Граф K3,3 непланарен.

Теорема 8. Число ребер полных графов.

Количество ребер полного графа Kn порядка n равно.

Количество ребер полного двудольного графа Kn,m равно nm.

Доказательство. В каждую из n вершин полного графа Kn входит ровно n 1 ребро. Перемножим количество вершин на количество входящих в них ребер, получим n(n 1). Но этом произведении каждое ребро подсчитано дважды, поэтому количество ребер графа Kn равно.

Из каждой из n вершин одного класса полного двудольного графа Kn,m выходит по m ребер, равное числу вершин второго класса. Следовательно, Поэтому число ребер графа Kn,m равно nm.

Следующую теорему 11 доказал, но не опубликовал, в 1927 г. русский математик Лев Семёнович Понтрягин. Первым опубликовал эту теорему польский математик Казимир Куратовский в 1930 г.

Теорема 9. Теорема Понтрягина — Куратовского.

Граф планарен тогда и только тогда, когда он ни в каком смысле не содержит ни K5, ни K3,3 (обсуждение, в каким смыслах не содержит, выходит за рамки этой книги).

На рисунке 4 справа показано, как граф K6 содержит граф K5.

§ 10. Планарные, раскрашенные и ориентированные графы Не всегда просто понять, является ли данный граф плоским. Обратимся к одной из самых старых топологических задач, которая особенно долго не поддавалась решению и будоражила умы. Мы сохраним ту же формулировку этой задачи, которую ей дал в 1917 году Генри Э. Дьюдени.

Задача об электро-, газо- и водоснабжении.

В каждый из трех домов, изображенных на рисунке 10, необходимо провести свет, газ и воду. Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды?

Другими словами, можно ли построить плоский граф с вершинами в указанных точках?

Решение. Предположим, что коммуникации надо подвести лишь к домам А и Б. Чтобы коммуникации нигде не пересекались, придется разделить плоскость на три области X, Y и Z, например так, как показано на рисунке 11.

Рис. 11. Доказательство неразрешимости задачи об электро-, газо- и водоснабжении Рисовать точно такую же схему совершенно необязательно, но, как бы мы ни соединяли вершины, получившийся граф всегда будет изоморфен графу, изображенному на рисунке 9. Дом В, таким образом, попадает в одну из трех областей X, Y или Z. Попав в область X, он окажется без воды. Находясь в области Y, он будет отрезан от газа. В области Z в него прекратится подача электричества.

Будем окрашивать вершины графов в разные цвета. Цвета обозначим греческими буквами. Будем использовать только правильную раскраску.

Правильная раскраска графа.

При правильной раскраске графа выполнены два условия:

1) смежные вершины имеют разные цвета;

2) используется минимальное возможное количество цветов (см. рис. 12).

Примеры.

Раскрасим все графы порядков 1—3 правильно.

Рис. 12. Раскраска графов порядка 1—3 и их хроматические числа Хроматическое число графа.

Хроматическое число графа — число цветов правильной раскраски графа.

Обозначение хроматического числа графа:.

На рисунке 12 приведена одна из возможных раскрасок вершин графов.

Нужно иметь в виду, что хроматическое число не зависит от того, как раскрашивать граф: при любой правильной раскраске потребуется одно и то же количество красок. Хроматическое число — это инвариант графа, не зависящий от правильной раскраски.

Теорема 13. Хроматические числа графов.

Хроматическое число полного графа Kn порядка n равно n.

Хроматическое число полного двудольного графа Kn,m равно 2.

Хроматическое число любого дерева, имеющего хотя бы одно ребро, равно 2.

Доказательство. Каждая из n вершин полного графа Kn смежна всем остальным n 1 вершинам. Поэтому хроматическое число полного графа Kn порядка n равно n.

Поскольку вершины каждого из двух классов любого двудольного графа попарно не смежны, то вершины одного класса красим в один цвет. В полном двудольном графе Kn,m есть хотя бы одно ребро, поэтому цвета вершин разных классов различны, имеем 2 цвета.

В дереве нет циклов, поэтому три цвета для его окраски не понадобятся.

§ 10. Планарные, раскрашенные и ориентированные графы В XIX веке в Англии хотя и изучали математику, но специалистам математического профиля было сложно устроиться на работу. Так, будущие профессора математики в процессе учебы дополнительно получали юридическое образование и сначала работали адвокатами.

Одному из них, Фрэнсису Гутри, позже профессору математики в Южной Африке, во время его адвокатской деятельности понадобилось раскрасить графства на карте Англии. Поскольку графств было больше, чем цветов для раскраски, некоторые графства должны были иметь одинаковый цвет. При этом каждые два графства, которые имеют общую границу, должны были быть раскрашены в разные цвета. Гутри замечает, что это удается сделать, используя 4 цвета, и ставит вопрос, выполняется ли это для любой возможной карты?

С этим вопросом он посылает 23 октября 1852 года своего младшего брата, тогда еще студента, Фредерика Гутри, позже известного физика, к их общему учителю математики Августу де Моргану, чьим именем в логике и алгебре множеств названы законы де Моргана.

Де Морган не отвечает на этот вопрос, но с помощью примера, показанного справа, констатирует, что существуют карты стран, для которых потребуется не менее четырех красок. Это является доказательством того, что трех красок недостаточно.

Первая важная публикация, относящаяся к проблеме, принадлежит известному математику Артуру Кэли, в которой он объясняет задачу. В связи с этим проблема приобретает большу известность, и уже год спустя церковю ный юрист и любитель математики Альфред Брей Кемпе предлагает доказательство, которое печатается после тщательной проверки. Но через 11 лет, в 1890 году, известный математик Персей Джон Хивуд находит ошибку в доказательстве Кемпе, при этом ему удается показать, что пяти цветов для раскраски хватит в любом случае.

В 1976 году группа американских математиков из университета Иллинойса нашли первое компьютерное доказательство теоремы о четырех красках.

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

Карты стран возникают после нанесения линий границ этих стран. Ясно, что такие линии всегда образуют плоский граф как показано на рисунке 14.

Карта стран. Страна. Соседние страны.

Картой стран называется планарный граф. Страны на карте являются вершинами графа. Две страны являются соседними, если они соединены ребром, как показано на рисунке 14.

Рассматриваются только связные страны. Так, например, Российская Федерация вместе с эксклавной территорией Калининградской области — это несвязная территория.

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

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

Задача о четырех красках.

Достаточно ли для раскраски карты стран четырех красок?

Рассмотрим также боле простую задачу.

Теорема 15. Теорема о двуцветных картах.

Любую карту на плоскости можно раскрасить в два цвета тогда и только тогда, когда все ее вершины четны.

Более широко эта теорема известна для случая, когда плоскость разбивается прямыми линиями.

Теорема 16.

Любую карту на плоскости, которая образована прямыми, всегда можно раскрасить в два цвета.

На рисунке 17а показан простейший пример такой карты — шахматная доска.

Менее правильный узор изображен на рисунке 17б Последнюю теорему можно обобщить на случай более разнообразных карт, образованных либо кривыми без, не имеющими границ, либо замкнутыми кривыми. Пример такой карты приведен на рисунке 17в.

§ 10. Планарные, раскрашенные и ориентированные графы 1°. Определение орграфа. Изоморфизм орграфов Выше, до этого раздела мы рассматривали только графы без ориентации ребер.

Ориентированный граф — орграф.

Ориентированным графом, или орграфом, называется граф с ориентированными ребрами.

Ориентированное ребро — орребро, дуга. Исход. Заход.

Ориентированное ребро, или орребро, или дуга — ребро графа, концы которого неравноценны. Ориентированное ребро начинается на одной вершине орграфа, называемой исходом, и заканчивается на другой вершине — заходе.

Обозначение: дуга обозначается стрелкой, идущей от исхода к заходу.

Примеры.

Нарисуем все орграфы низших порядков 1—2, упорядочив их по количеству дуг, как показано на рисунке 18.

Рис. 18. Единственный орграф порядка 1 и все три орграфа порядка Как Вы уже заметили, орграфы обозначаются числами так же, как и обычные графы.

(p, q)-орграф.

Орграф с p вершинами и q дугами называется (p, q)-орграфом.

Дуги орграфов можно обозначать и по-другому, с помощью прямых, а не изогнутых дуг.

Антипараллельные дуги.

Две противоположные дуги, соединяющие одни и те же две вершины, называются антипараллельными. Такие две дуги называют также двунаправленной дугой.

Обозначение: антипараллельные дуги для экономии места можно обозначать одной двунаправленной дугой, а не двумя однонаправленными дугами.

Примеры.

Нарисуем все орграфы низших порядков 1—2 с помощью прямых дуг, упорядочив их по количеству дуг (см. рис. 19).

Рис. 19. Единственный орграф порядка 1 и все 3 орграфа порядка Еще одно отличие орграфа от графа состоит в том, что в графе две вершины могут соединяться только одним ребром, а в орграфе — двумя антипараллельными ребрами.

В принципе, обычное ребро обычного графа можно рассматривать как две антипараллельные дуги!

В теории орграфов, как и в теории графов, не различают одинаковых, то есть изоморфных, орграфов. В каком бы виде ни рисовали орграф на плоскости, это будет один и тот же орграф.

Изоморфизм орграфов.

Орграфы изоморфны, если их можно наложить друг на друга до полного совпадения вершин и дуг.

При этом, разумеется, можно и нужно растягивать и сжимать их дуги.

Примеры.

На рисунке 20 показаны изоморфные и неизоморфные (3, 4)-орграфы.

Рис. 20. (3, 4)-орграфы двух конфигураций. Слева — три изоморфных (3, 4)-орграфа.

Справа — три изоморфных (3, 4)-орграфа. Орграфы слева и справа неизоморфны 2°. Слабая и сильная связности орграфа Из любого орграфа всегда можно получить обычный граф с неориентированными ребрами, и наоборот.

Остовный граф.

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

Обратите внимание, что неизоморфные орграфы могут иметь один остов.

Примеры.

Все орграфы с рисунка 20 имеют остовом один и тот же (3, 3)-граф.

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

Слабая связность орграфа.

Орграф слабо связен, если связен его остовный граф.

Итак, слабая связность не учитывает направления дуг орграфа.

Примеры.

(2, 0)-орграф на рисунках 18 и 19 слабо несвязен.

Остальные орграфы на рисунках 18, 19 и 20 слабо связны.

§ 10. Планарные, раскрашенные и ориентированные графы Рассмотрим понятие маршрута на орграфе.

Ормаршрут.

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

Нарисуем какой-нибудь орграф и обозначим буквами его вершины (рис. 21). Тогда ормаршруты просто обозначать метками вершин.

Некоторые ормаршруты, которыми можно соедиРис. 21. Граф с поме- нить вершины A и B:

Маршрутов, которыми можно вернуться в вершину A, здесь нет.

В случае с орграфами понятие связности углубляется.

Сильная связность орграфа.

Орграф сильно связен, если любые две его вершины соединяются ормаршрутами в обе стороны.

Только (2, 2)-орграф на рисунке 18 сильно связен. Остальные орграфы на рисунках 18, 19 и 20 сильно несвязны.

Совершенно очевидно, что сильно связный орграф слабо связен, а обратное неверно. Поэтому, в частности, сильно связным может быть только слабо связный орграф.

Рассмотрим различные виды ормаршрутов.

Замкнутый ормаршрут. Орцикл.

Ормаршрут замкнут, если он соединяет вершину саму с собой, и открыт в противном случае.

Ормаршрут называется орциклом, если все его дуги различны, а также различны все его вершины, кроме, быть может, конечных.

(2, 2)-орграф на рисунках 18 и 19 имеет только один орцикл, соединяющий две вершины антипараллельными дугами. Остальные орграфы на рисунках 18, 19 и 20 орциклов не имеют.

Эйлеров орграф.

Слабо связный орграф эйлеров, если имеется замкнутый ормаршрут, проходящий по всем дугам ровно по одному разу.

На рисунках 18, 19 и 20 сильно связные графы эйлеровы, и наоборот.

Нарисуем пять графов.

1.1. Какой по порядку граф неполный?

1.2. Какой по порядку граф непланарный?

1.3. Какой по порядку граф плоский?

1.4. Какой по порядку граф эйлеров?

1.5. Сколько здесь разных, то есть неизоморфных друг другу, графов?

Нарисуем пять графов.

2.1. Какой по порядку граф неполный?

2.2. Какой по порядку граф непланарный?

2.3. Какой по порядку граф плоский?

2.4. Какой по порядку граф эйлеров?

2.5. Сколько здесь разных, то есть неизоморфных друг другу, графов?

§ 10. Планарные, раскрашенные и ориентированные графы Нарисуем все семь графа порядков 1—3.

3.1. Чему равно хроматическое число графа (3, 3)?

3.2. Чему равно хроматическое число графа (3, 2)?

3.3. Чему равно хроматическое число графа (3, 1)?

3.4. Чему равно хроматическое число графа (3, 0)?

3.5. Чему равно хроматическое число графа (2, 1)?

4. Определение орграфа. Изоморфизм орграфов Нарисуем несколько орграфов.

4.1. Какой по порядку орграф не имеет изоморфного орграфа?

4.2. Сколько двунаправленных дуг у орграфов?

4.3. Сколько простых дуг у тех орграфов, у которых они есть?

4.4. Сколько дуг имеет орграф, который не имеет изоморфного орграфа среди представленных орграфов?

4.5. Сколько вершин имеют орграфы, имеющие более 2 дуг?

Нарисуем несколько орграфов.

4.1. Сколько орграфов из представленных либо слабо, либо сильно связны?

4.2. Сколько орграфов из представленных слабо связны?

4.3. Сколько орграфов из представленных сильно связны?

4.4. Сколько дуг имеют сильно связные орграфы?

4.5. Сколько дуг имеют слабо связные орграфы?

Пусть n — номер варианта от 1 до 16. Выполните упражнение с номером Вашего варианта.

1, 9. Перерисуйте графы с рисунка 7, если это возможно, в плоском виде, причем все ребра должны быть отрезками прямых линий.

2, 10. Нарисуйте все 10 двудольных графов порядка 4, упорядочив их сначала по количеству вершин в одном из классов, а затем по количеству ребер.

3, 11. Нарисуйте, упорядочив их по количеству ребер, правильно раскрасьте и определите хроматические числа всех 11 графов порядка 4.

4, 12. Нарисуйте все 6 деревьев порядка 6, правильно раскрасив их в два цвета.

5, 13. Нарисовать все 16 орграфов порядка 3 с метками вершин, упорядочив их сначала по количеству дуг, а затем по количеству двунаправленных дуг. Для каждого графа выпишите количество компонентов слабой связности.

6, 14. Нарисовать все 16 орграфов порядка 3 с метками вершин, упорядочив их сначала по количеству дуг, а затем по количеству двунаправленных дуг. Для каждого графа выпишите количество компонентов сильной связности.

7, 15. Нарисовать все 16 орграфов порядка 3 с метками вершин, упорядочив их сначала по количеству дуг, а затем по количеству двунаправленных дуг. Для каждого графа выпишите количество орциклов, причем орциклы следует перечислить.

8, 16. Нарисуйте все 3 эйлеровых орграфов порядка 3.

§ 11. Правильные многогранники 1. Трехмерные правильные многогранники..................................

1°. Определение правильного многогранника.............................

2. Многомерные правильные многогранники................................

2°*. Тетраэдр

3°*. Октаэдр

Болтянский В. Г., Савин А. П. Беседы о математике. Книга 1. Дискретные объекты.— М.: ФИМА, МЦНМО, 2002.

Гарднер М. Математические головоломки и развлечения: 2-е изд., испр. и дополн. / Пер. с англ.— М.: Мир, 1999.

Гарднер М. Этот правый, левый мир: 2-е изд., испр. и дополн. / Пер. с англ.— М.: Мир, 2007.

Гарднер М. Математические новеллы: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Многоугольник, правильный многоугольник, многогранник, правильный многогранник, грань, ребро, вершина, тетраэдр, октаэдр, куб, додекаэдр, икосаэдр, полуправильный многогранник, призма, антипризма, инвариант, двойственность правильных многогранников, формула Декарта — Эйлера, четырехмерный куб, гиперкуб, четырехмерный тетраэдр, четырехмерный октаэдр.

§ 11. Правильные многогранники 1. Трехмерные правильные многогранники 1°. Определение правильного многогранника Как всегда, начнем с определений.

Многоугольник. Правильный многоугольник.

Начнем с многоугольников, или полигонов,— фигур на плоскости, составленных из отрезков.

Правильный многоугольник — выпуклый многоугольник, у которого все стороны и все углы равны.

Условие выпуклости в этом определении существенно. В доказательство приведем пример невыпуклого многоугольника, у которого все стороны и все углы равны — правильную звезду (см. рис. 1).

Рис. 1. Пример невыпуклого многоугольника с равными сторонами и углами Теперь приведем примеры правильных многоугольников — треугольник, квадрат, правильные пятиугольник и шестиугольник(см. рис. 2).

Очевидно, что правильные многоугольники однозначно определяются количеством сторон, и количество правильных многоугольников бесконечно.

Многогранник (полиэдр). Правильный многогранник. Платоново тело.

Перейдем к многогранникам, или полиэдрам,— фигурам в пространстве, составленным из многоугольников.

Правильный многогранник, или платоново тело,— выпуклый многогранник, составленный из одинаковых правильных многоугольников.

Условия выпуклости и одинаковости многоугольников существенны.

Приведем на рисунке 3 слева пример невыпуклого многогранника, составленного из одинаковых правильных многоугольников — квадратов.

Приведем на рисунке 3 справа пример выпуклого многогранника, составленного из разных правильных многоугольников, квадратов и правильных треугольников — призму.

Рис. 3. Пример невыпуклого многогранника, составленного из квадратов, и выпуклого многогранника, составленного из квадратов и правильных треугольников 2°. Пять правильных многогранников Назовем составные части многогранника.

Грань. Ребро. Вершина.

Грань многогранника — многоугольник, которым многогранник ограничен в пространстве.

Ребро многогранника — отрезок, которым ограничена грань.

Вершина многогранника — точка, которой ограничено ребро.

Сколько всего имеется правильных многогранников?

Теорема 4. Количество правильных многогранников.

Правильных многогранников ровно пять.

Доказательство. Телесный угол при вершине должен быть меньше 360°.

Кроме того, в вершине сходится не менее 3 граней. Отсюда следует, что в вершине может сходиться 3, 4 или 5 правильных треугольника, поскольку треугольников уже образуют телесный угол в 360° и не могут сходиться в вершине многогранника Аналогично в вершине может сходиться 3 квадрата или 3 пятиугольника:

4 квадрата дадут угол 360°, а 4 пятиугольника — более 360°.

Наконец, 3 шестиугольника дают угол в 360°, 3 семиугольника и так далее — более 360°.

Итак, правильных многогранников не более пяти. Существуют ровно пять правильных многогранника: они показаны на рисунке 5.

Рис. 5. Пять платоновых тел: тетраэдр, гексаэдр, октаэдр, додекаэдр и икосаэдр В названиях многоугольников присутствуют обычные русские числительные: треугольник, четырехугольник и так далее. Названия же многогранников происходят от греческих числительных (см. табл. 6).

§ 11. Правильные многогранники Тетраэдр (правильная треугольная пирамида). Октаэдр. Куб (гексаэдр). Додекаэдр. Икосаэдр.

Тетраэдр, или правильная треугольная пирамида, имеет при всех вершинах по 3 правильных треугольника.

Гексаэдр, или куб, имеет при всех вершинах по 3 квадрата.

Октаэдр имеет при всех вершинах по 4 правильных треугольника.

Додекаэдр имеет при всех вершинах по 3 правильных пятиугольника.

Икосаэдр имеет при всех вершинах по 5 правильных треугольников.

Приставки — названия первых чисел в математике Дадим рекомендации, как можно быстро и правильно нарисовать пять правильных многогранников. Тетраэдр удобно начать рисовать с треугольника (рис. 7), а гексаэдр — с квадрата (рис. 7). Октаэдр рисуется с квадрата, нарисованного горизонтально показанного на рисунке 7 внутри октаэдра.

Додекаэдр рисуется, начиная с пятиугольной антипризмы, показанной внутри додекаэдра (рис. 7). Эта антипризма состоит из 2 параллельных пятиугольников, повернутых друг относительно друга и соединенных 10 треугольниками. Затем стороны пятиугольников стираются. Икосаэдр рисуется, тоже начиная с пятиугольной антипризмы, показанной внутри икосаэдра (рис. 7). Здесь стороны пятиугольников не стираются.

Рис. 7. Как рисовать тетраэдр, гексаэдр, октаэдр, додекаэдр и икосаэдр 3°. Полуправильные многогранники В предыдущем пункте уже использовалась пятиугольная антипризма. Рассмотрим более подробно такие многогранники, которые называются полуправильными.

Полуправильный многогранник.

Полуправильный многогранник, или архимедово тело — выпуклый многогранник, составленный из двух разных правильных многоугольников.

Здесь мы не будем рассматривать все полуправильные многогранники, и приведем только две их бесконечные серии — призмы и антипризмы. Описания оставшихся без рассмотрения 12 полуправильных многогранников можно найти в литературе.

Призма и антипризма.

Правильной n-угольной призмой называются два основания — параллельные правильные n-угольника, соединенные боковыми сторонами — n квадратами.

Правильной n-угольной антипризмой называются два основания — параллельные правильные n-угольника, соединенные боковыми сторонами — 2n правильными треугольниками.

Изобразим на рисунке 8 первые четыре призмы из бесконечной серии призм.

Отметим, что четырехугольная призма — это правильный многогранник куб, а остальные призмы — треугольная, пятиугольная и шестиугольная — полуправильные многогранники.

треугольная, четырехугольная, пятиугольная и шестиугольная призма На рисунке 9 показаны первые четыре антипризмы из бесконечной серии антипризм.

Отметим, что треугольная антипризма — это правильный многогранник октаэдр, а остальные антипризмы — четырехугольная, пятиугольная и шестиугольная — полуправильные многогранники.

Рис. 9. Антипризмы: треугольная, четырехугольная, пятиугольная и шестиугольная § 11. Правильные многогранники Найдем закономерность между количеством граней, ребер и вершин правильных многогранников. Сначала выработаем гипотезу, попробуем получить формулу, которая связывает эти числа.

Посмотрим, как изменится количество граней, ребер и вершин, если добавить одно ребро.

Возьмем сначала какой-нибудь простую грань, например, треугольник, показанный на рисунке 10 слева, и добавим в треугольник одно ребро между двумя ребрами треугольника, как показано на рисунке 10 справа). Получим, что при добавлении такого ребра количество граней увеличивается на 1, количество ребер — на 3 и количество вершин — на 2.

Теперь добавим в треугольник (см. рис. 11 слева) одно ребро между вершиной и ребром треугольника (см. рис. 11 справа). Получим, что при добавлении такого ребра количество граней увеличивается на 1, количество ребер — на 2 и количество вершин — на 1.

Рис. 11. Добавление ребра между вершиной и ребром В обоих случаях количество добавившихся ребер равно сумме добавившихся граней и вершин.

Инвариант.

Предположим, что разность между количеством ребер многогранников и суммой их граней и вершин является инвариантом, то есть одним и тем же постоянным числом для всех многогранников.

Теперь проверим эту гипотезу сначала на правильных многогранниках, а затем и на полуправильных.

Тетраэдр имеет 4 грани, 6 ребер и 4 вершины, что позволяет определить наш инвариант: 4 + 4 6 = 2. Посмотрим, получим ли тот же инвариант для других правильных многогранников.

У гексаэдра 6 граней, 12 ребер и 8 вершин, получаем: 6 + 8 12 = 2.

У октаэдра 8 граней, 12 ребер и 6 вершин, получаем: 8 + 6 12 = 2.

У додекаэдра 12 граней, 30 ребер и 20 вершин, получаем: 12 + 20 30 = 2.

У икосаэдра 20 граней, 30 ребер и 12 вершин, получаем: 20 + 12 30 = 2.

Двойственность правильных многогранников.

Правильные многогранники двойственны:

1) гексаэдр и октаэдр двойственны, так как количество граней гексаэдра равно количеству граней октаэдра, и наоборот;

2) додекаэдр и икосаэдр двойственны аналогично;

3) тетраэдр двойствен сам себе: он самодвойственный.

Наше утверждение верно не только для правильных многогранников!

Проверим его для призм и антипризм.

У треугольной призмы 5 граней, 9 ребер и 6 вершин, получаем:

У пятиугольной призмы 7 граней, 15 ребер и 10 вершин, получаем:

У шестиугольной призмы 8 граней, 18 ребер и 12 вершин, получаем:

У четырехугольной антипризмы 10 граней, 16 ребер и 8 вершин, получаем: 10 + 8 16 = 2.

У пятиугольной антипризмы 12 граней, 20 ребер и 10 вершин, получаем:

12 + 10 20 = 2.

У шестиугольной антипризмы 14 граней, 24 ребра и 12 вершин, получаем:

14 + 12 24 = 2.

Итак, получаем теорему.

Теорема 12. Формула Декарта — Эйлера.

Для любого выпуклого многогранника верна формула где Г — количество граней многогранника, В — количество его вершин и Р — количество его ребер.

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

Теорема 13. Призмы и антипризмы.

n-угольная призма, n 3, имеет n + 2 грани, 3n ребер и 2n вершин.

n-угольная антипризма, n 3, имеет 2n + 2 грани, 4n ребер и 2n вершин.

§ 11. Правильные многогранники 5°*. Проекции правильных многогранников Пять правильных многогранников легко спроектировать на плоскость так, чтобы получились красивые плоские графы.

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

Рис. 14. Проекции правильных многогранников на плоскость.

Слева направо: тетраэдр, октаэдр, куб, додекаэдр, икосаэдр 2. Многомерные правильные многогранники Построим последовательно нульмерный, одномерный, двумерный, трехмерный и так далее куб. Для этого придумаем единый алгоритм получения из куба меньшей размерности куб большей размерности.

Этот алгоритм — параллельный перенос. Процесс получения из нульмерного куба, то есть просто точки, одномерного куба, то есть отрезка, и так далее до четырехмерного куба показан на рисунке 15. Каждый раз количество вершин удваивается, и добавляются две новые грани.

Рис. 15. Получение параллельным переносом из нульмерного куба — точки — одномерного куба, затем двумерного куба — квадрата, трехмерного куба — просто куба и, наконец, четырехмерного куба Рассмотрим количественные закономерности, получающиеся при таком построении.

1. Отрезок имеет 2 конца.

2. Квадрат имеет 4 вершины и 4 стороны.

3. Куб имеет 8 вершин и 6 граней.

4. Четырехмерный куб имеет 16 вершин и 8 трехмерных граней (тоже кубов), которые заштрихованы парами противоположных граней на рисунке 16.

Рис. 16. Восемь заштрихованных трехмерных граней — кубов — четырехмерного куба, второй — образом исходного куба при параллельном переносе, а шесть остальных построены на шести гранях исходного куба Итак, мы построили четырехмерный куб. Далее мы построим также четырехмерные тетраэдр и октаэдр. Но сначала дадим определения этим четырехмерным правильным фигурам.

§ 11. Правильные многогранники Четырехмерные куб (гиперкуб), тетраэдр и октаэдр.

Четырехмерный куб, или гиперкуб — правильный многогранник в четырехмерном пространстве, у которого в каждой вершине сходится четыре трехмерных куба.

Четырехмерный тетраэдр — правильный многогранник в четырехмерном пространстве, у которого в каждой вершине сходится четыре трехмерных тетраэдра.

Четырехмерный октаэдр — правильный многогранник в четырехмерном пространстве, у которого в каждой вершине сходится восемь трехмерных тетраэдров.

Алгоритм построения тетраэдров — добавление точки. Процесс получения из нульмерного тетраэдра, то есть просто точки, одномерного тетраэдра, то есть отрезка, и так далее до четырехмерного тетраэдра показан на рисунке 17. Каждый раз добавляются одна новая вершина, которая образует со старым гранями новые грани размерностью на 1 больше. Количество граней также увеличивается на 1 за счет исходного многогранника.

Рис. 17. Получение добавлением точки из нульмерного тетраэдра — точки — одномерного тетраэдра, затем двумерного тетраэдра — правильного треугольника, трехмерного тетраэдра — просто тетраэдра и, наконец, четырехмерного тетраэдра Рассмотрим количественные закономерности, получающиеся при этом.

1. Отрезок имеет 2 конца.

2. Треугольник имеет 3 вершины и 3 стороны.

3. Тетраэдр имеет 4 вершины и 4 грани.

4. Четырехмерный тетраэдр имеет 5 вершин и 5 трехмерных граней (тоже тетраэдров), как показано на рисунке 18.

Рис. 18. Пять заштрихованных трехмерных граней — тетраэдров — четырехмерного тетраэдра. Один из них является исходным тетраэдром, а четыре остальные построены на четырех гранях исходного тетраэдра Рассмотрено два способа порождения отрезка из точки: параллельный перенос и добавление точки. Остался один способ: распространение из центра.

Процесс получения из нульмерного октаэдра, то есть просто точки, одномерного октаэдра, то есть отрезка, и так далее до четырехмерного октаэдра показан на рисунке 19. Каждый раз добавляются две новые вершины, которые образуют со старыми гранями новые грани размерностью на 1 больше.

То есть количество граней удваивается.

Рис. 19. Получение добавлением точки из нульмерного октаэдра — точки — одномерного октаэдра, затем двумерного октаэдра — квадрата, трехмерного октаэдра — просто октаэдра и, наконец, четырехмерного октаэдра Рассмотрим количественные закономерности, получающиеся при этом.

1. Отрезок имеет 2 конца.

2. Квадрат имеет 4 вершины и 4 стороны.

3. Октаэдр имеет 6 вершин и 8 граней.

4. Четырехмерный октаэдр имеет 8 вершин и 16 трехмерных граней (тетраэдров!), как показано на рисунке 20, где заштрихованы пары противоположных граней.

Рис. 20. Шестнадцать заштрихованных трехмерных граней — тетраэдров — четырехмерного октаэдра. Восемь из них образованы восемью гранями восемь остальных — восемью гранями исходного октаэдра и другой новой вершиной Изучая количество вершин и сторон четырехмерных гексаэдра и октаэдра, легко установить, что они двойственны друг другу точно так же, как и трехмерные.

Четырехмерный тетраэдр по-прежнему двойственен сам себе, о чем говорит равенство количеств его вершин и граней.

§ 11. Правильные многогранники 1. Определение трехмерных правильных многогранников Приведем все пять правильных многогранника:

1.1. Каким по счету из приведенных правильных многогранников является додекаэдр?

1.2. Каким по счету из приведенных правильных многогранников является куб?

1.3. Каким по счету из приведенных правильных многогранников является икосаэдр?

1.4. Каким по счету из приведенных правильных многогранников является тетраэдр?

1.5. Каким по счету из приведенных правильных многогранников является октаэдр?

2. Вершины трехмерных правильных многогранников Приведем все пять правильных многогранника:

2.1. Сколько вершин у додекаэдра?

2.2. Сколько вершин у куба?

2.3. Сколько вершин у икосаэдра?

2.4. Сколько вершин у тетраэдра?

2.5. Сколько вершин у октаэдра?

3. Грани трехмерных правильных многогранников Приведем все пять правильных многогранника:

3.1. Сколько граней у додекаэдра?

3.2. Сколько граней у куба?

3.3. Сколько граней у икосаэдра?

3.4. Сколько граней у тетраэдра?

3.5. Сколько граней у октаэдра?

§ 11. Правильные многогранники 4. Ребра трехмерных правильных многогранников Приведем все пять правильных многогранника:

4.1. Сколько ребер у додекаэдра?

4.2. Сколько ребер у куба?

4.3. Сколько ребер у икосаэдра?

4.4. Сколько ребер у тетраэдра?

4.5. Сколько ребер у октаэдра?

5. Многомерные правильные многогранники Приведем три правильных четырехмерных многогранника:

5.1. Сколько трехмерных граней у четырехмерного куба?

5.2. Сколько трехмерных граней и вершин у четырехмерного тетраэдра?

5.3. Сколько трехмерных граней у четырехмерного октаэдра?

5.4. Сколько вершин у четырехмерного куба?

5.5. Сколько вершин у четырехмерного октаэдра?

Пусть n — номер варианта от 1 до 16. Выполните упражнение с номером Вашего варианта.

1, 9. Напишите математические названия треугольника, четырехугольника и так далее до десятиугольника с использованием греческих числительных.

2, 10. Нарисуйте тетраэдр, куб и октаэдр.

3, 11. Нарисуйте додекаэдр.

4, 12. Нарисуйте икосаэдр.

5, 13. Нарисуйте треугольную, четырехугольную, пятиугольную и шестиугольную призмы.

6, 14. Нарисуйте треугольную, четырехугольную, пятиугольную и шестиугольную антипризмы.

7, 15. Нарисуйте четырехмерный куб.

8, 16. Посчитайте, сколько ребер имеет четырехмерные куб.

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

§ 12. Топология Гильберт Д., Кон-Фоссен С. Наглядная геометрия.

Болтянский В. Г., Савин А. П. Беседы о математике. Книга 1. Дискретные объекты.— М.: ФИМА, МЦНМО, 2002.

Прасолов В. В. Наглядная топология.— М.: МЦНМО, 2006.

Гарднер М. Математические досуги: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Гарднер М. Математические головоломки и развлечения: 2-е изд., испр. и дополн. / Пер. с англ.— М.: Мир, 1999.

Гарднер М. Математические новеллы: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Топология, фигура, кривая, поверхность, непрерывная деформация, гомеоморфизм, сторона, связность, край, замкнутая поверхность, открытая поверхность, инвариант, сфера, тор, крендель, степень связности, разрез, лента Мёбиуса, бутылка Клейна, проективная плоскость.

§ 12. Топология 1°. Определение фигуры. Гомеоморфизм Математика держится на двух китах: алгебре и топологии. Алгебра хорошо известна со школы. Дадим определение топологии.

Топология.

Топология — раздел математики, исследующий идею непрерывности.

Топология имеет дело с объектами, которые называют фигурами.

Фигура.

Фигура, или топологическое пространство — подмножество нашего однородного евклидового пространства, между точками которого задано некоторое отношение близости.

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

Будем рассматривать только одномерные и двумерные фигуры.

Кривая и поверхность.

Одномерная фигура называется кривой, двумерная — поверхностью.

В топологии очень важно следующее обстоятельство.

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

Непрерывная деформация.

Деформация фигуры непрерывна, если соседние точки фигуры переходят при деформации тоже в соседние точки.

Можно представлять, что фигуры сделаны из пластилина, которые нельзя разрывать, или из очень-очень мягкой резины, или нарисованы на поверхности воздушного шарика.

Дадим математическое определение топологического равенства фигур.

Гомеоморфизм.

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

Как видите, в разных областях математики равенство объектов называется по-разному. В одних математических науках объекты равны, в других — эквивалентны, в третьих — изоморфны, в топологии — гомеоморфны.

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

Пример.

Возьмем квадрат вместе с его внутренностью (см. рис. 1) и посмотрим, в какие фигуры его можно непрерывно деформировать.

Если квадрат хорошо «надуть» так, чтобы пропали его углы, то получим круг (см. рис. 1).

Если квадрат просто растянуть или сжать вдоль одной стороны, то получим полосу, или ленту (см. рис. 1).

Если полосу изогнуть, то получим подкову (см. рис. 1).

Если подкову изогнуть еще раз, то получим букву S (см. рис. 1).

Рис. 1. Квадрат и фигуры, ему гомеоморфные: круг, лента, подкова, буква S Квадрат — двумерная фигура, поскольку для задания положения точки на нем требуются две координаты. Квадрат — это поверхность. Рассмотрим другие поверхности и их свойства.

Сначала введем определения некоторых понятий.

Сторона, связность, край.

Сторона — часть поверхность, по которой может ползать муравей; при этом он не должен переползать через край поверхности, если он есть.

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

Край — кривая, разделяющая стороны поверхности.

На основе этих простейших понятий мы уже можем классифицировать фигуры.

Замкнутая и открытая поверхности.

Поверхность называется замкнутой, если она не имеет ни одного края, и открытой, если есть хотя бы один край.

Приведем примеры.

§ 12. Топология Примеры.

У квадрата две стороны и один край (см. рис. 1). Запишем это в таблицу 21.

Поэтому квадрат — открытая поверхность.

Еще две открытые поверхности и поверхности, им гомеоморфные, показаны на рисунках 2 и 3.

квадрат с дыркой, кольцо на боку, поверхность цилиндра квадрат с двумя дырками, знак «стоянка запрещена», цифра У кольца две стороны и два края, а у восьмерки две стороны и три края (см. рис. 2 и 3). Запишем это в таблицу 21. Кольцо и восьмерка — открытые поверхности.

Итак, наши фигуры вполне можно различить по количеству краев.

Инвариант.

Топологический инвариант фигуры, или просто инвариант — число, которое характеризует фигуру и не изменяется при гомеоморфизме.

Количество сторон поверхности и количество ее краев являются инвариантами, они полностью характеризуют открытые поверхности.

Квадрат, кольцо и восьмерка отличаются друг от друга только количеством краев: кольцо — это квадрат с дыркой, а восьмерка — это квадрат с двумя дырками.

Посмотрим, как можно преобразовать квадрат в кольцо.

На рисунке 4 показан первый способ преобразования квадрата в кольцо.

При этом требуется одна склейка. На рисунке 5 показан второй способ преобразования квадрата в поверхность цилиндра. При этом также требуется одна склейка.

Если прокрутить эти преобразования задом наперед, то получится преобразование кольца в квадрат с помощью одного разреза.

Рис. 4. Преобразование квадрата в кольцо при помощи одной склейки Рис. 5. Преобразование квадрата в поверхность цилиндра при помощи одной склейки Примеры.

Приведем еще две открытые поверхности и поверхности, им гомеоморфные, на рисунках 6 и 7.

Рис. 6. Плашка с тремя дырками и фигуры, ей гомеоморфные:

квадрат с тремя дырками, квадрат с тремя ручками Рис. 7. Плашка с четырьмя дырками и фигуры, ей гомеоморфные:

квадрат с четырьмя дырками, квадрат с четырьмя ручками В этом пункте приведем некоторые примеры гомеоморфных замкнутых поверхностей.

Примеры.

Три замкнутые поверхности и поверхности, им гомеоморфные, показаны на рисунках 8, 9 и 10.

Сфера.

Сфера — поверхность шара (см. рис. 8).

§ 12. Топология поверхность куба, поверхность пирамиды, поверхность стакана Тор — поверхность бублика (см. рис. 9).

Рис. 9. Тор и фигуры, ему гомеоморфные: сфера с ручкой, поверхность кружки Крендель.

Крендель — тор с двумя дырками (см. рис. 10).

сфера с двумя ручками, поверхность кружки с двумя ручками Сфера, тор и крендель имеют по две стороны и не имеют краев (см. рис. 8, 9 и 10). Запишем это в таблицу 21. Сфера, тор и крендель — замкнутые поверхности.

Получается, что по количеству краев сферу, тор и крендель не различить.

Для их различения нужен новый инвариант.

Посмотрим, как можно преобразовать квадрат в тор.

На рисунке 11 показан первый способ преобразования квадрата в тор. При этом требуется две склейки. На рисунке 12 показан второй способ преобразования квадрата в тор. При этом также требуется две склейки.

Если прокрутить эти преобразования задом наперед, то получится преобразование тора в квадрат с помощью двух разрезов.

Рис. 11. Преобразование квадрата в тор при помощи двух склеек Рис. 12. Преобразование квадрата в тор при помощи двух склеек Примеры.

Приведем еще две замкнутые поверхности и поверхности, им гомеоморфные, на рисунках 13 и 14.

Рис. 13. Крендель с тремя дырками и фигуры, ему гомеоморфные:

сфера с тремя ручками, поверхность кружки с тремя ручками Рис. 14. Крендель с четырьмя дырками и фигуры, ему гомеоморфные:

сфера с четырьмя ручками, поверхность кружки с четырьмя ручками § 12. Топология 3°. Степень связности поверхности Степень связности, разрез.

Степень связности — максимальное число разрезов, которые можно провести на поверхности так, чтобы она не распалась на два отдельных куска, перестав быть связной.

Разрез — кривая на поверхности либо замкнутая, либо обязательно от края до края поверхности.

Примеры.

Квадрат любым разрезом от края до края распадается на две части, поэтому степень связности квадрата 0 (рис. 15). Кольцо одним разрезом поперек превращается в квадрат, поэтому степень связности кольца 1 (рис. 15).

Восьмерка одним разрезом поперек превращается в кольцо со степенью связности 1, степень связности восьмерки 2 (рис. 16). Сфера любым разрезом по замкнутой линии распадается на две части, степень связности сферы 0 (рис. 16).

Тор одним разрезом по замкнутой линии вокруг дырки превращается в кольцо со степенью связности 1, степень связности тора 2 (рис. 17). Крендель двумя разрезами по замкнутым линиям вокруг дырок превращается в восьмерку со степенью связности 2, степень связности кренделя 4 (рис. 17).

Все эти инварианты можно свести в одну таблицу (см. табл. 21).

Теперь видно, что сфера, тор и крендель отличаются друг от друга степенью связности: у сферы степень связности 0, у тора — 2 и у кренделя — 4.

Рис. 15. В квадрате нельзя провести ни одного разреза, чтобы квадрат не распался, а в кольце можно провести один разрез, и кольцо превращается в квадрат Рис. 16. В восьмерке можно провести один разрез, и восьмерка превращается в кольцо, а сфера любым замкнутым разрезом распадается на две части Рис. 17. В торе можно провести один разрез, и тор превращается в кольцо, а в кренделе можно провести два разреза, и крендель превращается в восьмерку Рассмотрим поверхности, у которых не краев — замкнутые поверхности.

Лента Мёбиуса была обнаружена немецким математиком Августом Фердинандом Мёбиусом в 1858 г.

Лента Мёбиуса (лист Мёбиуса).

Лента Мёбиуса, или лист Мёбиуса,— лента, перекрученная на пол-оборота (см. рис. 18 слева).

До этого года математики не знали о существовании поверхностей с одной стороной. Одна сторона понимается, конечно, не локально, а глобально: муравей может ползать по всей ленте Мёбиуса, не переползая через ее край.

У ленты Мёбиуса 1 сторона и 1 край, в чем можно убедиться, выполнив упражнения в конце параграфа. Степень связности у ленты Мёбиуса 1, такая же, как и у обычной ленты: после разрезания поперек лента Мёбиуса превращается в квадрат.

Бутылка Клейна была открыта в 1882 г. немецким математиком Феликсом Клейном.

Бутылка Клейна.

Бутылка Клейна — бутылка, имеющая одну сторону, как показано на рисунке 18 справа.

Рис. 18. Лента Мёбиуса (слева) и бутылка Клейна (справа) § 12. Топология Бутылка Клейна имеет одну строну и не имеет краев.

На рисунке 19 слева направо показано, как лента Мёбиуса получается из обычной ленты.

На рисунке 20 слева направо показано, как бутылка Клейна получается из поверхности цилиндра.

Изучив этот рисунок справа налево, в обратную сторону, можно понять, как после одного разреза бутылка Клейна превращается в поверхность цилиндра, то есть в кольцо. Поэтому степень связности бутылки Клейна 2.

Рис. 20. Склеивание бутылки Клейна из поверхности цилиндра Сведем все инварианты рассмотренных поверхностей в одну таблицу.

При проектировании одной плоскости на другую точки плоскости могут уйти в бесконечность.

Проективная плоскость.

Проективная плоскость получается из обычной эвклидовой дополнением последней бесконечно удаленными точками, образующими бесконечно удаленную прямую.

Итак, проективная плоскость — замкнутая односторонняя поверхность.

При разрезе проективная плоскость превращается в лист Мёбиуса, поэтому ее степень связности равна 2.

Проективную плоскость можно склеить из квадрата, как тор и бутылку Клейна. Сначала деформируем квадрат, превратив его в сферу без квадрата, как показано на рисунке 22.

Рис. 22. Превращение квадрата в сферу без квадрата непрерывной деформацией Теперь возьмем сферу без квадрата ABCD склеим AB с CD и DA с BC так, чтобы совпали точки A с C и B с D, как показано на рисунке 23. Для этого приподнимем точки A и C и опустим точки B и D. Получим замкнутую поверхность с линией самопересечения в виде отрезка AB, топологическую эквивалентную проективной плоскости.

Рис. 23. Превращение сферы без квадрата склеиванием в проективную плоскость Подведем итоги нашим склеиванием. Получается, что основные поверхности можно склеивать из квадрата. Перепишем таблицу 21, нарисовав основные поверхности и способ их склеивания из квадрата.

§ 12. Топология Склеивание сторон квадрата в таблице 20 обозначено следующим образом:

1) склеиваются только те стороны, которые обозначенные стрлками;

2) стрлки склеиваются таким образом, чтобы одинаковые стрелки точно наложились друг на друга.

Инварианты поверхностей и склеивание их из квадрата Поверхность Изображение Сторон Краев Квадрат показан справа.

1.1. Сколько краев у квадрата?

1.2. Сколько сторон у квадрата?

1.3. При скольких разрезах от края до края квадрат не распадается на две части?

1.4. Сколько требуется склеек, чтобы сделать из квадрата кольцо?

1.5. Сколько требуется склеек, чтобы сделать из квадрата тор?

Кольцо показан справа.

2.1. Сколько краев у кольца?

2.2. Сколько сторон у кольца?

2.3. При скольких разрезах от края до края кольцо не распадается на две части?

2.4. Сколько требуется разрезов, чтобы сделать из кольца квадрат?

2.5. Сколько требуется склеек, чтобы сделать из кольца тор?

§ 12. Топология Восьмерка показана справа.

3.1. Сколько краев у восьмерки?

3.2. Сколько сторон у восьмерки?

3.3. При скольких разрезах от края до края восьмерка не распадается на две части?

3.4. Сколько требуется разрезов, чтобы сделать из восьмерки квадрат?

3.5. Сколько требуется разрезов, чтобы сделать из восьмерки кольцо?

Сфера показана справа.

4.1. Сколько краев у сферы?

4.2. Сколько сторон у сферы?

4.3. При скольких замкнутых разрезах сфера не распадается на две части?

4.4. Сколько требуется замкнутых разрезов, чтобы сделать из сферы квадрат?

4.5. При скольких замкнутых разрезах сфера распадается на две части?

Тор показан справа.

5.1. Сколько краев у тора?

5.2. Сколько сторон у тора?

5.3. При скольких замкнутых разрезах тор не распадается на две части?

5.4. Сколько требуется замкнутых разрезов, чтобы сделать из тора квадрат?

5.5. Сколько требуется замкнутых разрезов, чтобы сделать из тора кольцо?

Крендель показан справа.

6.1. Сколько краев у кренделя?

6.2. Сколько сторон у кренделя?

6.3. При скольких замкнутых разрезах крендель не распадается на две части?

6.4. Сколько требуется замкнутых разрезов, чтобы сделать из кренделя квадрат?

6.5. Сколько требуется замкнутых разрезов, чтобы сделать из кренделя кольцо?

§ 12. Топология Лента Мёбиуса показана справа.

7.1. Сколько краев у ленты Мёбиуса?

7.2. Сколько сторон у ленты Мёбиуса?

7.3. При скольких замкнутых разрезах лента Мёбиуса не распадается на две части?

7.4. Сколько требуется замкнутых разрезов, чтобы сделать из ленты Мёбиуса квадрат?

7.5. При скольких замкнутых разрезах лента Мёбиуса распадается на две части?

Бутылка Клейна показана справа.

8.1. Сколько краев у ленты бутылки Клейна?

8.2. Сколько сторон у бутылки Клейна?

8.3. При скольких замкнутых разрезах бутылка Клейна не распадается на две части?

8.4. Сколько требуется замкнутых разрезов, чтобы сделать из бутылки Клейна квадрат?

8.5. Сколько требуется замкнутых разрезов, чтобы сделать из бутылки Клейна кольцо?

1. Склейте достаточно широкий и длинный лист Мёбиуса.

2. Проведите точно по середине листа Мёбиуса замкнутую красную линию.

Ответьте на вопрос: по какому количеству «сторон» прошла эта линия? Этот опыт убеждает, что у листа Мёбиуса одна сторона.

Проведите между красной линией на середине листа Мёбиуса и его краем замкнутую синюю линию. Ответьте на вопрос: вдоль какого количества «краев» прошла эта линия? Этот опыт убеждает, что у листа Мёбиуса один край.

3. Выполните предыдущие два упражнения три раза.

Первый лист Мёбиуса с красной и синей линиями разрежьте вдоль по всей красной линии. Ответьте на вопрос: на какое количество лент распался лист Мёбиуса после полного разреза и сколько раз эти ленты перекручены?

Этот опыт убеждает, что у листа Мёбиуса одна сторона.

Второй лист Мёбиуса с красной и синей линиями разрежьте вдоль по всей синей линии. Ответьте на вопрос: на какое количество лент распался лист Мёбиуса после полного разреза и на скольких лентах имеется синяя линия? Этот опыт убеждает, что у листа Мёбиуса один край.

Третий лист Мёбиуса с красной и синей линиями разрежьте сначала вдоль по всей красной линии, а затем вдоль по всей синей линии. Ответьте на вопрос:

на какое количество лент распался лист Мёбиуса?

доктор кукольных наук синьор Карабас Буратино.— Так это ты помешал представлению моей прекрасной комедии?

Он схватил Буратино, отнес в кладовую театра и повесил на гвоздь. Вернувшись, погрозил куклам семихвостой плеткой, чтобы они продолжали представление.

Приложение.

2500 случайных чисел Практикум по Интернет-экзамену 1. Заданы множества A = {2, 4, 6} и B = {2, 4, 6, 8}. Верным для них будет утверждение… 1) Множества A и B равны.

2) Множество B есть подмножество множества A.

3) Множество A есть подмножество множества B.

4) Множества A и B не содержат одинаковых элементов.

Решение. Изучим состав множеств. Все элементы множества A являются также и элементами множества B, но не наоборот. Поэтому множество A есть подмножество множества B.

2. Задано множество {2, {4, 6}, 4, 6, 8}. Истинными высказываниями являются… Множество {4, 6} является подмножеством множества {2, {4, 6}, 4, 6, 8}.

Множество {4, 6} является элементом множества {2, {4, 6}, 4, 6, 8}.

Множество {2, {4, 6}, 4, 6, 8} состоит из 6 элементов.

Множество {2, {4, 6}, 4, 6, 8} состоит из 5 элементов.

Множество {2, {4, 6}, 4, 6, 8} пустое.

Множество {2, {4, 6}, 4, 6, 8} не пустое.

Множество {4} является подмножеством множества {2, {4, 6}, 4, 6, 8}.

Множество {4} является элементом множества {2, {4, 6}, 4, 6, 8}.

Множество {2, {4, 6}} является подмножеством множества {2, {4, 6}, 4, 6, 8}.

Множество {2, {4, 6}} является элементом множества {2, {4, 6}, 4, 6, 8}.

Множество {{4, 6}} является подмножеством множества {2, {4, 6}, 4, 6, 8}.

Множество {{4, 6}} является элементом множества {2, {4, 6}, 4, 6, 8}.

Решение. Изучим состав множества. Заданное множество {2, {4, 6}, 4, 6, 8} имеет ровно 5 элементов 2, {4, 6}, 4, 6, 8, из которых 4 числа 2, 4, 6, 8 и 1 множество {4, 6}. Поэтому истинными высказываниями являются:

Множество {4, 6} является элементом множества {2, {4, 6}, 4, 6, 8}.

Множество {2, {4, 6}, 4, 6, 8} состоит из 5 элементов.

Множество {2, {4, 6}, 4, 6, 8} не пустое.

Множество {4} является подмножеством множества {2, {4, 6}, 4, 6, 8}.

Множество {2, {4, 6}} является подмножеством множества {2, {4, 6}, 4, 6, 8}.