Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Подграф''' (''Subgraph'') - 1. Для графа <math>G = (V,E)</math> такой граф <math>H = (W,U)</math>, у кото...)
 
Нет описания правки
Строка 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</math>, <math>W \subseteq V</math>,
множество ребер/дуг <math>U</math> есть подмножество множества ребер/дуг <math>E</math>, <math>U
множество [[ребро|ребер]]/[[дуга|дуг]] <math>U</math> есть подмножество множества ребер/дуг <math>E</math>, <math>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>. Это определение подграфа мы будем называть сильным
определением подграфа. Оно восходит к К.~Бержу и распространено в
определением подграфа. Оно восходит к К. Бержу и распространено в
большей части русскоязычной литературы.
большей части русскоязычной литературы.


2. То же, что и ''часть'' графа. Это определение будем называть
2. То же, что и [[часть графа|''часть'' графа]]. Это определение будем называть
слабым определением подграфа; оно распространено в части русскоязычной
слабым определением подграфа; оно распространено в части русскоязычной
и практически во всей англоязычной литературе.
и практически во всей англоязычной литературе.


См. также ''Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево''.
==См. также==
''[[Линейный подграф графа|Линейный подграф]], [[Остовный подграф]], [[Порожденный подграф]], [[Четный подграф]], [[Поддерево]]''.
==Литература==
==Литература==
[Берж],  
[Берж],