Теория и практика математических графов

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

Часто по самым разным поводам мы чертим фигуру, состоящую из точек изображающих какие-то объекты, соединяя эти точки линиями, если соответствующие объекты находятся друг к другу в каких-то отношениях.

Предположим, что вы пригласили к себе в гости нескольких друзей, назовём их A,B,C,D,E,F. Одни из них - ваши родственники, другие - друзья по работе, третьи - живут с вами в одном доме, с четвёртыми - вы отдыхаете летом и т. д. Поэтому некоторые из них не знакомы друг с другом. Пытаясь вспомнить, кто из них с кем знаком. Вы, возможно, изобразите на бумаге шесть точек A,B,C,D,E,F, соединяя эти точки линиями, если соответствующие лица знакомы друг с другом. При этом у вас получится граф – фигура, состоящая из нескольких точек, называемых вершинами, и соединяющих их линий, называемых ребрами- [AC], [BF],[EC] и другие.

Определение графа можно ввести по-другому

Граф-это конечное множество точек и соединяющих их кривых на плоскости.

Но вёрнёмся к примеру с гостями с гостями: соединив точки A,B,C,D,E,F мы получим граф изображенный на чертеже 1.

Конечно, в этом случае неважно, как точки A,B,C,D,E,F расположены на плоскости и какими линиями они соединены. Эту же самую ситуацию и с тем же успехом передаёт граф изображённый на черт. 2.

Такие графы не считаются различными. Математики называют их изоморфными (гр. isos равный + morphe форма -сходный по форме). Изоморфные графы - это графы одно и то же число вершин, которое обозначить попарно одинаковыми буквами так, что если две вершины одного графа соединены ребром, одноимённые вершины другого графа то же соединены между собой ребром.

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

В другом крайнем случае, когда ни один из ваших друзей не знаком ни с одним из остальных- граф будет составлять из одних изолированных вершин, не соединённых между собой ребрами. Такой граф называется - нульграфом (черт. 4). Нульграф это граф, состоящий только из изолированных вершин: граф не имеющий рёбер. Число компонент нульграфа равно числу его вершин. Но это два крайних случая. В промежуточных случаях одни пары вершин будут соединены между собой рёбрам, другие- нет.

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

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

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

Число ребер p(A), встречающихся в вершине А графа, называются степенью этой вершины. Степень каждой n вершины полного графа равна n-1; степень каждой вершины нульграфа равна нулю.

Вершины, степени которых четны, называются чётными вершинами. Вершины не чётных степеней, не чётными вершинами.

Если степени всех вершин графа одинаковы и равны двум, граф называется однородным степени чётности. Так, полный граф, имеющий n вершин, будет однородным графом степени n-1. нуль граф является однородным графом нулевой степени.

Довольно часто приходится находить число рёбер графа с вершинами А1,А2,А3Аn, степени которых соответственно равны p(A1), p(A2), p(A3) p(An). Сосчитаем число рёбер в каждой из его вершин и все полученные числа сложим p(A1), + p(A2), +p(A3) ++p(An). Сумма будет равна удвоенному числу рёбер графа, так как каждое ребро при этом будет сосчитано дважды - по разу в каждом из его концов. Следовательно, общее число рёбер графа будет равно

N= ½ [p(A1)+p(A2)+p(An)].

Отсюда следует, что сумма (1) степеней всех вершин графа:∑ p(A1)= p(A1)+p(A2)+p(A3)++p(An), является числом четным, так как она равна удвоенному числу рёбер, а значит, число нечётных вершин любого графа чётно. Это утверждение верно и в случае, когда граф вовсе не содержит нечётных вершин, так как 0 является числом четным. Бывают графы, у которых степени всех вершин одинаковы

P(A1)=p(A2)=p(A3)==p(An)= четные. уже говорилось, что такой граф называется однородным. В силу формулы (2) число его рёбер равно N=1/2 n ч, где число n- число вершин данного графа. Можно рассматривать и такие графы, число вершин и рёбер которых бесконечно - бесконечные графы.

Графы с конечным числом вершин и рёбер называются конечными графами.

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

