Статья на тему "Графы - это интересно"

Графы – это интересно

К 18 веке. через реку Прегель, протекавшую по городу Кенигсберг (Калиниград), было построено 7 мостов. Они связывали ее берега с двумя островами (рис. 1).

                                                Рис.1

 

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

В будущем задача привлекала внимание ученых со всего света. И разрешить ее удалось в 1736 г. известному швей­царскому, немецкому и

                                                     

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

Разбираясь с задачей о семи мостах, Эйлер поступил следую­щим образом: он изобразил точками В и С берега реки, точками А и D – его острова, а линиями — мосты, которые соединяют соответствующие участки берегов и островов. В результа­те получилась фигура, приведенная на рисунке 2.

Такую фигуру называют графом, точки, А, В, С, D - вершинами графа, а отрезки кривых, соединяющие вершины,— дугами (или рёбрами) графа.

Эйлер подсчитал число дуг, которые исходят из каждой вер­шины графа. Из вершин В, С и D исходит по три дуги, а из вершины А — пять дуг. Вершины графа, из ко­торых исходит нечетное число дуг, он назвал нечетными вершинами, а вершины, из которых исходит четное число дуг,— четными. Все вершины данного графа оказались не­четными.

В ходе решения этой задачи Эйлер установил следую­щие четыре свойства графа:

1.                    

Число нечетных вершин графа всегда четно. Невоз­можно

                                              Рис.3

начертить граф, который имел бы нечетное число нечетных вершин.

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

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

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

Поскольку число нечетных вершин графа, получившегося при решении

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

Рассмотрим теперь еще одну задачу, аналогичную за­даче семи мостов.

Задача 1. Можно ли привязать к гвоздям А, В, С, D, К, М веревку так, как показано на рисунке 3, не разрезая ее на части и не сдваивая?

Решение. Из рисунка видно, что из вершин А, В, С и D исходят по три ребра, а из вершин М и К — по пять. Получили, что все шесть вершин нечетны. Согласно свойству 4, найденному Эйлером, привязать веревку так, как требуется в условии задачи, невозможно.

Начертим теперь без отрыва карандаша от бумаги лю­бую
 

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

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

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

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

Рассмотрим фигуру, изображенную на рисун­ке 5. У этой фигуры имеются только две нечетные верши­ны. По свойству 3 ее можно начертить одним росчерком. Заметим, что число росчерков                   равно половине числа не­четных вершин.

                   Рис.5

 

                                                    Рис.7                               Рис.8

Фигуру, изображенную на рисунке 6, нельзя начертить одним росчерком: эта фигура имеет четыре нечетные вер­шины. Ее можно начертить самое меньшее двумя росчер­ками. И опять число росчерков оказалось равным полови­не числа нечетных вершин (4 : 2 = 2). Фигуры, изображен­ные на рисунках 7 и 8, можно начертить соответственно четырьмя и пятью росчерками. В этом случае минималь­ное число росчерков опять-таки равно половине числа не­четных вершин (8:2=4, 10 :2 =5).

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

 Впервые термин «граф» в 1936 г. ввел венгерский математик Денеш Кениг, назвав графами схемы, состоящие из множества точек и связывающих эти точки отрезков прямых или кривых.

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

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

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

Рис.9

2.        После того как произошел частичный обмен фотографиями: Алина и Борислава дали по фотографии Виктории, Галине и Дарье, а Виктория, Галина и Дарья — по фотографии Алине и Бориславе, соответствующий граф будет иметь вид, изображенный на рисунке 10. Такой граф называется неполным графом.  

                                                                                    

                              Рис.10                                                             Рис.11                                                   

Этот граф мы можем изобразить так, чтобы линии, соединяющие точки А, Б, В, Г, Д, кроме этих точек, других точек пересечения не имели (рис. 11).

Граф, который можно начертить на плоскости так, чтобы ребра его пересекались только в его вершинах, называется плоским графом. Следовательно, граф на рисунке 16 плоский. Этот же граф можно изобразить по-другому, изменив расположение вершин на плоскости (рис. 12).

                          Рис.12                                    Рис.13   

Графы, изображенные на рисунках 10, 11 и 12, дают нам одну и ту же информацию о решении предложенной задачи. По этой причине такие графы называют одинаковыми или изоморфными. Графы будут изоморфны, если:

1) между вершинами их можно установить взаимно однозначное соответствие;

 2) две вершины одного графа соединены одним ребром, то и в другом графе соответствующие две вершины также должны быть соединены одним ребром (рис. 10, 11).

3.        Полному обмену фотографиями соответствует граф, показанный на рисунке 13. Этот граф является полным. Граф называется полным, если любые его две вершины соединены ребром. Заметим, что если полный граф имеет n вершин, то он будет иметь   ребер.

                                                                                           Рис.14

Рассмотрим задачу. Пусть на рисунке 19 изображена схема дорог какого-либо населенного пункта. Требуется найти дорогу, соединяющую перекрестки A и R. Легко заметить, что имеется много дорог, идущих от А к R. Для нахождения одной из них поступаем следующим образом. Двигаемся от А по направлению к R до перекрестка, а затем к другому перекрестку и т.д. В конце нашего движения мы достигнем перекрестка R. Поскольку в условии задачи никаких ограничений не дано, то, двигаясь от перекрестка А к перекрестку R, мы можем побывать на любом перекрестке или улице больше одного раза. Если бы потребовалось найти кратчайшую дорогу, то мы определили бы все дороги от А к R и их сравнением нашли кратчайшую.

Если при следовании от A к R на каком-либо перекрестке мы побываем больше одного раза, например, если пройдем по пути ALMNKMR и на перекрестке М побываем два раза, то, вычитая из этого пути путь MNKM, получим путь ALMR, который короче пройденного. Отметим, что на перекрестках A, L, М и R мы были только один раз. Такой путь в теории графов называется дугой (линия на графе, не проходящая ни через одну из вершин более одного раза). Согласно сказанному дугами будут: AKNR, ALMNR и т. д. Дуги могут иметь самопересечения, например, путь ABCDEFR также является дугой.

Линия на графе, не проходящая ни по какому ребру более одного раза, называется цепью. Например, ALMNKMR является цепью, которая соединяет вершины A и R.

Если, начав движение от вершины A, пройдем по нескольким вершинам графа так, что на каждом ребре побываем только один раз, а затем вернемся в ту же вершину A, то такой путь называется циклом. Вообще любая замкнутая цепь называется циклом. На рисунке 14 циклом являются пути ALMKA и ABCDRNKA.

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

Например, цикл ALMKPMNKA (рис. 14) является неэлементарным циклом.

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

                        Рис.15

 

                          Рис.16

такой граф, который не имеет ни одной изолированной вершины).

Например, граф на рисунке 15 не связный, так как из вершин А, В, С, D нельзя пройти к вершинам К, Р, Q. Тоже самое можно сказать о графе на рисунке 16, который одновременно является нулевым графом.

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

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

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