Подграф: различия между версиями
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. То же, что и [[часть графа|''часть'' графа]]. Это определение будем называть | ||
слабым определением подграфа; оно распространено в части русскоязычной | слабым определением подграфа; оно распространено в части русскоязычной | ||
и практически во всей англоязычной литературе. | и практически во всей англоязычной литературе. | ||
См. также ''Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево''. | ==См. также== | ||
''[[Линейный подграф графа|Линейный подграф]], [[Остовный подграф]], [[Порожденный подграф]], [[Четный подграф]], [[Поддерево]]''. | |||
==Литература== | ==Литература== | ||
[Берж], | [Берж], | ||
Версия от 12:38, 18 декабря 2009
Подграф (Subgraph) - 1. Для графа [math]\displaystyle{ G = (V,E) }[/math] такой граф [math]\displaystyle{ H = (W,U) }[/math], у которого множество вершин [math]\displaystyle{ W }[/math] есть подмножество вершин графа [math]\displaystyle{ G }[/math], [math]\displaystyle{ W \subseteq V }[/math], множество ребер/дуг [math]\displaystyle{ U }[/math] есть подмножество множества ребер/дуг [math]\displaystyle{ E }[/math], [math]\displaystyle{ 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. То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.
См. также
Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево.
Литература
[Берж],
[Зыков/69],
[Харари],
[Лекции]