Цикл – это конечная, замкнутая цепь, начинающаяся в некоторой вершине Х и оканчивающаяся в той же вершине Х; Цикл называется простым, если все его рёбра различны. Цикл называется составным в противном случае. И, наконец, цикл, непреходящий ни через одну из своих вершин, более одного раза, называется элементарным. Две вершины графа могут быть соединены несколькими рёбрами – черт. 8. а. В этом случае говорят, что граф имеет кратные рёбра. Вместо того, чтобы на самом деле проводить несколько рёбер между одними и теми же вершинами А и Д, можно провести всего одно ребро, приписав ему кратность - черт. 8. б-показывающую сколько раз надо считать это ребро.

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

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

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

Теория графов является одной из немногих областей математики, дата рождения которых может быть указана. Первая работа о графах, принадлежащая швейцарскому математику Леонарду Эйлеру (1707-1783), появилась в 1736 году в публикациях Петербургской Академии наук. Статья Эйлера была по поводу задачи о кенигсбергских мостах.

( Впрочем, сам термин «граф» был введён ровно 200 лет спустя, в монографии Кёнига). Задача состояла в следующем. Город Кенигсберг (ныне Калининград) расположен на берегах реки Прегель и двух её островах. Различные части города были соединены семью мостами. По воскресеньям горожане любили прогуливаться по берегам реки, её островам и мостам (черт 9).

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

Для решения этой задачи Эйлер построил граф, вершинами А,В,С,Д, которого были берега А и В и острова С и Д, а рёбрами соединяющие их мосты. Этот граф изображен на чертеже 10. Задача состоит в том, чтобы на этом графе найти цикл, проходящий по всем его рёбрам в точности по одному разу. Эйлер показал, что этот граф не представляет собой единого цикл, иными словами, с какой бы вершины вы не начали обход, мы не сможем обойти весь граф и вернуться, обратно, не проходя никакого ребра дважды. Если бы такой цикл существовал, то в каждой вершине графа было бы столько не входящих в неё рёбер, сколько и выходящих из неё, то есть вершин графа должны были быть чётными. Однако, как легко видеть, данное условие не имеет места для графа, представляющего карту Кенигсберга.

Изложив решение задачи о кенигсбергских мостах Эйлер в своей работе пришёл к следующей общей проблеме теории графов: на каких графах можно найти цикл 9, содержащий все рёбра графа, причем каждое ребро в точности по одному разу? Такой цикл мы будем называть эйлеровой линией, а граф, обладающий эйлеровой линией- эйлеровым графом. Из предыдущего ясно, что для этого необходимо, чтобы степени всех вершин графа должны быть чётными. Эйлер доказал: теорема (а): Связный граф, степени всех вершин которого чётны, обладает эйлеровой линией.

Предположим, что у нас имеется граф С, степени всех вершин которого чётны. Выберем какую-нибудь вершину А и из неё начнём наш путь по рёбрам графа, продвигаясь так далеко, насколько это возможно, проходя каждый раз по ребру ещё не пройденному ранее. Ввиду конечности рёбер этот процесс когда-нибудь закончится. Но так как в каждой вершине чётное количество ребер, то из каждой вершины за исключением начальной, то есть А, будет возможен и выход. Следовательно, такая цепь £ должна кончаться в вершине А (черт 11). И значит, она будет циклом.

Если £ проходит через все вершины графа, то мы уже получили требуемую эйлерову линию. Если это не так, найдётся вершина В, в которой ещё имеются не пройденные рёбра. Так как £ имеет в вершине В чётное число, то число рёбер, выходящих из В и не принадлежащих £, так же чётно; это верно и относительно всех других вершин. Теперь мы начнём новую цепь R из вершины, используя на этот раз только те, которые не принадлежат £. Ясно, что эта цепь должна оканчиваться в точке В. А тогда мы можем расширить первоначальный цикл, начинающийся в А: сначала следуем по £ от А к В, затем пройдем по циклу R и, вернувшись в В, пройдем оставшуюся часть £ и вернёмся снова в А. Если новый цикл содержит не все рёбра графа, его можно расширить точно таким же образом – и так до тех пор, пока мы не получим требуемую эйлерову линию. Ввиду конечности числа рёбер мы получим, в конце концов, цикл, проходящий в точности по одному разу по всем рёбрам графа.

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

