Определение 2.16. Деревом называется связный граф, не содержащий циклов.

Трехмерной моделью графа-дерева служит, например, настоящее дерево с его

замысловато разветвленной кроной; река и ее притоки также образуют дерево, но

уже плоское – на поверхности земли (рис.2.12).

(РИСУНОК 2.12)

Определение 2.17. Несвязный граф, состоящий исключительно из деревьев,

называется лесом.

Пример: на рисунке 2.13 изображен лес, состоящий из трех деревьев.

(РИСУНОК 2.13)

Определение 2.13. Дерево, все n вершин которого имеют номера от

1 до n, называют деревом с перенумерованными вершинами.

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

невозможно доказательство теорем, а, следовательно и решение задач.

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

параграфе объяснены базовые понятия теории.

§3. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ.

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

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

задач.

Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу

его ребер.

Доказательство. Пусть А1, А2, А

3, ..., An — вер­шины данного графа, a p(A1

), р(А2), ..., p(An) – степени этих вершин.

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

Это рав­носильно нахождению суммы степеней всех вершин. При таком подсчете

каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A1)+р(А2)+ ... +p(A

n)=0,5N, или 2(p(A1)+р(А2)+

... +p(An))=N , где N — число ребер. ‡

Теорема 3.2. Число нечетных вершин любого графа четно.

Доказательство. Пусть a1, a2, a3, .,

ak — это сте­пени четных вершин графа, а b1, b

2, b3, ., bm — степени нечетных вершин графа.

Сумма a1+a2+a3+.+ak+b1

+b2+b3+.+bm ровно в два раза превышает

число ребер гра­фа. Сумма a1+a2+a3+.+a

k четная (как сумма четных чисел), тогда сумма b1

+b2+b3+.+bm должна быть четной. Это

возможно лишь в том случае, если m — четное, то есть четным является и

число нечетных вершин графа. Что и требовалось доказать. ‡

Эта теорема имеет немало любопытных следствий.

Следствие 1. Нечетное число знакомых в любой компании всег­да четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное

число ребер, четно.

Следствие 3. Число всех людей, когда-либо пожавших руку дру­гим людям,

нечетное число раз, является четным.

Теорема 3.3. Во всяком графе с n вершинами, где n больше

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

Доказательство. Если граф имеет n вершин, то каждая из них может

иметь степень 0, 1, 2, ..., (n-1). Предположим, что в некотором

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

этого быть не может. Действительно, если р(А)=0, то это значит,

что А — изолированная вершина, и поэтому в графе не найдется вершины

Х со степенью р(Х)=n-1. В са­мом деле, эта вершина

должна быть соединена с (n-1) вершиной, в том числе и с А, но

ведь А оказалась изолированной. Следовательно, в графе, имеющем n

вершин, не мо­гут быть одновременно вершины степени 0 и (n-1). Это

значит, что из n вершин найдутся две, имеющие одинаковые степени.

‡

Теорема 3.4. Если в графе с n вершинами (n больше или

равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда

найдется либо единственная изолированная вершина, либо единственная вершина,

соединенная со всеми другими.

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

пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа,

состоящая из n школьников, обменивается фотографиями. В некоторый

момент времени выяс­няется, что двое совершили одинаковое число обме­нов.

Доказать, что среди школьников есть либо один еще не начинавший обмена, либо

один уже завершив­ший его.

Теорема 3.5. Если у графа все простые циклы четной длины, то он не

содержит ни одного цикла четной длины.

Рисунок 3.1 поясняет условие теоремы. На изображенном графе все 5 простых

циклов четные.

(РИСУНОК 3.1)

Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так

и непростой) нечетной длины, то есть содержащий нечетное число ребер.

Теорема 3.6. Для того, чтобы граф был эйлеро­вым, необходимо и

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

Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь

АВ, содержащую все его ребра в точности по одному разу, необходимо и

достаточно, чтобы А и В были единственными нечет­ными вершинами

этого графа.

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

также следует счи­тать конструктивным (обратите внимание на то, как

•использована при этом теорема 3.6). Для доказательства к исходному графу

присоеди­няем ребро (А, В); после этого все вершины графа станут

четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в

нем можно про­ложить эйлеров цикл Ψ. И если теперь в этом цикле

удалить ребро (А, В), то останется искомая цепь АВ

. ‡

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

следует считать обоб­щением теоремы 3.7.

Теорема 3.8. Если данный граф является связ­ным и имеет 2k вершин

нечетной степени, то в нем можно провести k различных цепей, содержащих

все его ребра в совокупности ровно по одному разу.

Теорема 3.9. Различных деревьев с n перенумерованными вершинами

можно построить nn-2.

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема

известна, в основном, как вывод английского математика А. Кэли (1821—1895).

Графы-деревья издавна привлекали внимание ученых. Се­годня двоичные деревья

