Графы в математике

Размещено на http://www.allbest.ru/

1. История теории графов

граф кёнигсбергский эйлер головоломка

Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Первая работа о графах, принадлежащая швейцарскому математику Леонарду Эйлеру появилась в 1736 году. Эйлер начал свою работу о графах с рассмотрения одной головоломки - так называемой «задачи о кёнигсбергских мостах». Город Кёнигсберг расположен на берегах реки Прегель (Преголи) и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно пройдя в точности один раз по каждому мосту?

Эту схему можно представить в виде чертежа. Четыре части города обозначены точками А, В, С и D. Так как нас интересуют только переходы по мостам, мы можем считать A, B, C, D вершинами некоторого графа, а отрезки, соответствующие мостам, соединяющие между собой точки будем считать ребрами.

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

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

2. Что такое граф?

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

· Вершина графа. Либо конец какого-нибудь ребра графа либо изолированная точка графа.

· Ребро графа. Кривая, соединяющая две вершины графа и не содержащая других вершин.

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

Предположим, что футбольная команда вашей школы участвует в соревнованиях и играет с командами других школ. Пусть общее число команд равно шести. Вашу команду обозначим буквой А, а другие команды буквами B, C, D, E и F. Через несколько недель после начала соревнований окажется, что некоторые из команд уже сыграли друг с другом, например:

A c C, D, F,

B c C, E, F,

C c A, B,

D c A, E, F,

E c B, D, F,

F c A, B, D, E.

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

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

Тогда для данного списка проведенных игр мы получим схему. Схема такого вида называется графом. Она состоит из нескольких точек A, B, C, D, E, F, называемых вершинами, и нескольких соединяющих эти точки отрезков, таких как AC или EB, называемых ребрами графа.

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

3. Изображение графа

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

4. Способы представления графа. Представление графов в ЭВМ

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

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

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

Третий способ представления графа это табличный. Граф - таблица с вершинами и с 1 или 0 в ячейках таблицы, они обозначают, есть ребро(1) между этими вершинами или нет (0). Иногда в литературе встречается что вместо 1 и 0 пишут «истина» и «ложь», т.е. 1 это И (истина), а 0 это Л (ложь). Давайте представим граф для нашей задачи с крольчатами. Вершин в задаче четыре, все соединены друг с другом ребрами.

Вот два варианта нашей задачи в табличном виде.

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

5. Виды графов

Основные понятия:

· Дерево. Связный граф, не имеющий циклов.

· Дополнение G' графа G. Граф G' состоит из всех ребер (и их концов), которые необходимо добавить к G для того, чтобы получился полный граф.

· Изоморфные графы. Графы G₁ и G₂ изоморфны, если между их вершинами можно установить взаимно однозначное соответствие, что пары вершин графа G₁ в том и только в том случае соединены ребром, когда соединены ребром соответствующие пары вершин графа G₂. В случае ориентированных графов это соответствие должно сохранять ориентацию ребер.

· Лес. Граф, все связные компоненты которого являются деревьями (граф без циклов).

· Нуль-граф. Граф, состоящий только из изолированных вершин: граф, не имеющий ребер.

· Ориентированный граф. Граф, на котором указаны направления всех его ребер.

· Полный граф. Граф, любые две вершины которого соединены ребром. Полный граф, которого N вершин, имеет Ѕ*n (n-1) ребер.

· Цикл. Замкнутая цепь.

· Эйлеров граф. Граф, содержащий эйлерову линию.

· Эйлерова линия. Цепь, проходящая по всем ребрам графа в точности по одному разу.

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

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

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

Этот новый граф мы назовем дополнением графа G; его принято обозначать его через G'. Ребра обоих графов G и G' вместе составляют полный граф с теми же вершинами. Граф можно изображать по-разному.

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

Во-вторых, мы можем произвольно располагать вершины на плоскости. Например, вершины графа G можно расположить так, как показано на рис.

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

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

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

Такой цикл мы будем называть эйлеровой линией, а граф, обладающий эйлеровой линией - эйлеровым графом.

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

Граф могут быть ещё ориентированные, в котором указаны направления всех его ребер, а также неориентированными соответственно в котором не указаны направления всех его ребер.

Размещено на Allbest.ru