1632
правки
Изменения
м
== Применения ===== Построение графов в функциональных языках ===
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее для удобства будем обозначать и одиночный граф и множество его как просто строчной вершин одной буквой. То есть Например, <tex> a = \{a, \varnothing \}</tex>{{---}} граф содержащий толко одну вершину <tex>a</tex>.
}}
{{Определение
'''Алгеброй графов''' (англ. ''algebra of graphs'') называется множество ориентированных графов с двумя определенными на нем операциями.
Пусть <tex>G_1 = \{V_1, E_1\}</tex> и <tex>G_2 = \{V_2, E_2\}</tex>. Тогда <tex>\forall G_1, G_2</tex>
* '''Сложение'''(англ. ''overlay''): <tex>G_1 + G_2 = \{V_1 \cup V_2, E_1 \cup E_2\}</tex>* '''СоединеиеСоединение'''(англ. ''connect''): <tex> G_1 \rightarrow G_2 = \{V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2\}</tex>
}}
== Cвойства операций ==
Данные операции обладают следующими свойствами очевидными из определения.
=== Сложение ===
* Наличие нейтрального элемента
{{Утверждение
|statement=Любой граф <tex>G = \{V, E\}</tex> можно представить в виде композиции сложений и соединений.
|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>, где <tex>\sum</tex> это послузовательное послeдовательное применение операции сложения графов.
}}
Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде. Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
Подробная реализация на языке <tex>\mathrm{Haskell}</tex><ref>[https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]</ref>.
== См. также ==
* [[Основные определения теории графов]]
* [https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/ Graphs à la carte {{---}} "no time" Andrey Mokhov's blog]
[[Категория: Теория Алгоритмы и структуры данных]][[Категория: Основные определения теории графов]]