используются не только ма­тематиками, а и биологами, химиками, физиками и

инженерами (подробнее об этом – в параграфе 6).

Теорема 3.10. Полный граф с пятью верши­нами не является плоским.

Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2,

где В — число вершин плоского графа, Р — число его ре­бер, Г

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

ни один из многоугольников не лежит внутри другого. На рисунке 3.2, а изображен

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

внутри другого. Справа приведено изображение графа, к которому формула

применима.

(РИСУНОК 3.2)

Эту формулу можно доказать методом математиче­ской индукции. Это доказательство

мы опускаем. За­метим только, что формула справедлива и для пространственных

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

3.2). Замечаем, что на графе нет ни одной грани, ограниченной только двумя

ребрами. Если че­рез φ1 обозначить число таких граней,

то φ2=0. Далее рассуждаем от противного, а именно:

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

формула Эйлера. Число вершин в данном графе В=5, число ребер

Р=10, тогда число граней Г=2-В+Р=2-5+10=7.

Это число можно представить в виде суммы: Г=φ1+φ

2+φ3+., где φ3 – число

граней, ограниченных тремя ребрами, φ4 — число граней,

ограниченных че­тырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число

граней равно 2Р, в то же время 2Р=20=3φ3+4

φ4+... . Умножив равенство Г=7=φ

3+ φ4 + φ5 + . на три,

получим ЗГ=21=3( φ3 + φ4 + φ

5 + .).

Ясно, что (3φ3+3φ4+3φ

5+.) < (3φ3+4φ4+ 5

φ5+.) или 3Г<2Р, но по

условию, 2Р=20, а ЗГ=21; поэтому вывод, полученный при введенном

нами предположе­нии (граф плоский), противоречит условию. Отсюда заключаем, что

полный граф с пятью вершинами не является плоским. ‡

Теорема 3.11. (Теорема Понтрягина-Куратовского) Граф является плоским

тогда и только тогда, когда он не имеет в качестве подграфа полного графа с

пятью вершинами.

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

объяснялись только основные теоремы теории графов. Их практическое применение

будет рассмотрено в следующих параграфах реферата.

§4. ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.

В данном параграфе будут рассмотрены некоторые задачи, при решении которых

используется теория графов. Они считаются классическими.

Задача 4.1. Необходимо составить фрагмент расписания для одного дня с

учетом следующих обстоятельств:

1. учитель истории может дать либо первый, либо второй, либо третий

уроки, но только один урок;

2. учитель литературы может дать один, либо второй, либо третий урок;

3. математик готов дать либо только первый, либо только второй урок;

4. преподаватель физкультуры согласен дать только последний урок.

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

условиям одновременно, может составить завуч школы?

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

перебора всех возможных вариантов, но решение будет наиболее простым, если

вычертить граф в виде дерева. Требуемый граф изображен на рисунке 4.1. На нем

выделены три возможных варианта расписания уроков.

(РИСУНОК 4.1)

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

графов. В настоящее время существует программа "Расписание 3.0" компьютерной

фирмы ЛинTex, в которой она решена с использованием современных технологий.

Рассмотрим еще одну задачу, решением которой также является граф.

Задача 4.2. В составе экспедиции должно быть 6 специалистов: биолог,

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

нужно выбрать участников экспедиции; условные имена претендентов: A,

B, C, D, E, F, G и H.

Обязанности биолога могут исполнять E и G, врача – A и

D, синоптика – F и G, гидролога – B и F,

радиста – С и D, механика – C и H.

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

обязанность. Кого и в какой должности следует включить в состав экспедицию,

если F не может ехать без B, D – без H

и C, C не может ехать вместе с G, A – вместе с B

?

Решение. Процесс решения задачи во всех подробностях мы рассматривать не

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

точный состав экспедиции, можно с помощью четного графа, в котором вершины

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

Применительно к задаче об экспедиции одна группа вершин есть группа из 8

кандидатов, а вторая – из 6 должностей. Решение задачи изображено на четном

графе (рис 4.2).

(РИСУНОК 4.2)

Задача 4.3. Планета имеет форму выпуклого многогранника, причем в его

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

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

по оставшимся дорогам.

Решение. Пусть A и B – данные города. Докажем сначала,

что из A в B можно было проехать до закрытия на ремонт двух

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

перпендикулярную ни одному из его ребер (при такой проекции вершины

многогранника не сливаются).

Пусть A' и B' – проекции точек A и B, а

M' и N' – крайние точки проекции многогранника (в точки

M' и N' проецируются вершины M и N). Если

идти из вершины A так, что в проекции движение будет происходить по

направлению от M' к N' , то, в конце концов, мы обязательно

попадем в вершину N. Аналогично из вершины B можно пройти в

N. Таким образом, можно проехать из A в B (через N).

