Аноним

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

Материал из 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.
 
[Лекции]