Подграф

Материал из WikiGrapp
Перейти к:навигация, поиск

Подграф (Subgraph) - 1. Для графа G = (V,E) такой граф H = (W,U), у которого множество вершин W есть подмножество вершин графа G, W \subseteq V, множество ребер/дуг U есть подмножество множества ребер/дуг E, U
\subseteq E, причем, если (x,y) \in E и x,y \in W, то обязательно (x,y) \in U. Это определение подграфа мы будем называть сильным определением подграфа. Оно восходит к К. Бержу и распространено в большей части русскоязычной литературы.

2. То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.

См. также

Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево.

Литература

[Берж],

[Зыков/69],

[Харари],

[Лекции]