Элементы теории графов. Способы обхода графов
статья по информатике и икт (11 класс) по теме

Лицей – интернат естественных наук

Автор

Ищенко М. Н.,

учитель информатики

Содержание

Введение        

1. Основные понятия        

2. Пути и маршруты в графах        

3. Способы представления графов        

3. 1. Матрица смежности        

3. 2. Матрица инциденций        

3. 3. Список смежности        

4. Обходы графов        

4. 1. Поиск в глубину        

4. 2. Поиск в ширину        

Заключение        

Список литературы        

Приложение        

Введение

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

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

Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

1. Основные понятия

Декартовым произведением двух множеств A и B называется множество пар элементов, таких, что первый элемент пары берется из множества A, второй из B: A x B = {(a, b): aA, b  B}.

Например, декартовым произведением множеств A ={0,1} и B = {a, b, c} является множество A x B = { (0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}.

Граф — это пара G = (V, E), где  V – множество вершин, E – множество ребер (дуг).

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

Вершины графа обозначают латинскими буквами A, B, C, D или цифрами. Иногда граф в целом можно обозначать одной заглавной буквой.

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

Отрезок между вершинами, не имеющий направления, называют ребром.

Дуги – это как дороги с односторонним движением: можно проехать только в одну сторону. Ребра – это как дороги с двусторонним движением: можно проехать в обе стороны.

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

Рассмотрим пример.

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение:

Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа.

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

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

Ориентированным называется граф, в котором — множество упорядоченных пар вершин вида (x, y), где x – называется началом, y – концом дуги. Дугу (x, y) часто записывают как  и изображают в виде:

X

Y

Считается, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x. Ориентированный граф также называют орграфом.

5

1

2

3

4

Рис 3. Взвешенный орграф

7545

10

35

20

30

40

35

5

1

2

3

4

Рис 2.Орграф

На рис. 2 изображен орграф с 5 вершинами и 7 дугами.

На практике вершины орграфа можно использовать для представления объектов, а дуги — для отношений между объектами. Например, вершины могут представлять собой города, а дуги — маршруты рейсов самолетов из одного города в другой. В другом примере вершины могут соответствовать блокам операторов программ, а дуги — направлениям перехода от одного блока к другому.

Иногда дугам графа приписывают некоторое число (например, расстояние между городами, время передачи данных между узлами), называемое весом. Тогда граф называют взвешенным орграфом (см. рис.3). Этот вес может иметь различные единицы измерения, исходя из условия, по которому строится граф.

X

Y

Граф, содержащий только ребра, называется неориентированным.Ребро (x, y) графически изображается в виде:

5

1

2

3

4

Рис 4. Неориентированный граф

5

1

2

3

4

Рис 5. Взвешенный неориентированный граф

7545

10

30

40

35

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

Вершины, соединенные общим ребром, называются смежными вершинами. Ребра, имеющие общую вершину, называются смежными ребрами.

На рис.4 вершины 1 и 5 — смежные, т. к. соединены общим ребром 1– 5. Ребра 4–5, 4–1 и 4–3 являются смежными ребрами, потому что имеют общую вершину 4.

Ребро и любая из двух вершин, с которыми связано это ребро, называются инцидентными.

На рис. 4 ребро 4–1 и вершина 1 – инцидентны.

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

На рис. 4 степень вершины 2 равна 1, степень вершины 4 равна 3.

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

На рис. 2 полустепень исхода для вершины 2 равна 1, полустепень захода – 2, степень – 3.

5

1

2

3

4

Рис 6. Смешанный граф

Граф, содержащий и рёбра и дуги, называется смешанным.

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

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

Данной задачей в 1736 году заинтересовался выдающийся математик Леонард Эйлер.

«В Кенигсберге есть остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава, через которые перекинуто семь мостов: а, b , с, d, e, f, g. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?».

Эйлеру удалось ответить на этот вопрос.

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

D

A

B

C

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

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

В ходе рассуждений Эйлер пришёл к следующим выводам:

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

2. Пути и маршруты в графах

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

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

В качестве примера рассмотрим орграф, представленный на рис. 2. Одним из существующих путей, соединяющих вершины 1 и 3, является последовательность вершин 1, 2, 1, 4, 3. Единственным простым путем для той же пары вершин является последовательность 1, 4, 3. Пути из вершины 1 в вершину 5 для того же графа не существует.

Если существует путь из вершины графа v в вершину u , то говорят, что вершина u достижима из v.

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

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

Рассмотрим орграф на рис. 2. Путем из вершины 2 в вершину 3 будет являться последовательность 2, 1, 4, 3; длина этого пути равна 3. Для аналогичного взвешенного орграфа на рис. 3 длина того же пути равна 130.

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

5

1

2

3

4

Рис 2.Орграф

5

6

2

3

4

Рис 7. Неориентированный граф

1

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

Неориентированный граф, представленный на рис. 7, является связным, а орграф, представленный на рис. 2, не является связным, т. к. не существует путей из вершин 1, 2, 3 и 4 в вершину 5.

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

Замкнутый путь называется циклом, если все его вершины (кроме начальной и конечной) различны.

Рассмотрим граф, изображенный на рис. 7. Для него путь 2, 1, 6, 5, 4, 1, 2 является замкнутым; а путь 1, 6, 5, 4, 1 является циклом.

Рис. 8. Петля

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

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

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

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

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

3. Способы представления графов

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

3. 1. Матрица смежности

Матрица смежности представляет собой квадратную матрицу n х n, где n – количество вершин графа.

Каждая ячейка этой матрицы может принимать только два значения (0 или 1) для невзвешенного графа или вес ребра для взвешенного. Ячейка несет в себе информацию о том, смежны вершины или нет.

5

6

2

3

4

Рис 7. Неориентированный граф

1

Рассмотрим матрицу смежности для графа на рис. 7. В графе 6 вершин:

При более подробном рассмотрении можно заметить, что в случае графа без петель матрица имеет ряд особенностей:

1) главная диагональ (выделена красной линией) матрицы всегда заполнена нулями, так как вершина не может быть смежна сама себе;