До сих пор мы говорили о цикле, проходящем по всем рёбрам графа в точности по одному разу. Можно поставить задачу и об отыскании цепи, обладающей тем же свойством. Предположим, что на графе имеется цепь £(А, В), начинающаяся в вершине А и оканчивающаяся в некоторой другой вершине В и проходящая по всем рёбрам в точности по одному разу. Эта цепь, начинаясь в вершине А, возможно, в дальнейшем снова заходит в А, и даже не один раз. Если эта цепь не оканчивается в А, то вершина А должна быть не чётной. По аналогичной причине нечётной будет и вершина В, в то время, как все остальные вершины графа чётны. Это приводит нас к следующему утверждению: теорема (в). Для того, чтобы на связном графе имелась цепь £(А, В), содержащая все его рёбра по одному разу, необходимо и достаточно, чтобы А и В были единственными нечётными вершинами этого графа.

Для доказательства достаточно прибавить к графу новое ребро АВ, тогда все его вершины станут чётными. Новый граф, согласно предыдущей теореме(а) обладает некоторой эйлеровой линией Р ; если ребро АВ удалить из Р, останется искомая цепь £ (А,В). В качестве примера можно указать цепь FCDBAEC графа, изображённого на черт. 12. этот граф имеет в точности две нечётные вершины F и С. Впрочем , попытаемся доказать более общую теорему: определим для произвольного графа наименьшее число цепей, таких, что никакие из них не имеют общих рёбер и все они вместе покрывают граф. Ясно, что если на графе имеется такое семейство цепей, то каждая нечётная вершина должна быть либо начальной, либо конечной точкой, по крайней мере, одной из них, иначе эта вершина была бы нечётной. Но мы знаем, что число нечётных вершин графа четно, пусть оно равно k 2.

Зададимся вопросом об отыскании наименьшего числа цепей, содержащих в совокупности все рёбра графа в точности по одному разу. Так как каждая нечётная вершина графа будет либо началом, либо концом одной из таких цепей, ясно. Что число их не меньше k. Покажем, что верно и обратное, всегда найдутся k цепей, в совокупности покрывающих весь граф, (по – другому можно сказать так, на любом связном графе с 2k нечётными вершинами имеется семейство k цепей, которые в совокупности содержат все рёбра графа в точности по одному разу).

Пусть нечётные вершина графа будут А1,А2,А3А2k(1)

Если мы добавим к нашему графу k рёбер

A1; A2; А 3А4;А 2k-1A 2k (2)

То все его вершины будут чётными и, следовательно, найдётся цикл, содержащий все его рёбра в точности по одному разу – эйлерова линия Р. Если из этого цикла удалить k добавленных рёбер(2), то он распадется на k цепей в совокупности покрывающих весь первоначальный граф.

В качестве примера можно привести граф, изображенный на черт. 13. Этот граф имеет нечётное число вершин АВДЕ и покрываются двумя цепями EFBA и BCADFED. Задача об отыскании на графе цикла, содержащего все его рёбра по одному разу, допускает, как мы видим, исчерпывающее решение. Существует родственная задача об отыскании цикла, содержащего в точности по одному разу все вершины графа – такая линия называется Гамильтоновой линией. Имеется аналогия между эйлеровыми и гамильтоновыми линиями. Первая – проходит один раз по каждому ребру. Вторая – через каждую вершину.

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

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

Плоский граф – это такой граф, который можно начертить на плоскости так, чтобы его рёбра пересекались только в его вершинах.

Один и тот же граф можно изобразить на плоскости по – разному. Графы а) и б) на черт. 15. не считаются различными, они изоморфны, так как «несут» одну и туже информацию. Тем не менее, в этих их изображениях на плоскости есть одно существенное различие: рёбра первого графа пересекаются только в его вершинах, на втором же имеется точка пересечения рёбер, не являющаяся его вершиной. На самом деле, эта точка принадлежит только данному представления графа, к самому графу она не имеет ни какого отношения: рёбра графа нужно представить себе, как проходящие друг над другом тонкие нити.

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

