Теория графов

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

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

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

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

схема расположения Кенигсбергских мостовРисунок 1 — Схема расположения Кенигсбергских мостов

В городе было семь мостов, которые соединяли острова между собой и с береговыми частями города. Мог ли любой житель Кенигсберга, выйдя из дома, пройти по всем семи мостам города в точности по одному разу и вернуться домой? Обобщенный вариант данной задачи, называют задачей почтальона. Эта задача имеет решение и в данном случае ответ на этот вопрос: «нет не мог».

Читайте также  Абсолютная медиана графа

К 50-м годам нашего века в теории графов сложились два существенно различных направления: алгебраическое и оптимизационное. Последнее получило широкое развитие благодаря появлению электронных вычислительных машин (ЭВМ) и в связи с разработкой методов линейного программирования.

Разбермся теперь, что из себя представляет граф и дадим ему строгое определение.

граф, определение
Рисунок 2 — Граф

Граф состоит из двух типов элементов: вершин и дуг, соединяющих между собой эти вершины. При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком (стрелкой). Для графа представленого на рисунке 2: A, B, C, D, E — вершины; a, b, с, d, e, f, g — дуги графа.

В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В более строгом определении граф — это совокупность множества Х, элементы которого называются вериашами, и множества А упорядоченных пар вершин, элементы которого называются дугами. Граф обозначается как G(Х, А). Предполагается, что как множество Х, так и множество А содержат конечное число элементов.

Далее введем основные определения, используемые в теории графов.

Граф, в котором направления дуг не задаются, называется неориентированным. Неориентировалные дуги называются ребрами. Например в графе представленом на рисунке 2 дуги a, b, d, g — неориентированые (они обозначены отрезками); дуги c, e, f — ориентированые (обозначены стрелочками).

Читайте также  Метод искусственного базиса (Симплекс метод) - Пример 2

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

Дуга, начальная и конечная вершина которой совпадают, называется петлей. На рисунке 2 дуга h является петлей.

Дуга и вершина инцидентны друг-другу, если вершина является для этой дуги концевой или начальной точкой. На рисунке 2 дуга с и вершина A инцидентны друг другу.

Если две дуги инцидентны одной и той же вершине то говорят что эти дуги инцидентны друг-другу. На рисунке 2 дуги a и с инцидентны друг-другу так как каждая из них инцидентна вершине A.

Будем называть две вершины соседними, если есть дуга, их соединяющая. На рисунке 2 вершины A и B соседние, поскольку существует дуга a, которая соединяет эти вершины.
Рассмотрим произвольную последовательность вершин х1, х2,…, хn, хn+1, Цепью называется любая последовательность дуг a1, a2, …, an, такая, что концевыми точками дуги ai являются вершины хi и хi+1 т. е. ai = (хi, хi+1) или ai = (хi+1, хi) для i = 1, 2, …, n. Вершина х1 называется начальной вершиной цепи Вершина хn+1 называется конечной вершиной цепи. Будем говорить, что цепь соединяет начальную вершину с конечной. Длина цепи совпадает с числом входящих в нее дуг. На рисунке 2 последовательность дуг e, g, i, с образует цепь длины 4, которая соединяет вершину B с вершиной A.
Цепь, для которой а = (хi, хi+1) при всех i = 1, 2, …, n, представляет собой путь. длина пути, его начальная и конечная вершины могут быть определены точно так же, как для цепи. Напрямер, на рисунке 2 дуги a, c, i, g образуют путь длины 4, соединяющий вершину B с вершиной C.
Циклом называется цепь, у которой начальная и конечная вершины совпадают. Контуром называется путь, у которого начальная и конечная вершины совпадают. Длина цикла или контура определяется так же, как длина соответствующей цепи. Например, на рисунке 2 дуги a, e, g, i, с образуют цикл длины 5, а дуги a, c, i, g, e — контур длины 5.
Цепь, путь, цикл или контур называются простыми, если ни одна вершина не инцидентна более чем двум входящим в нее дугам (т. е. если цепь, путь, цикл или контур не содержат внутри себя циклов).

Читайте также  Медиана графа

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Выполненные готовые работы

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...