Подграф

Подграф (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. То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.

См. также

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

Литература

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

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

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

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