Примером плоского графа может служить любой многоугольный граф, образованный прилегающими друг к другу криволинейными многоугольниками, то есть многоугольниками, стороны которых не обязательно прямолинейные отрезки, но какие угодно непрерывные линии без самопересечений. Примером многоугольного графа, может служить граф, изображенный на черт. 16. Каждый криволинейный многоугольник этого графа, и подобных ему, не содержащих внутри себя никаких вершин и рёбер граф, называется гранью графа. Внешнюю по отношению к графу бесконечную область удобно так же считать одной из его граней (мы будем называть её бесконечной гранью). Хорошим примером такого многоугольного графа служит карта США, разделённая на штаты, а так же любая другая географическая карта с границами между странами. Границы являются рёбрами графа, а страны – многоугольниками.

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

Предположим, что на некоторые рёбра мы поставим новые вершины, так, что эти рёбра элементарными цепями, состоящими из нескольких рёбер. Эту операцию мы назовем расширением графа. На черт. 17, приведем пример расширения, переводящего граф а), содержащего всего четыре вершины в граф, изображенный на черт 17 б. Предположим обратное. Мы имеем такой граф, как граф, изображенный на черт 17 (б), содержащий элементарные цепи, разделённые на рёбра, причём из промежуточных вершин не исходит никаких других рёбер. Посредством обратной он может быть сжат в такой граф, на котором его элементарные цепи становятся рёбрами. Так граф, изображенный на черт. 17б, может быть сжат в граф, изображенный на черт. 17а путем удаления из соответствующих элементарных цепей, разделяющих их вершины. Теперь мы можем сформулировать теорему Куратовского. Теорема(в): Для того, чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал внутри себя никакого графа, который можно было бы сжать до пятиугольного графа(черт 18) или шестиугольного графа (черт. 19).

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

(многоугольный граф – плоский граф, рёбра которого образуют множество смежных, не налегающих друг на друга многоугольников). Необходимо, кроме того, чтобы ни один многоугольник не лежал внутри другого. Граничные рёбра каждого такого многоугольного графа образуют цикл, называемый минимальным циклом. Часть плоскости, заключённая внутри такого многоугольного графа называется гранью графа. На таком графе, имеется ещё и максимальный цикл – цикл, окружающий весь граф со всеми его гранями. В математике обычно руководствуются превосходнейшим принципом, состоящим во введение таких соглашений, чтобы все формулы становились более простыми.

Так, в нашем случае выгодно рассматривать часть плоскости, лежащую вне максимального цикла – бесконечную грань. Проиллюстрируем, что нет никакой разницы между бесконечной гранью и любой из остальных, на черт. 20. Это граф с гранями, занумерованными числами от. Грань имеет в качестве границы цикл, состоящий из рёбер и. А грань ограничена только двумя рёбрами, соединяющими вершины 10 и 12. Рёбра максимального цикла проходят по всем вершинам от 1 до 10 по порядку, а затем возвращаются к 1. Бесконечная грань представляет собой совокупность всех точек, лежащих вне максимального цикла.

Для пространственных многогранников существует одно интересное соотношение, впервые доказанное Эйлером и известное под названием формулы Эйлера для многогранников. Она справедлива и для наших многоугольных графов. Обозначим через n, e, s соответственно число вершин ( n), рёбер (e) и граней (s) графа G. Теорема Эйлера утверждает, что всегда верно равенство

N – e + s =2

Докажем это: минимальное число граней графа равно 2, такой граф представляет собой один криволинейный многоугольник (вторая его грань – бесконечная внешняя область). Если число вершин этого многоугольника равно n, то и числа его рёбер тоже равно n, и n-n+2=2. Теорема Эйлера в этом случае справедлива. Но каждый многоугольный граф можно получить последовательным расширением простейшего многоугольного графа, присоединяя к нему каждый раз по одному многоугольнику. При этом s увеличивается на единицу: для нового графа s=s+1 и если присоединяемый многоугольник имеет m вершин, то число вершин графа увеличивается на m-2: n=n+(m-2), а число рёбер – на m-1: e=e+(m-1), и для нового графа. Так на чертеже 21,

N =19 E=23 S=6 и n-e +s=19-23+6=2.

Для этого более общего случая терему Эйлера можно доказать методом математической индукции по числу рёбер или по числу вершин. Её можно доказать совсем просто, если ввести понятие цикломатического числа. Цикломатическое число графа G минус число его вершин плюс ў =e-n+1

Ў – цикломатическое число.