2) если граф неориентированный, то матрица симметрична относительно главной диагонали.

1

2

4

3

5

3

1

2

6

Рис. 9. Взвешенный орграф

Рассмотрим матрицу смежности для графа на рис. 9. В графе 4 вершины:

3. 2. Матрица инциденций

Матрица инциденций представляет собой матрицу m х n, где m – количество ребер или дуг графа (орграфа), а n – количество вершин. На пересечении i - ой строки и j - ого столбца проставляются значения по следующему правилу:

"1" – если i - ое ребро и j - ая вершина инцидентны (для орграфа – если i - ая дуга "входит" в j - ую вершину);

"0" – если i - ая дуга и j - ая вершина не инцидентны;

"-1" – только в случае орграфа: если i - ая дуга "выходит" из j - ой вершины;

«1» применяют для невзвешенного графа, для взвешенного графа применяют вес ребра.

5

6

2

3

4

Рис 7. Неориентированный граф

1

Рассмотрим матрицу инциденций для графа на рис.7. В графе 6 вершин и 7 рёбер.

Рассмотрим матрицу инциденций для графа на рис.10. В графе 4 вершины и 5 рёбер.

1

2

4

3

Рис. 10. Орграф

1

2

4

3

5

3

1

2

6

Рис. 9. Взвешенный орграф

Рассмотрим матрицу инциденций для графа на рис. 9. В графе 4 вершины и 5 рёбер.

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

3. 3. Список смежности

Список смежности представляет собой перечень смежных вершин.

Рассмотрим список смежности для графа на рис.7:

5

6

2

3

4

Рис 7. Неориентированный граф

1

4. Обходы графов

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

При решении многих задач с использованием графов необходимо уметь обходить все вершины и ребра (дуги) графа. Обойти граф — это побывать во всех вершинах точно по одному разу. Существует два классических алгоритма обхода графов: обход графа в глубину и обход графа в ширину.

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

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

4. 1. Поиск в глубину

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

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

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

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

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

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

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

Пример.

Рассмотрим неориентированный граф (рис. 7).

