пользователей: 21277
предметов: 10471
вопросов: 178106
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Остовное дерево. Базис цикла графа

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

  • Любое остовное дерево в графе с n вершинами содержит ровно n - 1 ребро.
  • Число остовных деревьев в полном графе на n вершинах выражается знаменитой формулой Кэли:[2]

    Алгоритм построения остовного дерева:

    1) Выбираем произвольное ребро U из графа G и включаем его в T(G)

    2) Выбираем нерассмотренное ребро и если оно не образует цикла с ребрами дерева T(G), то включаем его в T(G)

    3) Если мощность множества ребер дерева меньше, чем n-1? nj переходим на шаг 2, если нет, то шаг 4

    4) Дерево T(G) построено.

    Базис пространства циклов графа, состоящий только из простых циклов. Б.ц. является максимальным набором независимых простых циклов графа или минимальным набором простых циклов, от которых зависят все циклы. Мощность базиса циклов пространства циклов графа называется циклическим рангом графа. 

     

     


18.06.2015; 01:25
хиты: 123
рейтинг:0
Точные науки
математика
логика и основания математики
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь