АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Типы подграфов. Остовное дерево. Циклический ранг.

Определение. Граф G’(V’,E’) называется подграфом графа G(V,E), (обозначается G’ G), если V’ V и E’ E.

Определение. Если V’=V, то G’ называется остовным подграфом графа G.

Определение. Если V’ V и E’ E, то G’ называется собственным подграфом графа G.

Определение. Подграф G’(V’,E’) называется правильным подграфом графа G(V,E), если G’ содержит все возможные ребра графа G: u, v V’(u,v) E (u,v) E’. Правильный подграф определяется множеством вершин V’.

Примеры. =>

G(V,E) G’(V’,E’)

Собственный подграф Остовный подргаф Правильный подграф Неправильный подграф

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

Несвязный граф не имеет остовных деревьев. Связный граф в общем случае имеет множество остовных деревьев. Число остовных деревьев полного графа равно .

Так как число ребер в дереве с q вершинами равно q-1, то для того, чтобы получить остов графа G, нужно удалить из него p(G)-(q(G)-1) ребер.

Определение. Циклическим рангом связного графа G называется число

p(G)-q(G)+1.

Дата добавления: 2015-09-27 | Просмотры: 805 | Нарушение авторских прав