Деревья, их характеризации. Остов графа.

Дерево — это связный ациклический граф (то есть граф, не содержащий циклов, между любой парой вершин которого существует ровно один путь).[1]

 

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.[2]

Свойства

Дерево не имеет кратных рёбер и петель.

Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1, где B — число вершин, P — число рёбер графа.

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

Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.

Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.

Для любых трех вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

 

Билет 16

Булевы решётки

Булева алгебра, булева решётка — частично упорядоченное множество специального вида; дистрибутивная решётка, имеющая наибольший элемент 1 — единицу булевой алгебры, наименьший элемент 0 — нуль булевой алгебры, и содержащая единственное дополнение каждого своего элемента x — элемент (не x)

 

Билет 16

Полные графы. Дополнение графа. Полные подграфы. Теорема Рамсея.

Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n − 1) / 2

В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, дополните данный граф до полного и удалите все ребра, которые уже были до этого.

Клика(полный подграф) - подмножество вершин, каждые две из которых соединены ребром графа.

 

 

Пусть даны числа a1,a2,...an. Тогда существует такое число R, что, как бы мы ни покрасили рёбра полного графа на R вершинах в n цветов, найдётся либо полный подграф 1-го цвета на a1 вершинах, либо полный подграф 2-го цвета на a2 вершинах, … либо полный подграф n-го цвета на an вершинах.

 

 

Билет 17

Булево кольцо

Булевым кольцом называют кольцо, в котором все элементы идемпотентны (коммутативность, наличие единицы или делителей нуля не требуется). Интересной особенностью булевых колец является то, что

в частности, при

то есть булево кольцо всегда коммутативно.

 

Билет 17

Двудольные графы, необходимое и достаточное условие существования.

Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Свойства

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

Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум)

Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые k элементов одной из долей связаны по крайней мере с k элементами другой (Теорема Холла).

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

Билет 20

Решетки. Группы. Унарные алгебры.