Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Деревья. Остов графа. Цикловой базис графа




Определение: Связный граф без циклов называется деревом.

Примеры:

 

 

Определение: Граф G, все компоненты связности которого являются деревьями, называют лесом.

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

Если граф G – дерево, то:

1) G – связный;

2) G не имеет простых циклов;

3) Если G имеет n вершин, то ребер (n-1);

4) Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдётся висячая вершина;

5) Любые две различные вершины графа G можно соединить единственной простой цепью;

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

При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершин, удовлетворяющих определенным свойствам. Тогда если граф есть дерево, то его удобно изображать следующим образом. Выберем в дереве произвольную вершину α0 и назовем её корнем дерева (или вершина нулевого яруса). Смежные с α0 вершины назовем вершинами 1-го яруса и т.д.

Номер яруса совпадает с расстоянием между его вершинами и корнем дерева.

Выделение корня в дереве определяет на множестве его вершин частичный порядок: .

Корень 0 является единственным минимальным элементом в этом частичном упорядоченном множестве вершин, а все концевые вершины – максимальные элементы.

Определение: Остовграфа G (или остовное дерево, или каркас графа G) – любой подграф графа G, содержащий все вершины графа G и являющийся деревом.

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

Остов выбирается, вообще говоря, неоднозначно, в него входят все ациклические ребра.

Пусть G – граф, Д – его остов. Тогда все ребра подграфа G\Д называются хордами. Каждая хорда связывает две вершины остова.

На практике удобнее строить остов графа G путем последовательного удаления из G циклических ребер (хорд).

Пусть дан граф G=(V,X) v={v1,…, v n}, X={x1,…,xm}.

В остове графа G ребер будет (n-1) .

Тогда из графа G при построении остова удаляется m-(n-1)=m-n+1 ребер, т.е. m-n+1 – количество хорд (количество удаленных циклических ребер).

Определение: Число m-n+1 называется цикломатическимчислом связного графа G и обозначается v(G) (или циклическим рангом).

Определение: Независимая система циклов { 1,…, n} называется цикловымбазисом мультиграфа G, любой цикл из графа G является линейной комбинацией циклов этой системы.

Утверждение: Если мультиграф G не является ациклическим, то в нём существует цикловой базис, элементами которого являются простые циклы.

Теорема: Количество элементов в цикловом базисе мультиграфа G=(V,X) совпадает с его цикломатическим числом. То есть цикломатическое число показывает, чему равна размерность пространства базисов циклов графа.

Для несвязного графа с к компонентами связности базис циклов графа получается объединением базисов его связных компонент.

Утверждение 1: Неорграф G является лесом тогда и только тогда, когда υ(G)=0.

Утверждение 2: Неорграф G имеет единственный цикл тогда и только тогда, когда υ(G)=1.



Поделиться:

Дата добавления: 2015-01-29; просмотров: 711; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты