Графы

                             ДОКЛАД

                 на научно-практическую                    

                         конференцию                                        

                                  Тема:    ГРАФЫ

Работу выполнил:  Улантиков Антон, ученик  8«А»класса

                                 Второй Новосибирской гимназии,

                                 Г. Новосибирск.

Научный руководитель:  Ефимова Наталья Владимировна,

                                           учитель  математики высшей                                      

                                           квалификационной категории.

                                               ГРАФЫ

             Вcем известно, что слово «граф» означает дворянский титул, например граф Лев Николаевич Толстой. А вот в математике графом называют набор точек, некоторые из которых соединены линиями. Точки именуются вершинами графа, а отрезки — ребрами На рис. I изображён граф, хорошо знакомый москвичам. Это схема московского метро: вершины конечные станции и станции пересадок, ребра пути, соединяющие эти станции. На рис 1 вы видите ещё один граф — часть генеалогического древа Графу Л. Н. Толстого. Здесь вершины — предки писателя, а рёбра показывают родственные связи между ними.

Основы теории графов как математической науки заложил в 1736 г. Леопард Эйлер, рассматривая задачу о кёнигсбергских мостах.

                                                    ЗАДАЧА

                                  О КЁНИГСБЕРГСКИХ МОСТАХ

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

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

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

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

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

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

Возможно, многим читателям подобного рода задачи знакомы ещё по журналам «Мурзилка» или «Весёлые картинки». Там предлагалось начертить какую-нибудь фигуру, не отрывая карандаша от бумаги и не проводя дважды по одной линии. На рис 5 и 6 приведены две такие фигуры. Первая из них называется «Сабли Магомета-'. В ней существует эйлеров цикл, так как из шести вершин графа выходит чётное число ребер Вторая фигура — «Распечатанное письмо» — имеет две вершины (нижние), из которых выходит нечётное количество рёбер. Поэтому рисунок нужно начинать с одной из них, а в другой — заканчивать.

А как же обстоит дело с кёнигсберскими мостами? Здесь при каждой из четырёх вершин нечётное число рёбер, так что пет не только

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

Карту, изображённую на рис. 4, попробуйте проанализировать самостоятельно.

                              ГРАФЫ ИЗОМОРФНЫЕ И ПЛОСКИЕ

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

Игрушка не имела такой популярности, какой еще недавно пользовался «кубик Рубика», но оставила след в математике. Замкнутый путь по рёбрам графа, проходящий по одному разу через все вершины, называю гамильтоновым циклом. В отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.

Но если поставить проволочный додекаэдр на плоскость, а затем поднести источник света близко к центру ею верхней грани (рис. 8), то проекции-тени рёбер па плоскость составят граф, изображенный па рис.9. Красным цветом отмечен гамильтонов цикл. На рис. 10 показаны графы, полученные таким же образом из остальных четырёх правильных многогранников. Попытайтесь найти на них гамильтоновы циклы.

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

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

     Рассмотрим два графа, которые «не укладываются» па плоскость без пересечения рёбер Первый из них граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным (рис, 13).

    Второй граф. с шестью вершинами и девятью рёбрами (рис I I). носит название < домики — колодцы», Оно произошло от старинного задачи головоломки.

   В трёх избушках жили трое друзей. Около их домиков находилось три колодца: один с солёной водой, второй со сладкой, a третий с пресной Но однажды друзья поссорились, да так. что не видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались      

    Как это сделать? На рис. IS проведено восемь из девя ш тропинок, но провести девятую уже не удаётся

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

плоские графы обладают многими интересными свойствами. Гак. Эйлер обнаружил простую связь между количеством вершин (В). количеством ребер (Р) и количеством частей (Г). на которые граф разделяет плоскость:

В - Р+ Г= 2.

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

ГРАФЫ ИГР

Па рис. 16 изображена шахматная мини-доска размером 3 х 3 клетки, а на ней четыре коня два белых и два черных. Задача переставить фигуры так, чтобы одинаковые кони оказались в противоположных углах доски (рис. 17). Перемещать их можно только ходом шахматного коня и нельзя ставить фигуру на уже занятое поле.

Все попытки совершить такую перестановку терпят неудачу . Почему?

Давайте начертим граф возможных ходов копей подоске (рис. 18).Затем построим изо морфный ему граф без самопересечении в двух вариантах: па одном отметим первоначальное

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

Этот же граф помогает решить и ещё одну задачу. В ней требуется из положения, показанного на рис. 16, за наименьшее количество ходок перевести коней в положение, изображённое на рис. 20, т. е. поменять местами чёрных и белых. Вновь обратимся к рис. 19, а. Ясно, ч то фигуры должны двигаться по этому графу в одном 11 том же направлении, и каждому коню придётся сделать ровно 4 хода, т.е. всего понадобится 16 ходов.

Вообще, граф игры - это граф, вершины которого ситуации, возникающие в процессе игры, а ребра связывают вершит- с теми вер шинами-ситуациями, которые могут сложиться после очередного хода. Так. в шахматах из начальной позиции первым ходом можно получить 20 позиций; каждая пешка можем пойти на одну или две клетки вперёд, и каждый копь может перейти на одно из двух полей. после хода чёрных число возможных позиций становится равным 20*20 = 400 и в дальнейшем быстро увеличивается. Это обстоятельство и стало основной трудностью при создании шахматных программ.

                        БРОДЯЧИЕ ТОРГОВЦЫ И ЖЕЛЕЗНЫЕ ДОРОГИ

Одна из классических задач теории графов называется -задачей коммивояжёра» или «задачей о бродячем торговце».

Представим себе торгового агента, который должен побывать в нескольких городах и вернуться обратно. Известно, какие дороги соединяют эти города и каковы расстояния между ними по этим дорогам (рис. 22). Нужно выбрать самый короткий маршрут. Это уже пе «игрушечная' задача. 11апример, водитель почтового автомобиля, вынимающий письма из ящиков, очень хотел бы знать Кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам. А решить эту задачу очень непросто, особенно когда число вершин графа велико.

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

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

Примере дороги, соединяющей пять городов: А, В. С, D и Е', Стоимость прокладки пути между каждой парой городов указана в таблице, а Расположение городов — на карте (рис. 23) Сначала строим ту дорогу, которая имеет наименьшую стоимость. В нашем случае это маршрут Н — Е. Теперь найдём самую дешёвую линию, соединяющую город В или Е с каким-то из остальных городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично — ищем самый дешёвый из путей, соединяющих один из городов В. С. Ее одним из оставшихся А или D. Это дорога между С и А. Осталось подключить к железнодорожной сети город А Дешевле всего соединить сто с С. Получим сеть, изображённую на рис. 21

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

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

                                    НАПРАВЛЕННЫЕ ГРАФЫ

В графах игр рёбра тоже часто бывают направленными если из позиции можно перейти к позиции Р1, го не всегда из позиции Р2, можно вернуться к позиции P1

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

Графы, в которых все рёбра имеют направления, называются орграфами. Па них удобно рассматривать различные транспортные задачи. Например, между городами А и В имеется сеть дорог, и на некоторых из них движение одностороннее (рис. 26). Кроме того, задана пропускная способность каждой дороги, скажем is тысячах машин в час. Попробуем ответить па вопрос: какой максимальный поток машин возможен из А в В и из В в А?

Как видим, хотя из А может выезжать в час 7 тыс. машин, по въехать в В в час смогут лишь 4 тыс. из них. Несложно проверить, что 1 тыс. машин в час остальные дороги в состоянии пропустить

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

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

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

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

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