Подграф

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

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

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

Литература

[Берж],

[Зыков/69],

[Харари],

[Лекции]