4634
правки
Подграф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Подграф''' (''Subgraph'') - 1. Для графа <math>G = (V,E)</math> такой граф <math>H = (W,U)</math>, у кото...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. То же, что и [[часть графа|''часть'' графа]]. Это определение будем называть | ||
слабым определением подграфа; оно распространено в части русскоязычной | слабым определением подграфа; оно распространено в части русскоязычной | ||
и практически во всей англоязычной литературе. | и практически во всей англоязычной литературе. | ||
См. также ''Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево''. | ==См. также== | ||
''[[Линейный подграф графа|Линейный подграф]], [[Остовный подграф]], [[Порожденный подграф]], [[Четный подграф]], [[Поддерево]]''. | |||
==Литература== | ==Литература== | ||
[Берж], | [Берж], | ||