Алгебра графов - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:22:02Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:22, 1 сентября 2022

2022-09-01T05:22:59Z

176.101.2.153: Была опечатка

2019-08-08T17:49:35Z

Была опечатка

Gpevnev в 22:11, 18 декабря 2017

2017-12-18T22:11:29Z

Gpevnev в 22:03, 18 декабря 2017

2017-12-18T22:03:57Z

Gpevnev в 21:59, 18 декабря 2017

2017-12-18T21:59:22Z

Gpevnev в 21:43, 18 декабря 2017

2017-12-18T21:43:51Z

Gpevnev в 21:42, 18 декабря 2017

2017-12-18T21:42:04Z

Gpevnev в 21:39, 18 декабря 2017

2017-12-18T21:39:50Z

Gpevnev в 21:36, 18 декабря 2017

2017-12-18T21:36:26Z

@@ Строка 1: / Строка 1: @@
 '''Алгебра графов''' (англ. ''algebra of graphs'')  {{---}} способ построить на пространстве [[Основные определения теории графов#Ориентированные графы | ориентированных графов]] алгебраическую структуру. Впервые такая возможность была продемонстрирована McNulty и George F. в 1983 году.<ref>[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.]</ref>
 == Основные определения ==
@@ Строка 28: / Строка 7: @@
 {{Определение
 |definition=
-'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее  для удобства будем обозначать и одиночный граф и множество его вершин одной буквой. Например, <tex> a = \{a, \varnothing \}</tex> {{---}} граф содержащий толко одну вершину <tex>a</tex>.
+'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее  для удобства будем обозначать и одиночный граф и множество его вершин одной буквой. Например, <tex> a = \{a, \varnothing \}</tex> {{---}} граф содержащий толко одну вершину <tex>a</tex>.
 }}
 {{Определение
@@ Строка 108: / Строка 87: @@
 Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
-Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
+Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
 Подробная реализация на языке <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>.

@@ Строка 1: / Строка 1: @@
 '''Алгебра графов''' (англ. ''algebra of graphs'')  {{---}} способ построить на пространстве [[Основные определения теории графов#Ориентированные графы | ориентированных графов]] алгебраическую структуру. Впервые такая возможность была продемонстрирована McNulty и George F. в 1983 году.<ref>[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.]</ref>
 == Основные определения ==
@@ Строка 7: / Строка 28: @@
 {{Определение
 |definition=
-'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее  для удобства будем обозначать и одиночный граф и множество его вершин одной буквой. Например, <tex> a = \{a, \varnothing \}</tex> {{---}} граф содержащий толко одну вершину <tex>a</tex>.
+'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее  для удобства будем обозначать и одиночный граф и множество его вершин одной буквой. Например, <tex> a = \{a, \varnothing \}</tex> {{---}} граф содержащий толко одну вершину <tex>a</tex>.
 }}
 {{Определение
@@ Строка 87: / Строка 108: @@
 Построенная нами алгебраическая структура очень полезна для использования в функциональных языках программирования. До введения понятия алгебры графов работа с ними в функциональных языках была очень неудобна и часто порождало ошибки.
-Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
+Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
 Подробная реализация на языке <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>.

@@ Строка 14: / Строка 14: @@
 Пусть <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>
+* '''Соединение''' (англ. ''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войства операций ==
 Данные операции обладают следующими свойствами очевидными из определения.

@@ Строка 7: / Строка 7: @@
 {{Определение
 |definition=
-'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex> или граф содержащий толко одну вершину <tex>a</tex>.
+'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее  для удобства будем обозначать и одиночный граф и множество его вершин одной буквой. Например, <tex> a = \{a, \varnothing \}</tex> {{---}} граф содержащий толко одну вершину <tex>a</tex>.
 }}
 {{Определение

@@ Строка 7: / Строка 7: @@
 {{Определение
 |definition=
-'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex>
+'''Одиночный граф''' (англ. ''single graph'') {{---}} [[Основные определения теории графов#Ориентированные графы|граф]] состоящий из одной вершины. Здесь и далее будем обозначать его как просто строчной буквой. То есть <tex> a = \{a, \varnothing \}</tex> или граф содержащий толко одну вершину <tex>a</tex>.
 }}
 {{Определение
@@ Строка 17: / Строка 17: @@
 }}
 == Cвойства операций ==
-Данные операции обладают следующими свойствами очевидными из определения
+Данные операции обладают следующими свойствами очевидными из определения.
 === Сложение ===
 * Наличие нейтрального элемента

@@ Строка 81: / Строка 81: @@
 {{Утверждение
 |statement=Любой граф <tex>G = \{V, E\}</tex> можно представить в виде композиции сложений и соединений.
-|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>, где <tex>\sum</tex> это послузовательное применение операции сложения графов.
+|proof=Действительно, <tex>G = \sum_{(u, v\in V)}u \rightarrow v</tex>, где <tex>\sum</tex> это послeдовательное применение операции сложения графов.
 }}
 == Построение графов в функциональных языках ==
@@ Строка 88: / Строка 88: @@
 Дело в том, что способ представления в виде списка смежности либо матрицы смежности, широко используемых в императивных программах, оказался очень тяжело применим в функциональной среде.  Компилятор при представлении графа в виде списка не может проверить, ни его корректность в принципе, ни корректность совершения некоторой операции над ним. Но если представить граф в виде последовательности операций из простейших графов, то почти все проблемы, связанные с построением графа и проверкой его корректности, устраняются.
-Подробная реализация на языке <tex>Haskell</tex><ref>[https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ An algebra of graphs {{---}} "no time" Andrey Mokhov's blog]</ref>.
+Подробная реализация на языке <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>.
 == См. также ==
 * [[Основные определения теории графов]]

← Предыдущая		Версия 21:39, 18 декабря 2017
Строка 103:		Строка 103:
	* [https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/ Graphs à la carte {{---}} "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]

−	[[Категория: ~~Теория~~ графов]]	+	[[Категория: Алгоритмы и структуры данных]]
		+	[[Категория: Основные определения теории графов]]