Подграфы и дополнения

Подграфом G′(V′,E′) графа G(V,E) называется граф с множеством вершин V′ÍV и множеством ребер (дуг) Е′ÍЕ, каждое из которых инцидентно только вершинам v_iÍV′.

Подграфом G′(V′,E′), порожденным подмножеством V′ÍV называется граф с множеством вершин V′ и набором ребер (дуг) E′, состоящий из всех ребер (дуг) графа G′, которые соединяют вершины из V′.

Остовный подграф G′(V,E′) содержит все вершины G и некоторый набор его ребер (дуг) Е′ÍЕ.

Рис.12. Граф и его подграфы: а) граф G; б) подграфы г) остовный подграф.

Граф G′(V,E′) называется дополнением простого графа G(V,E), если ребро <v_i, v_j> входит в E′ в том и только в том случае, если оно не входит в Е. Как видно из определения под дополнением понимается дополнение до полного (полносвязного) графа.

Рис.13. а) граф G; б) граф G, дополняющий графа (до полного графа)