Алгебра графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 7: Строка 7:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Одиночный граф''' (англ. ''singleton graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex>
+
'''Одиночный граф''' (англ. ''singleton graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex>
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 15: Строка 15:
 
* '''Сложение'''(англ. ''overlay''): <tex>G_1 + G_2 = \{V_1 \cup V_2, E_1 \cup E_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>
 
* '''Соединеие'''(англ. ''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войства операций ==  
 
== Cвойства операций ==  
Строка 48: Строка 43:
 
Левая часть:
 
Левая часть:
  
<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, 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>
  
 
Правая часть:
 
Правая часть:
Строка 66: Строка 61:
 
Правая часть:
 
Правая часть:
  
<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>
+
<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>
  
 
Правая дистрибутивность доказывается аналогично.
 
Правая дистрибутивность доказывается аналогично.
 
}}
 
}}
 +
 +
 
* ''Декомпозиция:''
 
* ''Декомпозиция:''
 
{{Утверждение
 
{{Утверждение
Строка 81: Строка 78:
  
 
<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>
 
<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>
 +
}}
 +
 +
 +
{{Утверждение
 +
|statement=Любой граф <tex>G = \{V, E\}</tex> можно представить в виде композиции сложений и соединений.
 +
|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>, где <tex>\sum</tex> обозначает суммирование при помощи ранее определенной операции сложения.
 
}}
 
}}
 
== Применения ==
 
== Применения ==
Строка 86: Строка 89:
 
Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
 
Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
  
Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в приныпе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательных операций из просевших графов, то почти все проблемы связанные с построением графа и проверкой его корректности устраняются.  
+
Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций алгебры из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.  
  
Подробная реализация на языке Haskell может быть найдена в этой статье.<ref>[https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]</ref>
+
Подробная реализация на языке Haskell может быть найдена в статье.<ref>[https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]</ref>
 
== См. также ==
 
== См. также ==
 
* [[Основные определения теории графов]]
 
* [[Основные определения теории графов]]

Версия 22:47, 18 декабря 2017

Алгебра графов (англ. Graph algebra) — способ построить на пространстве ориентированных графов алгебраическую структуру. Впервые такая возможность была продемонстрирована McNulty и George F. в 1983 году.[1]

Основные определения

Определение:
Пустой граф (англ. empty graph) — граф в котором нет вершин и ребер. Здесь и далее будем обозначать его как [math]\varepsilon[/math]. То есть [math]\varepsilon = \{\varnothing, \varnothing\}[/math].


Определение:
Одиночный граф (англ. singleton graph) — граф состоящий из одной вершины. Здесь и далее будем обозначать его строчной буквой. То есть [math] a = \{a, \varnothing \}[/math]


Определение:
Алгеброй графов (англ. algebra of graphs) называется множество ориентированных графов с двумя определенными на нем операциями.

Пусть [math]G_1 = \{V_1, E_1\}[/math] и [math]G_2 = \{V_2, E_2\}[/math]. Тогда [math]\forall G_1, G_2[/math]

  • Сложение(англ. overlay): [math]G_1 + G_2 = \{V_1 \cup V_2, E_1 \cup E_2\}[/math]
  • Соединеие(англ. connect): [math] G_1 \rightarrow G_2 = \{V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2\}[/math]

Cвойства операций

Данные операции обладают следующими свойствами очевидными из определения

Сложение

  • Наличие нейтрального элемента
Утверждение:
[math]G + \varepsilon = G[/math]
  • Коммутативность:
Утверждение:
[math]G_1 + G_2 = G_2 + G_1[/math]
  • Aссоциативность:
Утверждение:
[math]G_1 + (G_2 + G_3) = (G_1 + G_2) + G_3[/math]

Соединение

  • Наличие левого и правого нейтральных элементов:
Утверждение:
[math]\varepsilon \rightarrow G = G \\G \rightarrow \varepsilon = G[/math]
  • Ассоциативность:
Утверждение:
[math]G_1 \rightarrow (G_2 \rightarrow G_3) = (G_1 \rightarrow G_2) \rightarrow G_3[/math]
[math]\triangleright[/math]

Левая часть:

[math]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)[/math]

Правая часть:

[math](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)[/math]
[math]\triangleleft[/math]

Другие свойства

  • Левая и правая дистрибутивность:
Утверждение:
[math]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[/math]
[math]\triangleright[/math]

Левая часть:

[math]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)[/math]

Правая часть:

[math]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))[/math]

Правая дистрибутивность доказывается аналогично.
[math]\triangleleft[/math]


  • Декомпозиция:
Утверждение:
[math]G_1 \rightarrow G_2 \rightarrow G_3 = G_1 \rightarrow G_2 + G_1 \rightarrow G_3 + G_2 \rightarrow G_3[/math]
[math]\triangleright[/math]

Левая часть:

[math]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)[/math]

Правая часть:

[math]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)[/math]
[math]\triangleleft[/math]


Утверждение:
Любой граф [math]G = \{V, E\}[/math] можно представить в виде композиции сложений и соединений.
[math]\triangleright[/math]
Действительно, [math]G = \sum_{(u, v\in V)}u \rightarrow v[/math], где [math]\sum[/math] обозначает суммирование при помощи ранее определенной операции сложения.
[math]\triangleleft[/math]

Применения

Построение графов в функциональных языках

Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.

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

Подробная реализация на языке Haskell может быть найдена в статье.[2]

См. также

Примечания

Источники информации