Ориентированный граф - История изменений

Proshev: Перенаправление на Основные определения теории графов#Ориентированные графы

2012-01-18T00:40:39Z

Перенаправление на Основные определения теории графов#Ориентированные графы

Proshev в 18:28, 17 января 2012

2012-01-17T18:28:47Z

Proshev в 18:27, 17 января 2012

2012-01-17T18:27:44Z

Proshev в 01:12, 17 января 2012

2012-01-17T01:12:25Z

Proshev: /* Матрица и списки смежности */

2011-10-22T17:03:32Z

‎Матрица и списки смежности

Proshev в 17:01, 22 октября 2011

2011-10-22T17:01:00Z

Proshev: /* Матрица инцидентности */

2011-10-22T16:56:34Z

‎Матрица инцидентности

Proshev: /* Матрица инцидентности */

2011-10-22T16:55:58Z

‎Матрица инцидентности

Proshev: /* Матрица инцидентности */

2011-10-22T16:54:04Z

‎Матрица инцидентности

Proshev в 16:36, 22 октября 2011

2011-10-22T16:36:02Z

← Предыдущая		Версия 00:40, 18 января 2012
Строка 1:		Строка 1:
−	~~'''Слито со статьей [[Основные определения теории графов]]'''~~	+	#REDIRECT [[Основные определения теории графов#Ориентированные графы]]
−
−	~~== Основные определения ==~~
−
−	~~{{Определение~~
−	~~\|definition =~~
−	'''Ориентированный граф (directed graph) <tex> G </tex>''' - это пара <tex> G = (V, E) </tex>, где <tex>V</tex> - конечное множество вершин, а <tex>E \subset V \times V </tex> - множество рёбер. Ребро обозначается как пара вершин <tex>(v, u)</tex>, где <tex>v</tex> - начало ребра, а <tex>u</tex> - конец. Причём <tex>(v, u) \ne (u, v)</tex>.
−	}}
−
−	~~{{Определение~~
−	~~\|definition =~~
−	~~Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>begin, end: E \to V</tex>.~~
−	}}
−
−	Для ориентированного графа справедлива [[Лемма о рукопожатиях\|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#~~Степень вершины\|степеней вершин]].~~
−
−
−	~~{{Определение~~
−	~~\|definition =~~
−	~~Ребро ориентированного графа называется '''дугой (arc)'''.~~
−	}}
−
−	~~== Представление ==~~
−
−	~~=== Матрица и списки смежности ===~~
−
−	Ориентированный граф можно представить в виде [[Матрица смежности графа\|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра).
−	Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей\|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
−
−	Если граф разрежен (<tex>\|E\| < \|V^2\|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
−
−	~~=== Матрица инцидентности ===~~
−
−	Имеет место и другое представление графа - [[Матрица инцидентности графа\|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:
−	~~# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>.~~
−	~~# В остальных случаях ячейки матрицы равны 0.~~
−
−	~~== Источник ==~~
−	* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
−
−	~~== См. также ==~~
−	*[[Основные определения теории графов]]
−
−	~~[[Категория: Удалить~~]]

← Предыдущая		Версия 18:28, 17 января 2012
Строка 1:		Строка 1:
−	Слито со статьей [[Основные определения теории графов]]	+	'''Слито со статьей [[Основные определения теории графов]]'''

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

@@ Строка 1: / Строка 1: @@
 == Основные определения ==
@@ Строка 40: / Строка 42: @@
 *[[Основные определения теории графов]]
-[[Категория: Алгоритмы и структуры данных]]
+[[Категория: Удалить]]

@@ Строка 38: / Строка 38: @@
 == См. также ==
-*[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+*[[Основные определения теории графов]]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Основные определения теории графов]]

@@ Строка 26: / Строка 26: @@
 Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
-Если граф разрежен, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
+Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
 === Матрица инцидентности ===

@@ Строка 33: / Строка 33: @@
 # <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>.
 # В остальных случаях ячейки матрицы равны 0.
 == См. также ==

@@ Строка 31: / Строка 31: @@
 Имеет место и другое представление графа -  [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:
-# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = beg ej \wedge u = end ej</tex>
+# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>
-# <tex>graph[v][numberOfArc] = 0 \wedge graph[u][numberOfArc] = 0 \Leftrightarrow (v, u) \notin E</tex>.
+# В остальных случаях ячейки матрицы равны 0.
 == См. также ==

@@ Строка 8: / Строка 8: @@
 {{Определение
 |definition =
-Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>beg, end: E \to V</tex>.
+Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>begin, end: E \to V</tex>.
 }}
@@ Строка 23: / Строка 23: @@
 === Матрица и списки смежности ===
-Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра либо их количество, если в нашем графе разрешены паралелльные ребра.
+Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра).
 Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
-Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память.
+Если граф разрежен, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
 === Матрица инцидентности ===