![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Деревья. Остов графа. Цикловой базис графа
Примеры:
Определение: Граф G, все компоненты связности которого являются деревьями, называют лесом. Свойства деревьев: Если граф G – дерево, то: 1) G – связный; 2) G не имеет простых циклов; 3) Если G имеет n вершин, то ребер (n-1); 4) Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдётся висячая вершина; 5) Любые две различные вершины графа G можно соединить единственной простой цепью; 6) При добавлении к дереву любого нового графа получаем ровно один и притом простой цикл, который проходит через добавленное ребро. При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершин, удовлетворяющих определенным свойствам. Тогда если граф есть дерево, то его удобно изображать следующим образом. Выберем в дереве произвольную вершину α0 и назовем её корнем дерева (или вершина нулевого яруса). Смежные с α0 вершины назовем вершинами 1-го яруса и т.д. Номер яруса совпадает с расстоянием между его вершинами и корнем дерева. Выделение корня в дереве определяет на множестве его вершин частичный порядок: Корень Определение: Остовграфа 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) (или циклическим рангом). Определение: Независимая система циклов { Утверждение: Если мультиграф G не является ациклическим, то в нём существует цикловой базис, элементами которого являются простые циклы. Теорема: Количество элементов в цикловом базисе мультиграфа G=(V,X) совпадает с его цикломатическим числом. То есть цикломатическое число показывает, чему равна размерность пространства базисов циклов графа. Для несвязного графа с к компонентами связности базис циклов графа получается объединением базисов его связных компонент.
Утверждение 1: Неорграф G является лесом тогда и только тогда, когда υ(G)=0. Утверждение 2: Неорграф G имеет единственный цикл тогда и только тогда, когда υ(G)=1.
|