Если плоский граф имеет s граней и, значит, s-1, конечных граней. Его цикломатическое число ў =s-1, но ў=e-n+1 из равенства e-n+1=s-1, вытекает, что n-e+s=2. Покажем, что теорема Эйлера справедлива, как мы говорили, для многогранников. Для параллелепипеда n=8 – вершин, e=12 – рёбер, s=6 – граней, и n-e+s=8-12+6=2. Рассмотрим произвольный многоугольный граф. Пусть число его двуугольных граней равно а2, число треугольных граней – а3, число четырёхугольных граней – а4 и так далее. (Число сторон бесконечной грани – это число рёбер наибольшего охватывающего граф контура). Так, на чертеже 16 бесконечная грань является девятиугольником. Тогда очевидно, что а2+а3+а4+=s (1)

2а2+3а3+4а4+=2s (2), так как каждое рёбро принадлежит одновременно двум граням.

Мы воспользуемся равенством (1) и (2) и докажем, что: полный граф с пятью вершинами не является плоским.

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

E=5*4=10

2 и по теореме Эйлера число его граней было бы равно 7. Так как двуугольных граней у него нет ( каждые 2 вершины соединены единственным ребром ), то а2=0 и, следовательно S=7=a3+a4+a5+

2e=20=3a3+4a4+5a5+

Умножая первое равенство на 3 получим 21=3а3+3а4+3а5+ Но эта сумма должна быть меньше предыдущей, равной 20. Полученное противоречие доказывает несправедливость нашего предположения. Значит, полный граф с пятью вершинами не является плоским. Это видно и из чертежа 22. Ещё один не плоский граф получается в известной задаче о трех домах и трёх колодцах. Задача состоит в следующем. Имеется три дома А,В,С и три колодца X,Y,Z. Так как колодцы иногда пересекаются, то требуется провести от всех трех домов дорожки ко всем трем колодцам (черт. 23). Можно ли это сделать так, чтобы дорожки не пересекались? Если бы это было возможным, мы опять получили бы плоский граф, у которого n=6 e=3*3=9 s=5 и по теореме Эйлера. Этот граф не имеет двуугольных граней, а2=0 и треугольных граней, так как 2 дома и 2 колодца не соединяются между собой и, значит, а3=0. Имеем: s=5=а4+а5+а6+

2e=18 4а4+5а5+6а6+

Умножая, обе части первого равенства на 4 получим:

20=4а4+4а5+4а6+

Но эта сумма должна быть меньше предыдущей, равной 18. Значит, провести непересекающиеся дорожки от 3 домов к 3 колодцам невозможно.

Эти два неплоских графа – черт. 22, черт. 23 – интересны тем, что к ним в некоторой мере сводятся все остальные неплоские графы – в каждом неплоском графе можно найти неполный граф с 5или 6 вершинами. Это утверждение и составляет содержание теоремы Куратовского.

Мозаики

Если посмотреть на пол в ванной комнате, можно увидеть узор из повторяющихся правильных многоугольников. Форма этих многоугольников может быть разной. Они могут быть квадратами, или шестиугольниками – черт. 24. Такие узоры для мозаичных полов были распространены ещё в глубокой древности. В природе можно найти много примеров таких повторяющихся узоров со сходными или даже одинаковыми ячейками. В ботанике они встречаются при изучение расположения листьев, почек и семян у растений. Можно заметить правильность в расположение семян подсолнечника.

С точки зрения теории графов подобная мозаика – это плоский граф. Все грани, которого имеют одно и то же число рёбер и повторяются большое число раз.

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

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

Мы получим тогда многоугольный граф G, в котором все грани, за исключением бесконечно, ограничены р А рёбрами и в каждой вершине которого за исключением тех, которые лежат на границе грани.

Предположим, что мы кладём эту мозаику таким образом, что когда число кусков возрастает, отношение числа в, вершин, лежащих на границе, к общему числу вершин в становится всё меньше и меньше. В терминах теории пределов это можно записать так: в1/в – 0 , если в1 – n

Оценим число рёбер графа G, подсчитывая их отдельно в каждой вершине, пользуясь формулой 2р=р(А1)+р(А2)++р(А6)

Если бы в каждой вершине графа сходилось в точности р рёбер, то общее число рёбер было бы равно 1/2рв. Если не будем считать рёбра в граничных вершинах, получим р/2(в-в1) рёбер. Следовательно, рв-рв1,< 2р<рв, где р- число рёбер графа G. Эти неравенства можно переписать в виде р/2-р/2в1/в

Из выражения в1/в – 0, если в – n заключаем, что р/в – р/2, если в – n. Сосчитаем теперь число рёбер графа по формуле

2р=2&2+3&3+4&4+ Имеется г – 1 граней с р* граничными рёбрами и грань £n число граничных ребер которой равно в1, граничных вершин графа. Следовательно, 2р=(г-1)р*+в1

Разделив обе части этого равенства на вр*, мы представим его в виде г/в=2р/р*в+1/в-в1/р*в;

Если в – n, то оба последних члена в правой части стремятся к нулю г/в – 2/р*р/2=р/р* , если в – n. Вернемся к формуле Эйлера, которую запишем следующим образом: 1+г/в=р/в+2/в. При возрастании в левая часть стремится к 1+р/р*, в то время, как правая часть стремится к р/2. Так как обе части должны иметь один и тот же предел, то 1+р/р*=р/2, следует, (р-2)(р*-2)=4. Этому уравнению удовлетворяют только следующие пары целых чисел

Р=3 р=4 р=6 р*=6 р*=4 р*=3 следовательно. Все повторяющиеся плоские графы узоров или мозаик, должны быть образованны либо треугольниками, либо четырёхугольниками, либо шестиугольниками. Все эти случаи представлены на черт. 24.

Графы помогают решать логические задач

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

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

На помощь могут прийти графы. Выделяя из словесных рассуждений главное – объекты и отношения между ними, графы представляют изучаемые факты в наглядной форме. Приёмы решения задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, во многих случаях сокращают нагрузку на память. С одной стороны, графы помогают проследить все логические возможности, изучаемой ситуации, с другой, благодаря своей обозримости, помогают тут же, в ходе решения задачи, классифицировать логические возможности, отбрасывать неподходящие случаи, не доходя до полного перебора всех случаев. Рассмотрим примеры использования графов при решении некоторых задач.

Задача 1 : Четыре ученицы: Мария, Нина, Ольга, Поля участвовали в лыжных соревнованиях и заняли четыре первых места. На вопрос, кто какое место занял, они дали три разных ответа: 1. Ольга заняла первое место, Нина второе

2. Ольга – второе, Поля – третье.

3. Мария – второе, Поля четвертое.

Отвечавшие при этом признали, что одна часть каждого ответа верна, а другая – неверна. Какое место заняла каждая из участниц.

Решение: будем исходить из двух единственно возможных предположений. 1. первое место заняла Ольга (0)

2. первое место заняла не Ольга (0)

Двумя рёбрами изобразим эти возможности. Рассмотрим первую возможность (первое место заняла Ольга ). По первому ответу. Ольга заняла первое место. Тогда Нина заняла второе место – неверно. Присоединим к ребру 0 второе ребро Н. По второму ответу. Ольга не могла занять второе место, так как она заняла первое место, следовательно, первая часть ответа ложна. Значит, Поля заняла третье место. Присоединим к ребру 0Н третье ребро П. По третьему ответу. Мария заняла второе место, так как Поля четвертое место не могла занять – она заняла третье место. Следует, что четвертое место заняла Нина и последнее ребро Н. Если же сходить из предположения, что первое место заняла не Ольга, то По первому ответу. Второе место заняла Нина. Присоединим к ребру 0 второе ребро Н. по второму ответу. Третье место заняла Поля, так как Ольга второе место уже не могла занять. По третьему ответу. Обе части его оказываются не верными, второе место заняла не Мария, а Нина; Поля заняла третье место, а не четвертое. Делаем вывод. Второе исходное положение( первое место заняла не Ольга) следует отбросить. Поэтому первое исходное предположение – верно. Получаем ответ:

1 место заняла Ольга;

2 место заняла Мария;

3 место заняла Поля;

4 место заняла Нина.

Этот ответ можно изобразить с помощью графа.

Задача 2. Три ученицы – Аня, Варя, Клава – на первомайской демонстрации были: одна в красном, другая в белом, третья в синим платье. В высказывании: Аня была в красном платье, Варя не в красном, Клава не в синем – одна часть верна, а две других неверны. В каком платье была каждая из учениц.

