21. Деревья в теории графов.

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

Графом будем наз. Тройку множеств (V,E,P), где N=n – множество вершин, E=m – множество ребер, P(x, e ,y) – трехместный предикат инцидентности означает, что ребро e соединяет вершины x, y. Для предиката выполняются свойства:

1. P(x, e, y), где x, y Є V, e Є E

2.Для любого ребра e  вершины x y такие, что имеет место [P(x,e,y)^  x’, e’, y'  P(x’,e’,y’) → ((x’=x)^(y’=y)^(x’=y)^(y’=x))]

 e Є E  x,y Є V [P(x,e,y)^רP(y,e,x)] такой граф наз. ориентированным. Ребра –дугами.

 e Є E  x,y Є V [P(x,e,y)^P(y,e,x)] такой граф наз. неориентированным.

Если эти условия не выполняются граф наз. смешаным.

Граф G наз. простым, если для любых ребер e,f выполняется условие [(P(x,e,y)^P(y,f,x))→(e=f)], т.е. если любая пара в нем соединена одним и только 1 ребром.

Маршрутом или путем в графе G между вершинами x y наз. упорядоченное множество ребер l_i M={ l_i, т.ч.  V₁ ..V_n [P(x,e₁,V₁) ^ P(V₁,e₂,V₂) ^ P(V_m,e_n+1,y)]}

Маршрут наз. циклом, если начальная вершина совпадает с конечной.

Неориентированный граф G наз. Связным, если любые 2 вершины в нем взаимодостижимы.

Неориентированный граф G, если он связный и не содержит циклов наз. деревом.

Вместе с деревом обычно определяем его корень, в качестве которого может выступать любая вершина. Для определенности считаем, что корнем является вершина 1, если специально не определена другая.

Число ребер инцидентных вершине наз. ее степенью (S).

Вершины степени 1, не являющиеся корнем наз. листами.

Отцами (f) листов наз. вершины, определенные так:

1. если V лист, значит отец вершины V это смежная с ней вершина

2. для определения отцов других вершин рассмотрим подграф, полученный удалением части листов n в нем по правилу 1.определяем отцов вновь полученных листов и т.д.

3. корень не имеет отца

Предком вершины наз. ее отца и отца любого его предка.

Свойства деревьев:

1. дерево это простой граф

2. дерево не содержит петель

3. если в дереве n вершин, то в нем всегда n-1 ребер

док-во: воспользуемся ММИ – n=1(дерево из 1 вершины) m=1 (ребра) базис индуктивности выполняется

пусть в дереве n=1 то число ребер m=n-2

3 случая добавления вершин в графе:

Не добавляется ни одного ребра, тогда V становится изолированной

Добавляется более 1 ребра, петли добавлять нельзя, тогда вершины будут соединять разные ребра

Добавляется ровно одно ребро, т.е. число ребер становится n-1, значит индуктивность выполняется.

4. пусть G’ граф полученный из G путем ориентации ребер от отцов к сыновьям.

В этом случае транзитивное замыкание графа G’, рассматриваемое как бинарное отношение, является отношение древесного порядка (строго древесного порядка). 1.антирефлексивность (петель нет) 2.антисеммитричность 3.транзитивность

G’^*-транзитивное замыкание

Полным транзитивным замыканием б\о графа G наз. G^*=IGG²G³.. положительное тран. замык. G⁺=GG²G³..

I-множество рефлексивных пар, т.е. добавляется петли у каждой вершины.

21. Деревья в теории графов.

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

Графом будем наз. Тройку множеств (V,E,P), где N=n – множество вершин, E=m – множество ребер, P(x, e ,y) – трехместный предикат инцидентности означает, что ребро e соединяет вершины x, y. Для предиката выполняются свойства:

1. P(x, e, y), где x, y Є V, e Є E

2.Для любого ребра e  вершины x y такие, что имеет место [P(x,e,y)^  x’, e’, y'  P(x’,e’,y’) → ((x’=x)^(y’=y)^(x’=y)^(y’=x))]

 e Є E  x,y Є V [P(x,e,y)^רP(y,e,x)] такой граф наз. ориентированным. Ребра –дугами.

 e Є E  x,y Є V [P(x,e,y)^P(y,e,x)] такой граф наз. неориентированным.

Если эти условия не выполняются граф наз. смешаным.

Граф G наз. простым, если для любых ребер e,f выполняется условие [(P(x,e,y)^P(y,f,x))→(e=f)], т.е. если любая пара в нем соединена одним и только 1 ребром.

Маршрутом или путем в графе G между вершинами x y наз. упорядоченное множество ребер l_i M={ l_i, т.ч.  V₁ ..V_n [P(x,e₁,V₁) ^ P(V₁,e₂,V₂) ^ P(V_m,e_n+1,y)]}

Маршрут наз. циклом, если начальная вершина совпадает с конечной.

Неориентированный граф G наз. Связным, если любые 2 вершины в нем взаимодостижимы.

Неориентированный граф G, если он связный и не содержит циклов наз. деревом.

Вместе с деревом обычно определяем его корень, в качестве которого может выступать любая вершина. Для определенности считаем, что корнем является вершина 1, если специально не определена другая.

Число ребер инцидентных вершине наз. ее степенью (S).

Вершины степени 1, не являющиеся корнем наз. листами.

Отцами (f) листов наз. вершины, определенные так:

4. если V лист, значит отец вершины V это смежная с ней вершина

5. для определения отцов других вершин рассмотрим подграф, полученный удалением части листов n в нем по правилу 1.определяем отцов вновь полученных листов и т.д.

6. корень не имеет отца

Предком вершины наз. ее отца и отца любого его предка.

Свойства деревьев:

5. дерево это простой граф

6. дерево не содержит петель

7. если в дереве n вершин, то в нем всегда n-1 ребер

док-во: воспользуемся ММИ – n=1(дерево из 1 вершины) m=1 (ребра) базис индуктивности выполняется

пусть в дереве n=1 то число ребер m=n-2

3 случая добавления вершин в графе:

Не добавляется ни одного ребра, тогда V становится изолированной

Добавляется более 1 ребра, петли добавлять нельзя, тогда вершины будут соединять разные ребра

Добавляется ровно одно ребро, т.е. число ребер становится n-1, значит индуктивность выполняется.

8. пусть G’ граф полученный из G путем ориентации ребер от отцов к сыновьям.

В этом случае транзитивное замыкание графа G’, рассматриваемое как бинарное отношение, является отношение древесного порядка (строго древесного порядка). 1.антирефлексивность (петель нет) 2.антисеммитричность 3.транзитивность

G’^*-транзитивное замыкание

Полным транзитивным замыканием б\о графа G наз. G^*=IGG²G³.. положительное тран. замык. G⁺=GG²G³..

I-множество рефлексивных пар, т.е. добавляется петли у каждой вершины.