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

Материал из 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. То же, что и [[часть графа|''часть'' графа]]. Это определение будем называть
слабым определением подграфа; оно распространено в части русскоязычной
слабым определением подграфа; оно распространено в части русскоязычной
и практически во всей англоязычной литературе.
и практически во всей англоязычной литературе.


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

Версия от 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],

[Харари],

[Лекции]