Применение теории графов в информатике

Введение

Одним из наиболее объёмных разделов в дискретной математике считается теория графов, которая широко используется для решения различных проблем в самых разных сферах жизнедеятельности людей, в том числе и в информатике. Теория графов на научной базе занимается изучением их особенностей, параметров, характеристик и свойств. Граф является множеством точек и линий, которые соединяют этот набор точек. Основоположником теории графов считается Леонард Эйлер, решивший известную в его бытность задачу Кёнигсбергских мостах.

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

Формирование графов требуется для определения взаимных связей элементов внутри множеств. Приведём конкретный пример. Существует множество $А = {а_1, а_2, ... а_n}$, обозначающее некоторое людское сообщество, где все его компоненты изображаются в виде точек. Есть также множество $В = {b_1, b_2, ... b_m}$, которое отображает связи между людьми, то есть это линии разной конфигурации. В множестве A$А заданы взаимные связи между людьми этого множества. Требуется выстроить граф, который будет отображать все точки и связи между ними. Связи (линии) проходят между теми парами людей, которые знакомы друг с другом. Естественно, число знакомств у каждого человека будет разным, и, вероятно, имеются такие люди, у которых вообще нет ни одного знакомого человека. Они должны обозначаться точками, от которых не отходят соединительные линии. В результате будет сформирован такой вид графа: А заданы взаимные связи между людьми этого множества. Требуется выстроить граф, который будет отображать все точки и связи между ними. Связи (линии) проходят между теми парами людей, которые знакомы друг с другом. Естественно, число знакомств у каждого человека будет разным, и, вероятно, имеются такие люди, у которых вообще нет ни одного знакомого человека. Они должны обозначаться точками, от которых не отходят соединительные линии. В результате будет сформирован такой вид графа:

Статья: Применение теории графов в информатике

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ

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

Среди существующих строгих математических формулировок следует подчеркнуть такие определения графа:

1. Графом является систематизированный комплекс объектов разной физической природы, которые считаются вершинами графа, и связей, называемых рёбрами, которые связывают некоторые пары этих объектов.
2. Существует заполненное множество вершин $V$, причём элементы $v$, которые принадлежат множеству $V$, считаются его вершинами. Графом $G = G(V) $, который имеет множество вершин $V$, может считаться комплект пар типа $е = (а, b) $, где $а, b$ являются элементами множества $V$, и они определяют соединённые вершины. Каждая пара $е = (а, b$) является ребром графа. Множество $U$ определяется как множество рёбер $е$ графа, а вершины $а$ и $b$ будут конечными точками ребра $е$.

Графы как структурированные данные

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

• Начальные компоненты.
• Выработанные компоненты.
• Компоненты, являющиеся аналогами (подобные).

Главные понятия теории графов

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

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