Теория графов — это подраздел дискретной математики, который изучает свойства графов, представляющих собой наборы вершин, соединяемых рёбрами.
Введение
Одним из самых обширных подразделов дискретной математики является теория графов, которая находит широкое применение при разрешении проблем в сфере экономики, управления, программирования, химии, социологии и многих других сферах познания. В теории графов на систематической основе изучаются их особенности и свойства. Граф представляет собой множество точек и линий, соединяющих эти точки. Родоначальником теории графов является Леонард Эйлер, который решил популярную в те времена задачу о мостах Кёнигсберга.
Теория графов
Построение графов необходимо для изучения взаимосвязей внутри множеств. Рассмотрим пример. Имеется множество А = {а1, а2, ... аn}, которое обозначает людское множество и все его элементы отображаются как точки. Множество В = {b1, b2, ... bm} обозначает связей (линии разных конфигураций). В множестве А задаются взаимосвязи среди людей данного множества. Необходимо построить граф, отображающий все точки и связи. Связи соединяют людские пары, которые знают друг друга. Конечно, количество знакомств у разных людей будет различным, и возможно есть люди, которые вообще ни с кем не знакомы (они обозначаются точками без соединяющих линий). В итоге построен следующий граф:
Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ
Точки на графе необходимо теперь считать вершинами графа, а связи будем называть рёбра графа.
В теории графов не учитывается фактическая специфика множества А и множества В. Существует огромное количество разнообразных проблем и задач, для разрешения которых возможно на время абстрагироваться от фактического наполнения множеств и их компонентов. Конкретика не влияет на процесс разрешения проблемы, вне зависимости от сложности. К примеру, при нахождении маршрута движения из точки А в точку В, при условии движения лишь по соединениям между точками, не имеет значения, что за этим стоит, люди, машины и так далее. Но в итоге мы имеем решение, истинное для всех содержаний, наполняющих структуру графа. Значит, не стоит удивляться, что теория графов является одной из наиболее применяемых методик при проектировании искусственных интеллектов, поскольку последние способны дискутировать с кем угодно и на темы любовных отношений, и на музыкальные и спортивные темы, а также обсуждать разрешение разных задач. Причём он осуществляет всё это без всяких переключений и перенастроек, без чего даже человек не всегда обходится.
Если брать строго математические формулировки, то можно выделить следующие определения графа:
- Граф — это системный набор объектов любой природы, которые являются его вершинами, и связей (рёбер), которые соединяют отдельные пары данных объектов.
- Задано наполненное множество вершин V, элементы v, принадлежащие множеству V, являются его вершинами. Графом G=G(V), имеющим множество вершин V, называется набор пар типа: е = (а, b), где а, b принадлежат множеству V, и указывают, какие вершины соединены. Все пары е = (а, b) являются рёбрами графа. Множество U является множеством рёбер е графа, а вершины а и b являются конечными точками ребра е.
Графы как структурированные данные
Повсеместное использование теории графов в области информационных технологий и компьютерных наук связано с прибавлением к изложенным выше формулировкам, обозначение графа как структуры данных. То есть в сфере компьютеров и информационных технологий граф считается нелинейной структурой данных. Под линейной структурой данных понимается структура, у которой составные элементы связаны отношениями вида «простое соседство». К линейным структурам данных можно отнести табличные данные, тексты и так далее. В противовес им существуют нелинейные структуры данных, в которых компоненты расположены согласно разным иерархическим уровням и делятся на три вида:
- Исходные элементы.
- Порождённые элементы.
- Элементы аналоги (подобные).
Граф является нелинейной структурой данных. Само слово граф происходит из греческого языка и означает «пишу». То есть основное предназначение графа — описывать отношения входящих в него элементов.
Главные понятия теории графов
Одним из главных терминов теории графов, на который опираются другие определения, является понятие «инцидентность». Пара вершин графа считается инцидентными, если их соединяет ребро. В случае, если на вершине начинается или заканчивается ребро, то ребро и вершина графа будут инцидентны. Разновидности графов отличаются по тому, какие типы рёбер и (или) вершин такие графы имеют. Направленные или не направленные рёбра отличают ориентированные и неориентированные графы. Понятие инцидентности требуется при формировании алгоритмов разрешения отдельных проблем на базе графов. К примеру, есть реализация обхода в глубину графа, который представлен матрицей инцидентности. Там используется простая идея, возможно движение только через вершины графа, которые соединены посредством рёбер. Если же рёбра имеют «вес» (как правило, числовой), то это позволяет разрешать задачи повышенной сложности и прикладного характера.
Классические задачи теории графов
Как отмечалось выше, одной из первых работ по практическому применению теории графов считается задача с Кёнигсбергскими мостами. В условии заданы река, омываемые рекой острова, и некоторое количество мостов. Требуется дать ответ, есть ли возможность при выходе из заданной точки, перейти каждый из мостов только один раз и возвратиться в исходный пункт. Схема на рисунке ниже.
Рисунок 2. Схема. Автор24 — интернет-биржа студенческих работ
Задача может быть смоделирована так: ко всем участкам на берегу надо прикрепить одну точку, а две точки можно соединить линией лишь в случае, когда участки суши соединяются мостом. Получаем следующий граф:
Рисунок 3. Граф. Автор24 — интернет-биржа студенческих работ
Эйлер сформулировал такой ответ на данную задачу. Если бы эта задача имела решение, то в сформированном графе должен существовать замкнутый маршрут, который проходит по рёбрам и который сдержит каждое ребро лишь единожды. Если есть такой маршрут, то все вершины должны иметь чётное число рёбер, что в данном случае не выполняется.
