Викиконспекты - Вклад участника [ru]

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

2014-09-23T14:39:50Z

79.134.198.186: /* Часто используемые графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Данное определение разрешает соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Граф с кратными рёбрами принято называть '''мультиграфом''' (англ. ''multigraph''). Если в мультиграфе присутствуют петли, то такой граф называют '''псевдографом''' (англ. ''pseudograph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' (англ. ''length'') пути.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}
{{Определение
|definition=
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
}}

{{main|Гамильтоновы графы}}
{{Определение
|definition=
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
}}

{{main|Укладка графа на плоскости}}
{{Определение
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
}}

{{main|Лемма о безопасном ребре}}
{{Определение
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T10:00:49Z

79.134.198.186: /* Часто используемые графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' (англ. ''length'') пути.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}
{{Определение
|definition=
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
}}

{{main|Гамильтоновы графы}}
{{Определение
|definition=
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
}}

{{main|Укладка графа на плоскости}}
{{Определение
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
}}

{{Определение
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T09:56:05Z

79.134.198.186: /* Пути в графах */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' (англ. ''length'') пути.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

{{main|Эйлеров цикл, Эйлеров_путь, Эйлеровы графы, Эйлеровость_орграфов}}
{{Определение
|definition=
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
}}

{{main|Гамильтоновы графы}}
{{Определение
|definition=
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
}}

{{main|Укладка графа на плоскости}}
{{Определение
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
}}

