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


Операции над графами. Виды подграфов. Дополнение графа

Операции над графами образуют новые графы из старых.

Добавление ребра

Удаление вершины - вершина удаляется вместе с 2-мя ребрами, которые ей инцидентны.

Удаление ребра или удаление дуги

Виды подграфов:

Остовным подграфом Gp = (X, Ap ) графа называется граф, для

которого . Таким образом, остовный подграфимеет то же самое множество вершин, что и исходный граф G, но множество дуг подграфа Gp является подмножество ммножества дуг исходного графа. Примеры остовных подграфов приведены на рис. 6.1,в. Для графа, имеющего дуг, можно построить остовных подграфов

 

k=C1m+C2m+...+Cm-1m=2m-1

Остовный подграф содержит все вершины исходного подграфа.

 

Порожденным подграфом Gs =(Xs , Гs ) называется граф, для которого  и для каждой вершины прямое отображение . Таким образом, порожденный подграф состоит из подмножества вершин Xsмножества вершин исходного графа и всех таких дуг графа G, у которого конечные и начальные вершины принадлежат подмножеству Xs .

 

дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, дополните данный граф до полного и удалите все ребра, которые уже были до этого.


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