Подграф

Материал из WikiGrapp
Версия от 14:04, 7 июня 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Подграф (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.