Если полученный путь из A и B проходит через закрытую дорогу, то

есть еще два объезда по граням, для которых это ребро является общим. Вторая

закрытая дорога не может находиться сразу на двух этих объездах. Значит, из

города A в город B можно проехать, по крайней мере, одним

путем.

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

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

курса математики.

§5. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ

КУРСЕ МАТЕМАТИКИ.

В соответствии с вышесказанным, в данном параграфе будут рассмотрены задачи,

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

Условно их можно классифицировать, подразделив на несколько групп:

1. Задачи о мостах.

2. Логические задачи

3. Задачи о "правильном" раскрашивании карт

4. Задачи на построение уникурсальных графов

5.

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

Одной из наиболее известных задач о мостах является эйлерова задача; все

остальные сформулированы похожим образом и решаются по тому же принципу.

Поэтому в данном параграфе мы не будем подробно останавливаться разборе этого

типа задач.

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

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

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

рассмотрения соответствующих графов.

Задача 5.1. Из трех человек, стоящих рядом, один всегда говорит правду

(правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам,

говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто

стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали

вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа

спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

Решение: Если в данной задаче ребро графа будет соответствовать месту,

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

возможности (рис 5.1).

(РИСУНОК 5.1)

Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним,

судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец".

Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев

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

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

"правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что

выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно,

лжет (что возможно из условия), а стоящий справа также лжет. Таким образом,

все условия задачи выполнены.

Задача 5.2. В обеденный перерыв члены строительной бригады разговорились

о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две

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

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

Сколько человек в бригаде?

Решение: Решение этой задачи достигается построением следующего графа

(рис 5.2), где каждая вершина обозначает соответствующую газету и

соответственно 5 подписчиков, а каждое ребро будет соответствовать одному

подписчику.

(РИСУНОК 5.2)

Иными словами, суть метода решения этой и подобных ей задач состоит в

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

Любая географическая карта является многоугольным графом, в котором страны

будут гранями, границы – ребрами, а окружающий страны Мировой океан –

бесконечной гранью.

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

были раскрашены в разные цвета. Такую карту называют "правильно"

раскрашенной.

Широко известное предположение состоит в том, что каждая карта может быть

раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому

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

будем останавливаться на его рассмотрении.

Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от

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

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

имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по

одному разу, необходимо и достаточно, чтобы АА и ВВ были единственными

нечетными вершинами, т. е. вершинами с нечетной степенью.

§6. ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ

ОБЛАСТЯХ НАУКИ И ТЕХНИКИ.

Графы и информация

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

что определенное число сообщений требуется закодировать в виде конечных

последовательностей различной длины, состоящих из нулей и единиц. Если

вероятности кодовых слов заданы, то наилучшим считается код, в котором

средняя длина слов минимальна по сравнению с прочими распределениями

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

алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска.

Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо

"да", либо "нет". Утвердительному и отрицательному ответу соответствуют два

ребра, выходящие из вершины. "Опрос" завершается, когда удается установить

то, что требовалось.

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

ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на

предыдущий вопрос, то план такого интервью можно представить в виде двоичного

дерева.

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или

предельных) углеводородов, молекулы которых задаются формулой:

CnH2n+2

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны.

Структурные формулы простейших углеводородов показаны на рисунке 6.1 (а – метан

CH4, б – этан C2H6).

(РИСУНОК 6.1)

Молекула каждого предельного углеводорода представляет собой дерево. Если

удалить все атомы водорода, то оставшиеся атомы углеводорода также будут

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

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

число гомологов данного вещества, равно числу деревьев с вершинами степени не

больше четырех.

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

приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее

обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для

простоты мы рассмотрим только одну разновидность ветвящихся процессов –

размножение бактерий. Предположим, что через определенный промежуток времени

каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства

одной бактерии мы получим двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n-е

поколение одной бактерии насчитывает ровно k потомков? Рекуррентное

соотношение, обозначающее число необходимых случаев, известно в биологии под

названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай

многих общих формул.

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей

было конструирование печатных схем.

Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего

материала), на которой в виде металлических полосок вытравлены дорожки.

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

необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в

других местах вызовет замыкание электрической цепи.

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

указанных точках.

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

теории графов, доказательство которой и являлось целью данного параграфа.

СПИСОК ИСПОЛЬЗОВАННОЙ И РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ:

1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

2. Касаткин В. Н. "Необычные задачи математики", Киев, "Радяньска школа"

1987(часть 2);

3. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

4. "В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение

элементов теории графов");

5. Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные

занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;

7. Оре О. "Графы и их применения", М. "Мир", 1965;

8. Зыков А. А. "Теория конечных графов", Новосибирск, "Наука", 1969;

9. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

10. Реньи А., "Трилогия о математике", М., "Мир", 1980.

Страницы: 1, 2