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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
  
 
{{Определение
 
{{Определение
|id = oriented_grath
 
 
|definition =
 
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
+
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (vertices), а <tex> E \subset V \times V </tex> {{---}} множество рёбер (edges, дуг (arcs), линий (lines)).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = finite_graph
 
 
|definition =
 
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
+
'''Конечным графом''' (finite graph) <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = def_graph_edge_1
 
 
|definition =
 
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
+
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = isomorphic_graphs
 
 
|definition=
 
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа <tex>A</tex> и <tex>B</tex> называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.
+
'''Изоморфные графы''' {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
 
}}
 
}}
  
В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется <b>петлей</b> (англ. ''loop'').
+
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b> (loop).
 
 
Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').  
 
  
 
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
 
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
+
* <tex> v </tex> {{---}} '''предок''' (direct predecessor) <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
+
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные''' (adjacent)
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
+
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>
* Вершина <tex> v </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>-граф называют <b>тривиальным</b>.
+
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом.  <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.
  
 
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
 
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Строка 44: Строка 38:
 
|id = def1
 
|id = def1
 
|definition =
 
|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> называется четверка <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'').
+
 
 +
Иногда граф, построенный таким образом, называют '''псевдографом''' (pseudograph). В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', multi-edge, parallel edge). Псевдограф без петель принято называть '''мультиграфом'''.
 
{|border="0" cellpadding="5" width=30% align=center
 
{|border="0" cellpadding="5" width=30% align=center
 
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]
 
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]
Строка 54: Строка 49:
 
|}
 
|}
  
{{Определение
 
|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>.
 
}}
 
  
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество рёбер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
+
 
 +
Также для ориентированных графов определяют '''полустепень исхода вершины''' (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>.
 +
 
 +
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
  
 
==Неориентированные графы==
 
==Неориентированные графы==
 
{{Определение
 
{{Определение
|id = def_undirected_graph_1
 
 
|definition =
 
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
+
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
 
}}
 
}}
 
{{Определение
 
{{Определение
|id=def_edge_und
 
 
|definition =
 
|definition =
 
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
 
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
Строка 74: Строка 66:
 
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]
 
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]
 
Иное определение:
 
Иное определение:
 +
 
{{Определение
 
{{Определение
|id = def_undirected_graph_2
 
 
|definition =
 
|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>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.
+
'''Неориентированным графом''' <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>. Обратите внимание, что это определение позволяет задавать графы с кратными ребрами.
 
}}
 
}}
  
{{Определение
+
Две вершины называются '''смежными''' (adjacent), если между ними есть ребро.
|id = def_simple_graph
+
 
|definition =
+
'''Степенью''' (degree, valency) вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
'''Простым графом''' <tex>G</tex> называется граф, в котором нет петель и кратных рёбер.
 
}}
 
  
{{Определение
 
|id = def_graph_degree_1
 
|definition =
 
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число рёбер, инцидентных <tex>v_i</tex>.
 
}}
 
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
 
  
{{Определение
 
|id = isolated_vertex
 
|definition =
 
'''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex>
 
}}
 
  
 
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
 
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
Строка 105: Строка 84:
 
=== Матрица и списки смежности ===
 
=== Матрица и списки смежности ===
  
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные рёбра).
+
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (adjacency matrix), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</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>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.
+
Если граф разрежен (sparse graph, <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
  
 
=== Пути в графах ===
 
=== Пути в графах ===
 
{{Определение
 
{{Определение
|id = path
 
 
|definition =
 
|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'') пути.
+
'''Путём''' (маршрутом, 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=
 
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
+
'''Циклическим путём''' (closed walk) в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = def_no_graph_path
 
 
|definition =
 
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а также <tex> e_i \ne e_{i \bmod k + 1}</tex>.
+
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = def_graph_cycle_1
 
 
|definition =
 
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists  j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности рёбер в циклическом пути.
+
'''Цикл''' (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=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
+
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.
+
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
 
}}
 
}}
  
== Часто используемые графы ==
 
 
{{Определение
 
{{Определение
|id = defFullGraph
 
 
|definition=
 
|definition=
'''Полный граф''' (англ. ''complete graph'', ''clique'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
+
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
 
}}
 
}}
  
{{Определение
+
== Часто используемые графы ==
|id = defBiparateGraph
 
|definition=
 
<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
 
}}
 
 
 
{{Определение
 
|id = defRegularGraph
 
|definition=
 
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
 
}}
 
 
 
{{main|Дерево, эквивалентные определения}}
 
{{Определение
 
|id=defTree
 
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
 
}}
 
 
 
{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}
 
{{Определение
 
|definition=
 
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
 
}}
 
 
 
{{main|Гамильтоновы графы}}
 
{{Определение
 
|definition=
 
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
 
}}
 
 
 
{{main|Укладка графа на плоскости}}
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
+
<tex>K_n</tex> {{---}} полный граф с <tex>n</tex> вершинами.
 
}}
 
}}
  
{{main|Лемма о безопасном ребре}}
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
+
<tex>K_{n,m}</tex> {{---}} двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй.
 
}}
 
}}
  
Строка 202: Строка 140:
 
* [[Связь степени матрицы смежности и количества путей]]
 
* [[Связь степени матрицы смежности и количества путей]]
  
==Источники информации==
+
==Литература==
* [[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
 
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
+
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: