Министерство образования Российской Федерации

Марийский Госдарственный Технический Университет

Учебное пособие

Н. В. Костромина Б. Л. Истомин

Графы: теория, задачи, алгоритмы

Йошкар-Ола, 2000г

ББК

K

УДК

Рецензенты:

1.

2.

Печатается по решению редакционного издательского совета МаГТУ.

Н. В. Костромина, Б. А. Истомин.

Теоретические основы применения графов: Учебное пособие.-Йошкар-Ола, МарГТУ, 2000.- с

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

 Костромина Н. В., Истомин Б. А.

 Мариский Государственный

Технический Университет

Введение

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

Таким образом, граф можно представить как совокупность двух множеств: V- (точек) и U - линий, между элементами которых определено отношение инцидентности, т.е. каждый элемент uU инцидентен ровно двум элементам v₁,v₂V (или каждая вершина инцидентна какому- либо ребру);

G = < V, U >.

Элементы множества V называются вершинами (или узлами) графа G, элементы множества U- его рёбрами. Вершины и рёбра графа называют также его элементами и вместо vV и uU пишут vG, uG. .

Первая работа по графам была опубликована в 1736 г. Леонардом Эйлером. Эта работа объясняла решение задачи о кенигсбергских мостах: можно ли совершить про-

а) б)

Рис. В1

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

Ясно, что по условию задачи не имеет значения, как проходит путь по частям суши a, b, c, d, на которых расположен город, поэтому их можно представить вершинами. А так как связи между частями суши осуществляются только через семь мостов, то каждый из них изображается ребром, соединяющим соответствующие вершины. В результате получается граф, показанный на рис. В.1 Исследуя этот граф, Эйлер дал отрицательный ответ на свой вопрос, более того, он доказал, что подобный маршрут имеется только на таком графе, каждая из вершин которого связана с чётным числом рёбер.

В середине XIX в. Г. Кирхгоф применил графы для анализа электрических цепей. Как математическая дисциплина, теория графов сформировалась к середине 30-х годов XX века, её основатели: Д. Кениг, Л. С. Понтрягин, А. А. Зыков, В. Г. Визинг и др. С помощью теории графов, наряду с головоломками и играми, решаются многие важные практические задачи, в которых имеется некоторое множество объектов, тем или иным образом связанных друг с другом. Это могут быть сети автомобильных дорог, телефонные и другие коммуникационные сети, системы нефтепроводов и т. п.

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