Решение. Будем исходить из двух возможностей: Аня была в красном платье (Ак) и Аня была не в красном (то есть белом или синим – Аб, Ас). Изобразим эти возможности: первую ребром Ак, а вторую – двумя рёбрами Ас и Аб ( исходящими из одной точки).

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

2 возможность: К ребру Ас присоединим 2 ребра Вк и Кб, так как в красном платье в этом случае могла быть Варя или Клава. Такие же 2 ребра присоединяем к Аб. Закончить каждый из получившихся путей очень просто: нужно присоединить последовательно рёбра Кб, Вб, Кс и Вс. Имеем 4 логические возможности, но условию задачи удовлетворяет лишь путь АсВкКб, а остальные три пути не удовлетворяют. Значит, ответ задачи: Аня была в синем платье,

Варя в красном,

Клава в белом платье.

Задача 3. Ученики А, В, С, Д, и Е участвовали в математическом конкурсе. Знающий этих учеников учитель истории предсказал, что получится последовательность А, В, С, Д, Е( А – займёт первое место, В – вторе, С – третье и так далее). А занимающийся с этими учениками учитель математике предполагал, что последовательность будет такой Д, А, Е, С, В. Когда конкурс прошёл, то оказалось, что учитель истории не указал верно места ни одного из участников и никакой пары следующих друг за другом учеников. Учитель же математики угадал места двух учеников, а так же две пары непосредственно следующих друг за другом учеников. Каким был на самом деле результат конкурса?

Решение: для решения этой задачи с помощью графов следует построить 4 графа по первому условию. Строить их нужно опираясь на то, что ни в одном из этих графов рёбра А, В, С, Д, Е не могут быть соответственно первым, вторым, третьим, четвертым и пятым, а кроме того, за ребром А не может следовать ребро В, за В – С, за С – Д и за Д – Е. Вот каким будет граф, начинающийся ребром Е. Полных путей в нем 4, а остальные (неполные) можно не принимать в расчет. После построения всех четырёх графов из получившихся полных путей нужно выделить те, которые удовлетворяют втором условию. Такой путь лишь один ЕДАСВ. Значит, участники конкурса заняли следующие места: Е – 1 место,

Д – 2 место,

А – 3 место,

С – 4 место,

В – 5 место.

