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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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. Для графа [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.