162
правки
Изменения
Новая страница: «'''Алгебра графов''' (англ. ''Graph algebra'') {{---}} способ построить на пространстве [[Основные опре...»
'''Алгебра графов''' (англ. ''Graph algebra'') {{---}} способ построить на пространстве [[Основные определения теории графов#Ориентированные графы | ориентированных графов]] алгебраическую структуру. Впервые такая возможность была продемонстрирована McNulty и George F. [https://www.researchgate.net/publication/225490641_Inherently_nonfinitely_based_finite_algebras в работе "Inherently nonfinitely based finite algebras"] в 1983 году.
== Основные определения ==
{{Определение
|definition=
'''Пустой граф''' (англ. ''empty graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] в котором нет вершин и ребер. Здесь и далее будем обозначать его как <tex>\varepsilon</tex>. То есть <tex>\varepsilon = \{\varnothing, \varnothing\}</tex>.
}}
{{Определение
|definition=
'''Одиночный граф''' (англ. ''singleton graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex>
}}
{{Определение
|definition=
'''Алгеброй графов''' (англ. ''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>
}}
{{Утверждение
|statement=Любой граф <tex>G = \{V, E\}</tex> можно представить в виде последовательности применения операций сложения и соединения.
|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>
}}
== Cвойства операций ==
Данные операции обладают следующими свойствами очевидными из определения
=== Сложение ===
* Наличие нейтрального элемента
{{Утверждение
|statement=<tex>G + \varepsilon = G</tex>
}}
* ''Коммутативность:''
{{Утверждение
|statement=<tex>G_1 + G_2 = G_2 + G_1</tex>
}}
* ''Aссоциативность:''
{{Утверждение
|statement=<tex>G_1 + (G_2 + G_3) = (G_1 + G_2) + G_3</tex>
}}
=== Соединение ===
* ''Наличие левого и правого нейтральных элементов:''
{{Утверждение
|statement=<tex>\varepsilon \rightarrow G = G \\G \rightarrow \varepsilon = G</tex>
}}
* ''Ассоциативность:''
{{Утверждение
|statement=<tex>G_1 \rightarrow (G_2 \rightarrow G_3) = (G_1 \rightarrow G_2) \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow (G_2 \rightarrow G_3) = (V_1, E_1) \rightarrow ((V_2, E_2) \rightarrow (V_3, E_3)) = (V_1, E_1) \rightarrow (V_2 \cup V_3, E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_2 \times V_3 \cup V_1 \times (V_2 \cup V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_2 \times V_3 \cup V_1 \times V_2 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
Правая часть:
<tex>(G_1 \rightarrow G_2) \rightarrow G_3 = ((V_1, E_1) \rightarrow (V_2, E_2)) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_3 \cup (V_1 \cup V_2) \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
}}
=== Другие свойства ===
* ''Левая и правая дистрибутивность:''
{{Утверждение
|statement= <tex>G_1 \rightarrow (G_2 + G_3) = G_1 \rightarrow G_2 + G_1\rightarrow G_3 \\ (G_1 + G_2) \rightarrow G_3 = G_1 \rightarrow G_3 + G_2 \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow (G_2 + G_3) = (V_1, E_1) \rightarrow ((V_2, E_2) + (V_3, E_3)) = (V_1, E_1) \rightarrow (V_2 \cup V_3, E_2 \cup E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times (V_2 \cup V_3)</tex>
Правая часть:
<tex>G_1 \rightarrow G_2 + G_1 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) + (V_1, E_1) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) + (V_1 \cup V_3, E_1 \cup E_3 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_1 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_1 \cup E_3 \cup V_1 \times V_3 = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times (V_2 \cup V_3))</tex>
Правая дистрибутивность доказывается аналогично.
}}
* ''Декомпозиция:''
{{Утверждение
|statement=<tex>G_1 \rightarrow G_2 \rightarrow G_3 = G_1 \rightarrow G_2 + G_1 \rightarrow G_3 + G_2 \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow G_2 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_3 \cup (V_1 \cup V_2) \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
Правая часть:
<tex>G_1 \rightarrow G_2 + G_1 \rightarrow G_3 + G_2 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) + (V_1, E_1) \rightarrow (V_3, E_3) + (V_2, E_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) + (V_1 \cup V_3, E_1 \cup E_3 \cup V_1 \times V_3) + (V_2 \cup V_3, E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_1 \cup V_3 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_1 \cup E_3 \cup V_1 \times V_3 \cup E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
}}
== Применения ==
=== Построение графов в функциональных языках ===
Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде. Компилятор при представлении графа в виде списка не может проверить, ни его корректность в приныпе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательных операций из просевших графов, то почти все проблемы связанные с построением графа и проверкой его корректности устраняются.
Подробная реализация на языке Haskell может быть [https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ найдена в этой статье.]
== См. также ==
* [[Основные определения теории графов]]
== Источники информации ==
* [https://www.researchgate.net/publication/225490641_Inherently_nonfinitely_based_finite_algebras McNulty, George F.; Shallon, Caroline R. (1983), "Inherently nonfinitely based finite algebras", Universal algebra and lattice theory (Puebla, 1982), Lecture Notes in Math., 1004, Berlin, New York: Springer-Verlag, pp. 206–231 ]
* [https://www.staff.ncl.ac.uk/andrey.mokhov/algebra.pdf Algebra of Parameterised Graphs {{---}} Andrey Mokhov, Victor Khomenko, Newcastle University UK, ACM Transactions on Embedded Computing Systems, Vol. 1, No. 1, Article 1, Publication date: January 2014 .]
* [https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]
* [https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/ Graphs à la carte {{---}} "no time" Andrey Mokhov's blog]
[[Категория: Теория графов]]
== Основные определения ==
{{Определение
|definition=
'''Пустой граф''' (англ. ''empty graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] в котором нет вершин и ребер. Здесь и далее будем обозначать его как <tex>\varepsilon</tex>. То есть <tex>\varepsilon = \{\varnothing, \varnothing\}</tex>.
}}
{{Определение
|definition=
'''Одиночный граф''' (англ. ''singleton graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex>
}}
{{Определение
|definition=
'''Алгеброй графов''' (англ. ''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>
}}
{{Утверждение
|statement=Любой граф <tex>G = \{V, E\}</tex> можно представить в виде последовательности применения операций сложения и соединения.
|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>
}}
== Cвойства операций ==
Данные операции обладают следующими свойствами очевидными из определения
=== Сложение ===
* Наличие нейтрального элемента
{{Утверждение
|statement=<tex>G + \varepsilon = G</tex>
}}
* ''Коммутативность:''
{{Утверждение
|statement=<tex>G_1 + G_2 = G_2 + G_1</tex>
}}
* ''Aссоциативность:''
{{Утверждение
|statement=<tex>G_1 + (G_2 + G_3) = (G_1 + G_2) + G_3</tex>
}}
=== Соединение ===
* ''Наличие левого и правого нейтральных элементов:''
{{Утверждение
|statement=<tex>\varepsilon \rightarrow G = G \\G \rightarrow \varepsilon = G</tex>
}}
* ''Ассоциативность:''
{{Утверждение
|statement=<tex>G_1 \rightarrow (G_2 \rightarrow G_3) = (G_1 \rightarrow G_2) \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow (G_2 \rightarrow G_3) = (V_1, E_1) \rightarrow ((V_2, E_2) \rightarrow (V_3, E_3)) = (V_1, E_1) \rightarrow (V_2 \cup V_3, E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_2 \times V_3 \cup V_1 \times (V_2 \cup V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_2 \times V_3 \cup V_1 \times V_2 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
Правая часть:
<tex>(G_1 \rightarrow G_2) \rightarrow G_3 = ((V_1, E_1) \rightarrow (V_2, E_2)) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_3 \cup (V_1 \cup V_2) \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
}}
=== Другие свойства ===
* ''Левая и правая дистрибутивность:''
{{Утверждение
|statement= <tex>G_1 \rightarrow (G_2 + G_3) = G_1 \rightarrow G_2 + G_1\rightarrow G_3 \\ (G_1 + G_2) \rightarrow G_3 = G_1 \rightarrow G_3 + G_2 \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow (G_2 + G_3) = (V_1, E_1) \rightarrow ((V_2, E_2) + (V_3, E_3)) = (V_1, E_1) \rightarrow (V_2 \cup V_3, E_2 \cup E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times (V_2 \cup V_3)</tex>
Правая часть:
<tex>G_1 \rightarrow G_2 + G_1 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) + (V_1, E_1) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) + (V_1 \cup V_3, E_1 \cup E_3 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_1 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_1 \cup E_3 \cup V_1 \times V_3 = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times (V_2 \cup V_3))</tex>
Правая дистрибутивность доказывается аналогично.
}}
* ''Декомпозиция:''
{{Утверждение
|statement=<tex>G_1 \rightarrow G_2 \rightarrow G_3 = G_1 \rightarrow G_2 + G_1 \rightarrow G_3 + G_2 \rightarrow G_3</tex>
|proof=
Левая часть:
<tex>G_1 \rightarrow G_2 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_3 \cup (V_1 \cup V_2) \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
Правая часть:
<tex>G_1 \rightarrow G_2 + G_1 \rightarrow G_3 + G_2 \rightarrow G_3 = (V_1, E_1) \rightarrow (V_2, E_2) + (V_1, E_1) \rightarrow (V_3, E_3) + (V_2, E_2) \rightarrow (V_3, E_3) = (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2) + (V_1 \cup V_3, E_1 \cup E_3 \cup V_1 \times V_3) + (V_2 \cup V_3, E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_1 \cup V_3 \cup V_2 \cup V_3, E_1 \cup E_2 \cup V_1 \times V_2 \cup E_1 \cup E_3 \cup V_1 \times V_3 \cup E_2 \cup E_3 \cup V_2 \times V_3) = (V_1 \cup V_2 \cup V_3, E_1 \cup E_2 \cup E_3 \cup V_1 \times V_2 \cup V_1 \times V_3 \cup V_2 \times V_3)</tex>
}}
== Применения ==
=== Построение графов в функциональных языках ===
Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде. Компилятор при представлении графа в виде списка не может проверить, ни его корректность в приныпе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательных операций из просевших графов, то почти все проблемы связанные с построением графа и проверкой его корректности устраняются.
Подробная реализация на языке Haskell может быть [https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ найдена в этой статье.]
== См. также ==
* [[Основные определения теории графов]]
== Источники информации ==
* [https://www.researchgate.net/publication/225490641_Inherently_nonfinitely_based_finite_algebras McNulty, George F.; Shallon, Caroline R. (1983), "Inherently nonfinitely based finite algebras", Universal algebra and lattice theory (Puebla, 1982), Lecture Notes in Math., 1004, Berlin, New York: Springer-Verlag, pp. 206–231 ]
* [https://www.staff.ncl.ac.uk/andrey.mokhov/algebra.pdf Algebra of Parameterised Graphs {{---}} Andrey Mokhov, Victor Khomenko, Newcastle University UK, ACM Transactions on Embedded Computing Systems, Vol. 1, No. 1, Article 1, Publication date: January 2014 .]
* [https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]
* [https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/ Graphs à la carte {{---}} "no time" Andrey Mokhov's blog]
[[Категория: Теория графов]]
