электронный учебник

"Экономико-математические методы"

 

На главную страницу

Графы и сети. Потоки в сетях

В конец страницы

14.3.  ПОДГРАФЫ

       Граф  называется подграфом графа , если  и  являются подмножествами R и , причем ребро содержится в  только в том случае, если его концевые вершины содержатся в .

        Пусть       –   некоторое    подмножество    множества    вершин    графа  и пусть – множество всех ребер графа G, концевые вершины которых входят в . Тогда граф  называется вершинно-порожденным подграфом графа G. Обозначим через  некоторое подмножество множества ребер графа G и пусть  есть множество всех вершин графа G, инцидентных ребрам из . Тогда граф  называется реберно-порожденным подграфом  графа G.

 Рисунок 14.3.

        На рис. 14.3 изображены вершинно-порожденный подграф , представленного на рис. 11.1 (множество вершин ), и реберно–порожденный подграф  того же графа G (того же графа G ( множество ребер ).

 

 Назад     К началу страницы     Вперед