Дискретная математика

122 Физическое содержание информации, содержащейся в графах, может быть самым разнообразным. Если вершины обозначают города, то ребра (дуги) могут представлять собой дорожную сеть между ними или линии газопроводов, или линии электропередачи, если вершины - спортивные команды, ребра (дуги) могут свидетельствовать о недельном плане Иф между командами и т. д. а) б) в) г) Рис. 5.4. Подграфом графа (орграфа) G=(V,X) называется граф (орграф) G = (V',X'), множество вершин V' которого является подмножеством вершин V графа G, а ребрами (дугами) - часть ребер (дуг) графа G, оба конца которых лежат в множестве V'. Остовным подграфом фафа G=(l^,X) называется граф G=(V,XV' X, содержащий все вершины графа G=(V,X), но возможно не содержащий некоторых ребер из X. Дополнением графа {орграфа) G=(V,X) называется граф (opqэaф) G=(V,X) с тем же множеством вершин V> а X является дополнением множества X до множества всех, неупорядоченных (упорядоченных) пар вершин из V. Таким образом, в дополнении графа G вершины смежны тогда и только тогда, когда они не смежны в G. Удаление вершины v,- из графа G приводит к подграфу G\v.-, содержащему все вершины графа G, за исключением v,-, и все ребра графа G, не инцидентные v,-. Другими словами, G\v,- есть максимальный подграф графа G, не содержащий v,-. Удаление ребраXj из G приводит к остовному подграфу, содержащему все ребра графа G, за исключением Xj, т.е. G\xj есть максимальный подграф графа G, не содержащий Xj, см рис, 5.5. °6й О 6 Рис. 5.5. Графы, содержащие и не содержащие вершину или ребро