Эйлеровы и гамильтоновы циклы.

Цикл называется эйлеровым, если каждое ребро графа участвует в его образовании только один раз. Граф, содержащий такой цикл, называется эйлеровым.

Граф G=<V, U> является эйлеровым  граф связан и степень каждой вершины V_iV - четное число.

Цикл называется простым, если все его вершины различны. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа. Граф содержащий такой цикл, называется гамильтоновым.

Деревья

Неориентированное дерево - это связной неориентированный граф без циклов, а значит без петель и кратных ребер.

Любые две вершины дерева V' и V" связаны одной и только одной цепью.

Пусть в дереве G отмечена вершина V₀ - корень дерева.

В дереве с корнем можно естественным образом ориентировать ребра - в направлении либо от корня, либо к корню. Получим ориентированное дерево (в последнем случае - сеть сборки).

В каждую вершину ориентированного дерева ( за исключением корня) входит только одно ребро.

В конечном дереве число вершин на единицу больше числа ребер.

Операции на графами.

1. Дополнение графа G=<V₁, E₁> называется графG=<V₂, E₂> где V₂=V₁ и E₂=E₁={eV₁²| eE₁}.

2. Объединением графов G=<V₁, E₁> и G=<V₂, E₂> называется граф G=<V, E>, где V=V₁V₂ и E=E₁E₂, V₁V₂=, E₁E₂=

3. Соединением графов G=<V₁, E₁> и G=<V₂, E₂> при условии, что V₁V₂=, E₁E₂= называется граф G=<V, E>, где V=V₁V₂ и E=E₁E₂{e=(v₁, v₂)|v₁V₁ и v₂V₂}.

4. Удаление вершины v из графа G=<V₁, E₁> при условии vV₁ дает граф G=<V₂, E₂> где V₂=V₁\{v}, и E₂=E₁\{e=(v₁, v₂) | v₁=v или v₂=v}.

5. Удаление ребра из графа G=<V₁, E₁> при условии eE₁ дает граф G=<V₂, E₂>, где V₂=V₁ и E₂=E₁\{e}.

6. Добавление вершины v в граф G=<V₁, E₁> при условии vV₁ дает граф G=<V₂, E₂>, где V₂=V₁{v} и E₂=E₁.

7. Добавление ребра e в граф G=<V₁, E₁> при условии eE₁, дает граф G=<V₂, E₂>, где V₂=V₁ и E₂=E₁{e}.

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

Графом G называется совокупность множества M с заданным в нем бинарным отношением TM².

G=<M, T>

М - множество вершин, Т - множество ребер.

Подграфом G графа G называется граф, полученный удалением из графа G некоторых вершин и инцидентных им ребер.

G=<M, T>, G'=<M', T '>, M'M, T 'T

Частичным графом G графа G=<V, U> называется граф вида G'=<V', U'>, U'U, то есть граф, полученный из исходного удалением некоторых дуг.

Дуга - это направленное ребро.

Путь - это последовательность дуг (₁,₂,…,_n) вида _i=(v_i,v_i+1), i=1,2,…,n вершины.

Контуром называется путь, концевые вершины которых совпадают.

Цепь - это последовательность ребер (p₁,p₂,…,p_n) вида p_i=(v_i,v_i+1), i=1,2,…,n. Вершины цепи могут иметь степень, равную 1.

Циклом называется цепь, концевые вершины которой совпадают. Все вершины цикла имеют степень 2.

Граф G=<V, U> называется связным, если любая пара его вершин соединена цепью. Максимальный по включению вершин связной подграфграфа называется его компонентой связности.

Граф называется несвяязным, если число его компонент больше одной.

Граф, состоящий из одной вершины, называется тривиальным.

Связностью графа называется наименьшее число вершин, удаление которых делает граф несвязным или тривиальным.

Виды графов.

G=<M, R>

Подграфом G графа G называется граф, полученный удалением из графа G некоторых вершин и инцидентных им ребер: G'=<M', R'>, M'M, R'R.

Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не более чем одним ребром.

Простой граф называется полным, если каждая пара вершин соединена ребром.

Дополнением простого графа G называется графG, имеющий те же вершины, а его ребра являются дополнением G до полного графа.

G₁

G₂

G₃

G₄

Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все пересечения ребер являются вершинами.