Справочник по математике для экономистов

11.3. подграфы

Рассмотрим граф G~(P, А) с множеством вершин Р и множеством ребер А. Граф G' = (P', А') называется подграфом графа G, если Р' и А' являются подмножествами Р и А, причем ребро содержится в А' только в том случае, если его концевые вершины содержатся в Р'. Пусть Р' — некоторое подмножество множества вершин графа G~(P, А) и пусть А' — множество всех ребер графа G, концевые вершины которых входят в Р'. Тогда граф G'=(P', А') называется вершинно-порожден-ным подграфом графа G.

Обозначим через А' некоторое      а> ^ подмножество множества ребер графа G=(P, А) и пусть Р' есть множе- °Д» ство всех вершин графа G, инцидент- с» ных  ребрам  из  А'.  Тогда граф G' = (P', А') называется реберно-по-рожденным подграфом графа G. Рис

На рис. 11.4 изображены вершин-но-пврожденный подграф Gx графа G, представленного на рис. 11.1 (множество вершин ри Ръ> Рл)> и реберно-порожденный подграф G2 того же графа G (множество ребер alt a3, a^, a6).