Элементы теории графов

Структура изображённая на рисунке – граф.

Граф задаётся двумя множествами G=(x,u), непустым множеством, х не равен 0; множеством вершин x={x₁; x₂; x₃; x₄; x₅; x₆; x₇}; или множеством пар элементов u={ x₁x₁; x₁x₂; x₂x₃; x₃x₄; x₃x₅; x₄x₅; x₅x₆}

При этом элементы множества Uмогут повторяться, а так же могут повторяться элементы в парах.

Граф заданный на множествах «x» и«u» обозначается G=(x,u).

Если элементы в парах не упорядочены (не указано направление), то граф называется неориентированным графом, в противном случае – ориентированным графом или орграфом.

Элементы множества Х называются вершинамиграфа, а элементы множества U называются рёбрами для неориентированного графа и дугами для ориентированного.

На плоскости граф задаётся в виде плоскостей и вершин и линий соединяющих вершины или некоторые из них.

1. Определение для неориентированного графа: ребро, начало и конец которого совпадают, называется петлёй (x₁x₁)

2. Вершины называются смежными или соседскими, если существует ребро их соединяющее.

3. Если вершина является началом или концом ребра, то эти вершины и ребро называются инцидентными.

4. Степенью вершины называется число инцидентных её рёбер

5. Вершина, степень которой равна 0, называется изолированной (x₇)

6. Вершина, степень которой равна 1, называется висячей или тупиковой. (x₆)

7. Последовательность вершин и рёбер, в которой конец предыдущего ребра совпадает с началом следующего, называется маршрутом. Число рёбер маршрута определяет его длину.

8. Цепью называется маршрут, в котором все рёбра различны.

9. Граф называется связным, если для двух любых его вершин существует цепь, их соединяющая.

10. Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей его вершины

11. Диаметром графа называется максимальное расстояние между его вершинами.

12. Циклом называется цепь, начало и конец которой совпадают (x₃; x₄; x₅; x₃). Простым циклом называется простая цепь

13. Цикл в графе называется Эйлеровым, если он содержит все рёбра графа только один раз.

14. Связный граф, в котором есть Эйлеров цикл называется Эйлеровым графом (его можно нарисовать не отрывая руки от листа)

Теорема: связный граф называется Эйлеровым тогда и только тогда, когда степень каждой его вершины чётная.

15. Подграфом графа G=(x,u) называется такой граф G=(x₁,u₁), для которого x₁входит в множество х, а u₁входит в множество u

16. Компонентой связности графа называется его связный граф не являющийся собственным подграфом никакого другого связного подграфа данного графа. (Компонента связности графа – это некоторое множество вершин графа, такое, что для любых двух вершин из этого множества существует путь из одной в другую и не существует пути из вершин этого множества в вершины не из этого множества)