5

6

2

3

4

Рис 7. Неориентированный граф

1

Решение:

Граф неориентированный. Стартовая вершина – 1, с неё начинаем обход. Эта вершина активна и единственная открытая. Остальные вершины: 2,3,4,5,6 – новые. У вершины 1 три инцидентных ребра – 1–2, 1–4 и 1–6. Начнем с ребра 1 –2, проходим его и попадаем в вершину 2 – она становится открытой. У вершины 2 одно инцидентное ребро 2–1 и оно просмотрено. Таким образом, мы просмотрели вершину 2 и она становится закрытой, по ребру 2–1 возвращаемся  в вершину 1.

По ребру 1– 4 мы попадаем в вершину 4. Она становится открытой. У вершины 4 четыре инцидентных ребра: 4–1, 4–3, 4–5, 4–6.

Ребро 4–1 просмотрено.

Рассматриваем ребро 4–3, по нему мы попадаем в вершину 3.Она становится открытой. У вершины 3 одно инцидентное ребро 3–4, т.е. мы ее посмотрели и оно просмотрено. Таким образом, мы просмотрели вершину 3 и она становится закрытой, по ребру 3–4 возвращаемся  в вершину 4.

Рассматриваем ребро 4 – 5. У вершины 5 два инцидентных ей ребра: просмотренное (4–5) и ребро 5–6, по которому мы попадаем в вершину 6.

Вершина 6 имеет три инцидентных ей ребра: просмотренное 6–5, 6–1 и 6–4.

По ребру 6–1 мы попадаем в вершину 1, которая является просмотренной. По ребру 6–4 попадаем в вершину 4, которая также является просмотренной.

Таким образом, все вершины графа являются просмотренными.

Порядок посещения вершин: 1, 2, 4, 3, 5, 6.

4. 2. Поиск в ширину

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

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

Сначала посещается сама вершина A, затем все вершины, смежные с A, находящиеся от нее на расстоянии 1, затем вершины, находящиеся от A на расстоянии 2, и т.д. Чем ближе вершина к стартовой вершине, тем раньше она будет посещена. Поиск в ширину ищет наиболее короткий возможный путь.

Пример.

5

6

2

3

4

Рис 7. Неориентированный граф

1

Рассмотрим неориентированный граф (рис. 7).

Решение:

Граф неориентированный. Стартовая вершина – 1, с неё начинаем обход. Отмечаем её как просмотренную, кладем в очередь. Вершины 2, 4 и 6 являются смежными вершине 1. Их помещаем в очередь (2, 4,6) и отмечаем как просмотренные. Рассмотрим вершину 2. Она не имеет смежных вершин. Далее рассмотрим вершину 4: у неё две смежных вершины 3 и 5. Помещаем их в очередь и отмечаем как просмотренные.

Таким образом, все вершины графа являются просмотренными.

Порядок посещения вершин: 1, 2, 4, 6, 3, 5.

Заключение

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

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

На практике граф используется для задания симметрических отношений для объектов.

Список литературы

1. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
2. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.
3. Оре О. Теория графов. – М.: Наука, 1980.

Для подготовки данной работы были использованы материалы с сайтов:

1. http://ru.wikipedia.org/wiki.
2. http://school-sector.relarn.ru.

Приложение

Программа, описывающая обход графов в глубину (Pascal).

Program graff;

Var n, v, u: integer;

        fr: text;

        gr: array[1..30, 1..30] of integer;

        nov: array[1..15] of boolean;

procedure dfs (v: integer);

        var u: integer;

Begin

readln;

write (v, ‘ ‘);

nov [v]:=false;

for u:=1 to n do

if (gr[v,u]=1) and (nov[u]) then dfs (u);

end;

begin

n:=3;

for v:=1 to n do

        begin

                nov [v]:=true;

                writeln;

                for u:=1 to n do begin

                        nov[u]:=true;

write (‘ gr[‘,v,u,’]=’);

read (gr [v, u] );

end;

end;

        for v:=1 to n do begin

                if nov[v] then dfs (v);

        end;

readln;

End.