11.3. подграфы
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).
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы