Часть графа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Часть графа''' (''[[Subgraph]]'') -
'''Часть графа''' (''[[Subgraph]]'') для [[граф|графа]] <math>\,G = (V,E)</math> граф <math>\,H = (V',E')</math> такой, что <math>V' \subseteq V</math> и <math>E' \subseteq E</math>; другими словами, это граф, порождаемый [[ребро|ребрами]] ([[дуга|дугами]]) графа <math>\,G</math>. Частью графа являются [[цепь]], [[цикл]], [[каркас]] и т.д.
для [[граф|графа]] <math>G = (V,E)</math> граф <math>H = (V',E')</math> такой, что <math>V' \subseteq V</math>
и <math>E' \subseteq E</math>; другими словами, это граф, порождаемый [[ребро|ребрами]]
([[дуга|дугами]]) графа <math>G</math>. Частью графа являются [[цепь]], [[цикл]], [[каркас]] и т.д.
Вместо термина  '''часть графа'''  часто  используют  термин  ''[[подграф]]'' (в слабом
Вместо термина  '''часть графа'''  часто  используют  термин  ''[[подграф]]'' (в слабом
смысле).
смысле).


[[Файл:Subgraph.png]]
[[Файл:Subgraph.gif|500px]]


==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 12:16, 4 октября 2011

Часть графа (Subgraph) — для графа [math]\displaystyle{ \,G = (V,E) }[/math] граф [math]\displaystyle{ \,H = (V',E') }[/math] такой, что [math]\displaystyle{ V' \subseteq V }[/math] и [math]\displaystyle{ E' \subseteq E }[/math]; другими словами, это граф, порождаемый ребрами (дугами) графа [math]\displaystyle{ \,G }[/math]. Частью графа являются цепь, цикл, каркас и т.д. Вместо термина часть графа часто используют термин подграф (в слабом смысле).

Subgraph.gif

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.