ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В СФЕРЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

АННОТАЦИЯ

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

ABSTRACT

The article considers the application of the graph theory in the sphere of information technologies and use of basic problems of graph theory in programming.

Ключевые слова: теория графов, применение графов, использование основных проблем теории графов.

Keywords: graph theory, the application of the graph theory, use of basic problems of graph theory in programming.

Введение

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

Кратко о теории графов

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

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

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

Рисунок 1. Пример простого графа

Степень вершины графа - количество ребер, входящих или исходящих из вершины [4].

Инварианты - для применения теоретических проблем теории графов в практических задачах, графовые инварианты сопоставляются с реальными проблемами. Инварианты - это свойства графа, такие как вершины, ребра, диаметр и степень [5].

Подграфы - это граф, вершины и ребра которого, являются подмножествами другого графа [6].

Случайные графы - это граф, свойства которого, такие как число вершин и ребер и связи между ними определены случайным образом [7].

Рисунок 2. Примеры случайных графов с 10 вершинами

Примеры использования теории графов

Теория графов нашла свое применение во многих сферах информационных технологий, рассмотрим наиболее классические примеры.

1. Социальные сети - где пользователя можно представить как вершину, а его подписки на другие аккаунты и сообщества, отмеченных друзей на фотографиях и в записях и прочие активности, как ребра, соединяющие его с другими пользователями [3].
2. Навигаторы и интернет карты - различные места или текущее местоположение пользователя можно представить как вершины графа, а соединяющие их дороги, как ребра графа. Благодаря такому подходу реализуется алгоритм построения кратчайшего пути [3].
3. Механизм рекомендаций на различных сайтах - теория графов здесь используется для поиска объектов, статей или событий, которые могут заинтересовать пользователя, опираясь на его предыдущие действия. К примеру, последний просмотренный товар в интернет магазине и товар их рекомендации - это две вершины графа, а их схожие характеристики - это ребро, которое их соединяет  [3].

Использование основных проблем теории графов в программировании

Инварианты графа действуют, как мост между наукой и инженерией как инструмент поддержки или вычислительные техники, особенно в области химии, электроники,  компьютеров и телекоммуникационной инженерии [5].

Вложенные графы и массивы графов - суть проблемы в том, как встроить один граф в другой с сохранением расстояний и прочих инвариантов, при этом минимизировав степень вершины графа. Например, визуализацию и представление массивных наборов данных можно рассматривать как проецирование большого графа на небольшой выбранный граф. Обратная задача построения графа из его проекций имеет приложения, среди прочего, в управлении памятью, вычислительной биологии и интернет-томографии [2].

Случайные графы - достигнутый прогресс в понимании случайных графов, пороговых функций и их поведении позволил ответить на вопросы вывода одного свойства графа из другого, и, в частности, как можно управлять поведением графа с помощью его основных инвариантов. Ответы на такие основные вопросы являются одними из основных инструментов разработки и анализа рандомизированных алгоритмов и алгоритмов аппроксимации [2].

Массивные графы - данные графы во многом схожи с разреженными случайными графами, но есть и различия. Так реалистичные массивные графы служат испытательным стендом для моделирования и анализа графов [2].

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

Заключение

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

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

1. Baeldung: Combinatorial Optimization / [Электронный ресурс]. - Режим доступа: URL: https://www.baeldung.com/cs/combinatorial-optimization-problems-methods (дата обращения 31.01.2023)
2. Discrete Mathematics for Information Technology: сб. ст. for DMS workshop "Intellecual Opportunities in the Mathematicl Sciences" —  Ирвин, 2000. — 300 c. https://mathweb.ucsd.edu/~fan/research/it2.html (дата обращения 31.01.2023)
3. GeeksforGeeks: A computer science portal for geeks / [Электронный ресурс]. - Режим доступа: URL: https://www.geeksforgeeks.org/mathematics-graph-theory-basics-set-1/ (дата обращения 31.01.2023)
4. Graph Online: Степень вершин / [Электронный ресурс]. - Режим доступа: URL: https://graphonline.ru/wiki/%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0/%D0%A0%D0%B0%D1%81%D1%87%D0%B5%D1%82%D0%A1%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D0%B8%D0%92%D0%B5%D1%80%D1%88%D0%B8%D0%BD (дата обращения 31.01.2023)
5. Hindawi: Mathematical Problems in Engineering / [Электронный ресурс]. - Режим доступа: URL: https://www.hindawi.com/journals/mpe/si/954839/ (дата обращения 31.01.2023)
6. NIST: National Institute of Standards and Technology / [Электронный ресурс]. - Режим доступа: URL: https://xlinux.nist.gov/dads/HTML/subgraph.html#:~:text=(definition),are%20subsets%20of%20another%20graph (дата обращения 31.01.2023)
7. Wolfram MathWorld: the web’'s most extensive mathematics resource / [Электронный ресурс]. - Режим доступа: URL: https://mathworld.wolfram.com/RandomGraph.html#:~:text=A%20random%20graph%20is%20a,edge%20probabilities%20distributed%20uniformly%20in%20 (дата обращения 31.01.2023).