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

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

2010-10-11T03:05:48Z

Kn793: /* Для неориентированного графа */

==Граф==
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В [[Ориентированный граф|ориентированном графе]] (v, u) = (u, v).

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

==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi
}}
Говорят, что ребро <tex> e = (u, v) </tex> инцидентно вершине a, если u = a или v = a.

====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.
}}
{{Определение
|definition =
Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.
}}

==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.

==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).
}}

==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk
}}

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

2010-10-10T18:49:35Z

Kn793: переименовал «Основные определения: граф, ребро, вершина, степень, петля, путь, цикл» в «Основные определения теории графов»

==Граф==
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В [[Ориентированный граф|ориентированном графе]] (v, u) = (u, v).

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

==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi
}}
====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.
}}
{{Определение
|definition =
Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.
}}

==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.

==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).
}}

==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk
}}

Основные определения: граф, ребро, вершина, степень, петля, путь, цикл

2010-10-10T18:49:35Z

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

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

2010-10-10T05:40:41Z

Kn793: Новая страница: «{{Определение |definition = Ориентированным графом <math> G </math> называется пара <math> G = (V, E); </math> где V…»

{{Определение
|definition =
Ориентированным графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер. Причём (v, u) ≠ (u, v).
}}

{{Определение
|definition =
Ребро ориентированного графа называется '''дугой'''.
}}

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

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

2010-10-10T05:40:09Z

Kn793: /* Граф */

==Граф==
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В [[Ориентированный граф|ориентированном графе]] (v, u) = (u, v).

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

==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi
}}
====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.
}}
{{Определение
|definition =
Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.
}}

==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.

==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).
}}

==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk
}}

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

2010-10-10T05:13:49Z

Kn793: Новая страница: «==Граф== {{Определение |definition = Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечно…»

==Граф==
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В ориентированном графе (v, u) = (u, v).

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

==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi
}}
====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.
}}
{{Определение
|definition =
Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.
}}

==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.

==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).
}}

==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk
}}