Пример 2.6

На рис. 2.15 изображено дерево, рядом с вершинами которого указаны их кортежи. В скобках указаны уровни центральных вершин, их две, т.е. дерево бицентральное. Если центральные вершины совместить (слить), удалив инцидентное им ребро, то получим центральное дерево, центр v которого будет иметь кортеж:

k (v) = 2413 941113111311 6 11111 4 321 1.

Рис. 2.15. Кортежи вершин дерева

Теорема 2.10. Для того чтобы два дерева были изоморфны необходимо и достаточно, чтобы они оба были центральными (или бицентральными) и кортежи их центров совпадали.

(Без доказательства).

2.4. Паросочетания и двудольные графы

Ø Наибольшее паросочетание

Ø Метод чередующихся цепей

Ø Хроматическое число

Ø Двудольные графы

Ø Наибольшее паросочетание в двудольном графе

Ø Гамильтоновы цепи и циклы в двудольном графе

Наибольшее паросочетание

Паросочетанием простого графа G = (V, E) называется такое подмножество
R Í E его ребер, в котором никакие два ребра не имеют общей инцидентной вершины. Ребра, не имеющие общих инцидентным им вершин, называются независимыми. Поэтому иначе можно сказать, что паросочетание это множество независимых ребер.

Дата добавления: 2015-07-20