Подграф

Подграф (Subgraph) — 1. Для графа [math]\displaystyle{ \,G = (V,E) }[/math] такой граф [math]\displaystyle{ \,H = (W,U), }[/math] у которого множество вершин [math]\displaystyle{ \,W }[/math] есть подмножество вершин графа [math]\displaystyle{ G,\;W \subseteq V }[/math], множество ребер/дуг [math]\displaystyle{ \,U }[/math] есть подмножество множества ребер/дуг [math]\displaystyle{ E,\;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. То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.

См. также

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

Литература

• Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

• Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Харари Ф. Теория графов. — М.: Мир, 1973.