{{Определение
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T09:54:14Z

79.134.198.186: /* Часто используемые графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' (англ. ''length'') {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

{{main|Эйлеров цикл, Эйлеров_путь, Эйлеровы графы, Эйлеровость_орграфов}}
{{Определение
|definition=
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
}}

{{main|Гамильтоновы графы}}
{{Определение
|definition=
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
}}

{{main|Укладка графа на плоскости}}
{{Определение
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
}}

{{Определение
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T09:36:51Z

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

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' (англ. ''length'') {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T08:49:43Z

79.134.198.186:

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \bmod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' (англ. ''length'') {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2014-09-23T08:16:52Z

79.134.198.186: /* Неориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''''Неориентированным графом''''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф разрежен (англ. ''sparse graph'', <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]

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

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

2014-09-23T08:14:11Z

79.134.198.186: /* Ориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом''' (англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф разрежен (англ. ''sparse graph'', <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]

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

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

2014-09-23T07:42:00Z

79.134.198.186: /* Часто используемые графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей (англ. ''loop'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные''' (англ. ''adjacent'')
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>

'''Инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>. Такой граф иногда называют '''псевдографом''' (англ. ''pseudograph'').
}}
В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом'''.
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

Также для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e~|~\operatorname{beg}~e = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e~|~\operatorname{end}~e = v_i\}|</tex>.

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф разрежен (англ. ''sparse graph'', <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' {{---}} связный ациклический граф.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]

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

Список

2014-06-12T16:21:54Z

79.134.198.186: /* Поиск длины хвоста в списке с циклом */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(Node thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node search('''int''' value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(Node thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' hasCycle(Node head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex> (так как <tex>2</tex> (скорость зайца) <tex>- 1</tex> (скорость черепахи) <tex>= 1</tex>), что гарантирует их встречу за конечное время.
==Поиск длины хвоста в списке с циклом==
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её <tex>pointMeeting</tex>.
===Наивные реализации===
====Реализация за <tex>O(n^2)</tex>====
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от текущего элемента вперёд указатель. Если он окажется в текущем элементе, прежде чем два раза посетит <tex>pointMeeting</tex>, то точку окончания (начала) хвоста нашли.
====Реализация за <tex>O(n \log n)</tex>====
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем 2 шага вперёд, потом 4, потом 8 и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.
===Эффективная реализация===
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(Node head, Node pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
====Доказательство корректности алгоритма====
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.
Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка.

Node reverse(Node current, Node prev):
'''if''' current == ''NULL''
'''return''' prev
next = current.next
current.next = prev
'''return''' reverse(next, current)

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели <tex>next</tex> изменят свое направление, не нарушив связности самого списка.

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-12T15:09:04Z

79.134.198.186:

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(Node thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node search('''int''' value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(Node thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' hasCycle(Node head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex> (так как <tex>2</tex> (скорость зайца) <tex>- 1</tex> (скорость черепахи) <tex>= 1</tex>), что гарантирует их встречу за конечное время.
==Поиск длины хвоста в списке с циклом==
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её <tex>pointMeeting</tex>.
===Реализация за <tex>O(n^2)</tex>===
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от текущего элемента вперёд указатель. Если он окажется в текущем элементе, прежде чем два раза посетит <tex>pointMeeting</tex>, то точку окончания (начала) хвоста нашли.
'''int''' getTail(Node head, Node pointMeeting):
lengthTail = 0
currentElement = head
'''while''' true
iterator = currentElement.next
count = 0
'''while''' iterator != currentElement '''and''' count != 2
'''if''' iterator == pointMeeting
count++
iterator = iterator.next
'''if''' count < 2
'''break'''
currentElement = currentElement.next
lengthTail++
'''return''' lengthTail

===Реализация за <tex>O(n \log n)</tex>===
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем 2 шага вперёд, потом 4, потом 8 и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.
===Эффективная реализация===
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(Node head, Node pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
====Доказательство корректности алгоритма====
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.
Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка.

Node reverse(Node current, Node prev):
'''if''' current == ''NULL''
'''return''' prev
next = current.next
current.next = prev
'''return''' reverse(next, current)

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели <tex>next</tex> изменят свое направление, не нарушив связности самого списка.

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-12T13:32:14Z

79.134.198.186: /* Задача на поиск цикла в списке */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' hasCycle(Node head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(Node head, Node pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
'''return'''
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = current
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-12T13:30:57Z

79.134.198.186: /* Задача на поиск цикла в списке */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' hasCycle(head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
'''return'''
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = current
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-11T20:55:50Z

79.134.198.186: /* Задача на обращение списка */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCycle(head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
'''return'''
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = current
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-11T19:49:34Z

79.134.198.186: /* Задача на обращение списка */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCycle(head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача на обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
'''return'''
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = current
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-11T19:48:53Z

79.134.198.186: /* Задача на обращение списка */

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCycle(head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача на обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
return
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = current
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-11T19:48:18Z

79.134.198.186:

'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead):
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCycle(head):
tortoise = head
hare = head
'''repeat'''
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL''
'''return''' ''false''
tortoise = tortoise.next
hare = hair.next.next
'''until''' tortoise != hare
'''return''' ''true''

Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
'''while''' firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
'''return''' lengthTail
===Доказательство корректности алгоритма===
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):

<tex>f_1(n) = L + (n-L) \bmod N</tex>

<tex>f_2(n) = L + (2n-L) \bmod N</tex>

Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> - голова списка, <tex>X</tex> - точка встречи, <tex>A</tex> - первый элемент цикла, <tex>Q</tex> - расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:

<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>

<tex>Q = L + (1-k) N</tex>

Пусть <tex>L = p N + M, 0 <= M < N</tex>

Известно, что

<tex>L < k N \leqslant L + N</tex>

<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>

Подставив полученные значения, получим:
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.

==Задача на обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.

'''function''' reverse(head):
'''if''' head == ''NULL'' '''or''' head.next == ''NULL''
return
current = head
prev = ''NULL''
'''while''' current != ''NULL''
next = current.next
current.next = prev
prev = cur
current = next
head = prev

==См.также==
* [[Динамический массив]]

==Источники информации==
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-11T15:27:57Z

79.134.198.186: /* Задача на поиск цикла в списке */

Список

2014-06-11T15:20:54Z

79.134.198.186:

Список

2014-06-09T17:09:32Z

79.134.198.186:

Динамический массив

2014-06-09T16:58:16Z

79.134.198.186: /* Источники информации */

{{Определение
| definition =
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Динамический массив''' может изменять свой размер в зависимости от количества элементов в нём.
}}

== Операции ==
Определим операции, которые мы будем применять к динамическому массиву: 
=== get(i) ===
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения {{---}} <tex>O(1)</tex>.
=== set(i,x) ===
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив {{---}} <tex>O(n)</tex> (<tex>n</tex> {{---}} размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если количество элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> {{---}} константы, зависящие от реализации). Время выполнения операции в худшем случае {{---}} <tex>O(n)</tex>.

=== size() ===
:Возвращает количество элементов массива. Время выполнения {{---}} <tex>O(1)</tex>.

== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.
=== Метод предоплаты ===
==== Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex dpi=150>i</tex> и <tex dpi=150>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex dpi=150>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex dpi=150>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.
=== Метод потенциалов ===
За потенциал примем число:
<tex dpi=150>\Phi(c, s) = \begin{cases}
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex>

где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.

==== Стоимость операции '''add(x)''' ====

* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex>

* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>

В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==== Стоимость операции del() ====

* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=3</tex>

Средняя стоимость операции {{---}} <tex>2</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==Динамические массивы в современных языках программирования==
Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
===С++ {{---}} vector===
В С++ динамический массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен <tex>0</tex>.
===Java {{---}} ArrayList===
В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в <tex>1.5</tex> раза. Причем начальный размер равен <tex>10</tex>. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

==Источники информации==
* [[wikipedia:Dynamic_array | Wikipedia {{---}} Dynamic array]]
* [[wikipedia:ru:Динамический_массив | Wikipedia {{---}} Динамический массив]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Список

2014-06-09T16:49:06Z

79.134.198.186: /* См.также */

'''Связный список''' {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead)
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value)
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead()
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement)
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==См.также==
* [[Динамический массив]]

==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2014-06-09T16:47:29Z

79.134.198.186: /* Вставка */

'''Связный список''' {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

'''function''' insert(newHead)
newHead.next = head
head = newHead

[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next
thisElement.next = thatElement
[[Файл:insertAfter.png|center|490px]]

===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value)
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead()
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement)
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2014-06-09T16:45:19Z

79.134.198.186: /* Поиск */

'''Связный список''' {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value)
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
node = node.next
'''return''' node

===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead()
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement)
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2014-06-09T16:40:13Z

79.134.198.186: /* Удаление */

'''Связный список''' {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead()
'''if''' head != ''NULL''
tmp = head
head = head.next
'''delete''' tmp
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement)
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
thisElement.next = thisElement.next.next
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]

==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2014-06-09T14:18:14Z

79.134.198.186:

'''Связный список''' {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
<pre>
removeHead()
if head != NULL
tmp = head;
head = head.next;
delete tmp;
</pre>
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
</pre>
[[Файл:removeAfter.png|center|550px]]
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Динамический массив

2014-05-25T19:52:58Z

79.134.198.186:

{{Определение
| definition =
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Динамический массив''' может изменять свой размер в зависимости от количества элементов в нём.
}}

== Операции ==
Определим операции, которые мы будем применять к динамическому массиву: 
=== get(i) ===
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения {{---}} <tex>O(1)</tex>.
=== set(i,x) ===
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив {{---}} <tex>O(n)</tex> (<tex>n</tex> {{---}} размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если количество элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> {{---}} константы, зависящие от реализации). Время выполнения операции в худшем случае {{---}} <tex>O(n)</tex>.

=== size() ===
:Возвращает количество элементов массива. Время выполнения {{---}} <tex>O(1)</tex>.

== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.
=== Метод предоплаты ===
==== Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex dpi=150>i</tex> и <tex dpi=150>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex dpi=150>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex dpi=150>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.
=== Метод потенциалов ===
За потенциал примем число:
<tex dpi=150>\Phi(c, s) = \begin{cases}
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex>

где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.

==== Стоимость операции '''add(x)''' ====

* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex>

* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>

В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==== Стоимость операции del() ====

* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=3</tex>

Средняя стоимость операции {{---}} <tex>2</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==Динамические массивы в современных языках программирования==
Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
===С++ {{---}} vector===
В С++ динамический массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен <tex>0</tex>.
===Java {{---}} ArrayList===
В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в <tex>1.5</tex> раза. Причем начальный размер равен <tex>10</tex>. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

==Источники информации==
* [[wikipedia:Dynamic_array | Wikipedia {{---}} Dynamic array]]
* [[wikipedia:Динамический_массив | Wikipedia {{---}} Динамический массив]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Саморасширяющийся массив

2014-05-25T10:55:44Z

79.134.198.186: /* Источники информации */

{{Определение
| definition =
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Саморасширяющийся массив''' может изменять свой размер в зависимости от количества элементов в нём.
}}

== Операции ==
Определим операции, которые мы будем применять к саморасширяющемуся массиву: 
=== get(i) ===
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения — <tex>O(1)</tex>.
=== set(i,x) ===
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения — <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения — <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив — <tex>O(n)</tex> (<tex>n</tex> — размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если кол-во элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> — константы, зависящие от реализации). Время выполнения операции в худшем случае — <tex>O(n)</tex>.

=== size() ===
:Возвращает количество элементов массива. Время выполнения — <tex>O(1)</tex>.

== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.
=== Метод предоплаты ===
==== Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.
=== Метод потенциалов ===
За потенциал примем число:
<tex dpi=150>\Phi(c, s) = \begin{cases}
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex>

где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.

==== Стоимость операции '''add(x)''' ====

* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex>

* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>

В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==== Стоимость операции del() ====

* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=3</tex>

Средняя стоимость операции — <tex>2</tex>, а среднее время работы — <tex>O(1)</tex>.

==Саморасширяющиеся массивы в современных языках программирования==
Саморасширяющиеся массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
===С++ {{---}} vector===
В С++ саморасширяющийся массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен <tex>0</tex>.
===Java {{---}} ArrayList===
В Java структура ArrayList основана на саморасширяющемся массиве. При превышении максимального на данный момент размера происходит увеличение в <tex>1.5</tex> раза. Причем начальный размер равен <tex>10</tex>. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

==Источники информации==
* [[wikipedia:Dynamic_array | Wikipedia {{---}} Dynamic_array]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Саморасширяющийся массив

2014-05-25T10:52:55Z

79.134.198.186:

Саморасширяющийся массив

2014-05-25T10:44:19Z

79.134.198.186: /* Саморасширяющиеся массивы в современных языках программирования */

Саморасширяющийся массив

2014-05-20T17:36:33Z

79.134.198.186: /* С++ {{---}} vector */

{{Определение
| definition =
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Саморасширяющийся массив''' может изменять свой размер в зависимости от количества элементов в нём.
}}

== Операции ==
Определим операции, которые мы будем применять к саморасширяющемуся массиву: 
=== get(i) ===
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения — <tex>O(1)</tex>.
=== set(i,x) ===
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения — <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения — <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив — <tex>O(n)</tex> (<tex>n</tex> — размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если кол-во элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> — константы, зависящие от реализации). Время выполнения операции в худшем случае — <tex>O(n)</tex>.

=== size() ===
:Возвращает количество элементов массива. Время выполнения — <tex>O(1)</tex>.

== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.
=== Метод предоплаты ===
==== Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.
=== Метод потенциалов ===
За потенциал примем число:
<tex dpi=150>\Phi(c, s) = \begin{cases}
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex>

где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.

==== Стоимость операции '''add(x)''' ====

* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex>

* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>

В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==== Стоимость операции del() ====

* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=3</tex>

Средняя стоимость операции — <tex>2</tex>, а среднее время работы — <tex>O(1)</tex>.

==Саморасширяющиеся массивы в современных языках программирования==
Саморасширяющиеся массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
===С++ {{---}} vector===
В С++ саморасширяющийся массив называется vector, он описан в STL(<vector>). Стратегия его расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит.

Саморасширяющийся массив

2014-05-20T17:34:25Z

79.134.198.186:

{{Определение
| definition =
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Саморасширяющийся массив''' может изменять свой размер в зависимости от количества элементов в нём.
}}

== Операции ==
Определим операции, которые мы будем применять к саморасширяющемуся массиву: 
=== get(i) ===
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения — <tex>O(1)</tex>.
=== set(i,x) ===
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения — <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения — <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив — <tex>O(n)</tex> (<tex>n</tex> — размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если кол-во элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> — константы, зависящие от реализации). Время выполнения операции в худшем случае — <tex>O(n)</tex>.

=== size() ===
:Возвращает количество элементов массива. Время выполнения — <tex>O(1)</tex>.

== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.
=== Метод предоплаты ===
==== Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.
=== Метод потенциалов ===
За потенциал примем число:
<tex dpi=150>\Phi(c, s) = \begin{cases}
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex>

где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.

==== Стоимость операции '''add(x)''' ====

* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex>

* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>

* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>

В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.

==== Стоимость операции del() ====

* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=3</tex>

Средняя стоимость операции — <tex>2</tex>, а среднее время работы — <tex>O(1)</tex>.

==Саморасширяющиеся массивы в современных языках программирования==
Саморасширяющиеся массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
===С++ {{---}} vector===
В С++ саморасширяющийся массив называется vector, он описан в STL(<vector>). Стратегия его расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшения размера массива никогда не происходит.