Подграф — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
 
Строка 1: Строка 1:
'''Подграф''' (''[[Subgraph]]'') -
+
'''Подграф''' (''[[Subgraph]]'')
1. Для [[граф|графа]] <math>G = (V,E)</math> такой граф <math>H = (W,U)</math>, у которого множество
+
1. Для [[граф|графа]] <math>\,G = (V,E)</math> такой граф <math>\,H = (W,U),</math> у которого множество
[[вершина|вершин]] <math>W</math> есть подмножество вершин графа <math>G</math>, <math>W \subseteq V</math>,
+
[[вершина|вершин]] <math>\,W</math> есть подмножество вершин графа <math>G,\;W \subseteq V</math>,
множество [[ребро|ребер]]/[[дуга|дуг]] <math>U</math> есть подмножество множества ребер/дуг <math>E</math>, <math>U
+
множество [[ребро|ребер]]/[[дуга|дуг]] <math>\,U</math> есть подмножество множества ребер/дуг <math>E,\;U \subseteq E,</math> причем, если <math>(x,y) \in E</math> и <math>x,y \in W,</math> то обязательно
\subseteq E</math>, причем, если <math>(x,y) \in E</math> и <math>x,y \in W</math>, то обязательно
+
<math>(x,y) \in U.</math> Это определение подграфа мы будем называть сильным
<math>(x,y) \in U</math>. Это определение подграфа мы будем называть сильным
 
 
определением подграфа. Оно восходит к К. Бержу и распространено в
 
определением подграфа. Оно восходит к К. Бержу и распространено в
 
большей части русскоязычной литературы.
 
большей части русскоязычной литературы.
Строка 13: Строка 12:
  
 
==См. также==
 
==См. также==
''[[Линейный подграф графа|Линейный подграф]], [[Остовный подграф]], [[Порожденный подграф]], [[Четный подграф]], [[Поддерево]]''.
+
* ''[[Линейный подграф графа|Линейный подграф]],''
 +
* ''[[Остовный подграф]],''
 +
* ''[[Порожденный подграф]],''
 +
* ''[[Четный подграф]],''
 +
* ''[[Поддерево]].''
 
==Литература==
 
==Литература==
[Берж],  
+
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.
 +
 +
* Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.
  
[Зыков/69],  
+
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  
[Харари],  
+
* Харари Ф. Теория графов. —  М.: Мир, 1973.
 
 
[Лекции]
 

Текущая версия на 14:04, 7 июня 2011

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