4624
правки
Подграф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Подграф''' (''Subgraph'') - 1. Для графа <math>G = (V,E)</math> такой граф <math>H = (W,U)</math>, у кото...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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>\,W</math> есть подмножество вершин графа <math>G,\;W \subseteq V</math>, | ||
множество ребер/дуг <math>U</math> есть подмножество множества ребер/дуг <math>E | множество [[ребро|ребер]]/[[дуга|дуг]] <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 U.</math> Это определение подграфа мы будем называть сильным | ||
<math>(x,y) \in U</math> | определением подграфа. Оно восходит к К. Бержу и распространено в | ||
определением подграфа. Оно восходит к К. | |||
большей части русскоязычной литературы. | большей части русскоязычной литературы. | ||
2. То же, что и ''часть'' графа. Это определение будем называть | 2. То же, что и [[часть графа|''часть'' графа]]. Это определение будем называть | ||
слабым определением подграфа; оно распространено в части русскоязычной | слабым определением подграфа; оно распространено в части русскоязычной | ||
и практически во всей англоязычной литературе. | и практически во всей англоязычной литературе. | ||
См. также ''Линейный подграф, Остовный подграф, Порожденный подграф, Четный подграф, Поддерево'' | ==См. также== | ||
* ''[[Линейный подграф графа|Линейный подграф]],'' | |||
* ''[[Остовный подграф]],'' | |||
* ''[[Порожденный подграф]],'' | |||
* ''[[Четный подграф]],'' | |||
* ''[[Поддерево]].'' | |||
==Литература== | ==Литература== | ||
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962. | |||
* Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
* Харари Ф. Теория графов. — М.: Мир, 1973. | |||