Задача 4. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Решение: Построим граф отношения, заданного в условии задачи. Для этого, прежде всего выделим множество фамилий М и множество цветов волос К, элементы которых будут обозначаться точками. Точки множества М назовём Б, Ч, Р ( Белокуров, Чернов, Рыжов). Точки второго множества К – б, бр, р( белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы соединим их сплошной линией, а если не соответствует – штриховой. Условия задачи указывают лишь на несоответствия, поэтому в начале должен возникнуть граф, изображенный на черт. 25(а). Из условия следует, что для каждой точки множества М существует одна и только одна точка из множества К и, наоборот, каждой точке из множества К существует соответственно одна и только одна точка из множества М. Задача сводиться к тому, чтобы найти это единственно возможное соответствие между элементами множеством М и К, то есть к нахождению трех сплошных линий, соединяющих соответствующие точки множеств. Принцип решения задачи прост. Если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой её необходимо соединить сплошной линией. Поэтому граф на черт 25(а) дополняется сплошными линиями, соединяющими точки Б и р, Р и бр (черт. 25,б). Далее остаётся соединить сплошной линией точку Ч с б, так как точка р уже занята (черт. 25,в). Таким образом, на графе черт. 25,в, читаем ответ: Белокуров – рыжий,

Чернов – белокурый,

Рыжов – брюнет.

Задача 5. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы( химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде.

2. Москвич преподаёт не физику.

3. Тот, кто работает в Ленинграде, преподаёт химию.

4. Дмитрий преподаёт не биологию.

Какой предмет, и в каком городе преподаёт каждый из товарищей.

Решение: выделим три множества: множество имён, множество предметов, множество городов. Элемент каждого из множеств на черт. 26(а) задан своей точкой (буквы на чертеже – первые буквы соответствующих слов). Несоответствия – штриховые линии. Если же две разные точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попарно сплошными линиями. По условию задачи для каждой точки любого множеств найдется одна и только одна точка ей соответствующая. Граф на (на черт. 26,а) содержит все заданные в условии элементы множеств и отношения между ними. Задача на языке графов сводиться к нахождению трех «сплошных» треугольников с вершинами в разных множествах. Рассмотрим граф на черт. 26(а) напрашивается штриховой отрезок ХД. Действительно, Л соответствует Х и, одновременно, Л не соответствует Д, то есть Х не может соответствовать Д. Итак, используется типичная для такого рода операция на графе: если у треугольника с вершинами в разных множествах одна сторона сплошная, вторая – штриховая, то и третья должна быть штриховой. Из условий задачи следует правомерность ещё одной операции на графе: если какая-то точка соединена штриховым отрезком с двумя точками во втором множестве, то её следует соединить с третьей точкой этого множества сплошным отрезком. Последовательность в которой нужно проводить отрезки: ХД, ДФ, ДМ, ДК,ФК,МС,ИЛ, ХИ,БМ,БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподаёт химию в Ленинграде,

Дмитрий – физику в Киеве

Степан – биологию в Москве.

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

Задача 6. Четыре друга Ваня, Коля, Миша и Петя купили лодку и катались на ней в течение 4 недель, каждый одну неделю. В какой очерёдности они катались, если известно следующее:

1. Если во вторую неделю на лодке катались Ваня или Петя, то Миша катался в первую неделю.

2. Если Петя катался на лодке последним, то Миша был 3, а Ваня – первым.

3. Если Миша катался 2 или Петя 3, то Коля катался последним.

4. если Ваня катался в 3 неделю, то, Коля – во 2 и наоборот.

5. Если Петя катался в 1 неделю, то Миша в 3.

6. Если Петя катался в 3 неделю, то Ваня – во 2.

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

Первый этап. установление базисного множества высказываний. Множество высказываний назовём базисным множеством для данной задачи, если при помощи его элементы и логических связок можно выразить условия задачи и возможные ответы на её вопросы. В нашей задаче это множество состоит из 16 высказываний типа «Х катался на лодке в п-ю неделю», где Х{ Ваня, Коля, Миша, Петя} и n {1;2;3;4}. Обозначим сформулированное в кавычках высказывание символом (х,n), а операцию отрицания. Конъюнкции, дизъюнкции, импликации, эквиваленции – символами *, ^, ─, v или (v), то(-), а(^).

Запишем условия задачи символически:

1. [ (В;2) – (М;2)] – (М;1).

2. (П;4) – [(М;3)^(В;1)].

3. [(М;2)V(П;3)] – (К;4).

4. (В;3) – (К;2).

5. (П;1) – (М;3)

6. (П3) – (В;2).

Сложные высказывания 1-4 представим в виде конъюнкций простых импликаций и выразим, условия задачи с помощью 10 импликаций. (В;2) – (М;1), (П;4) – (В;1), (В;3) – (К;2), (П;3) – (В;2), (П;2) – (М;1), (М;2) – (К;4), (К;2) –(В;3), (П;4) – (М;3), (П;3) – (К;4), (П;1) –(М;3). Установление базисного множества высказывания.

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

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

Импликация Х – У Ребро ХУ графа

Эквиваленции Х – У ребро ХУ (с двумя стрелками)

Истинное высказывание красная вершина графа

Ложное высказывания черная вершина графа

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

Правило 01

Если импликация Х – У Если вершина Х красная, то и вершина У красная истина и посылка Х

истина, то и заключение У

истина Если вершина У черная, то и Х черная

Правило 02

Если импликация истина, а заключение ложно, то и Каждая вершина или черная или красная посылка ложна

Правило 03

Каждое высказывание одно и только одно из двух значений истинности

Правило 01,02,03 являются общими для всех логических задач

Пятый этап. Раскрашивание графа.

Рассмотрим 4 возможности: 1. вершина В;1 красная

2. вершина В;2 красная

3. вершина В;3 красная

4. вершина В;4 красная

Эти четыре возможности изображены на чертеже 29.

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

(В;2)^(К;4)^(М;1)^(П;3) И (В;4)^(К;3)^(М;1)^(П;2).

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

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