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

'''Подграф''' (''[[Subgraph]]'') —

1. Для [[граф|графа]] <math>\,G = (V,E)</math> такой граф <math>\,H = (W,U),</math> у которого множество

[[вершина|вершин]] <math>\,W</math> есть подмножество вершин графа <math>G,\;W \subseteq V</math>,

множество [[ребро|ребер]]/[[дуга|дуг]] <math>\,U</math> есть подмножество множества ребер/дуг <math>E,\;U \subseteq E,</math> причем, если <math>(x,y) \in E</math> и <math>x,y \in W,</math> то обязательно

<math>(x,y) \in U.</math> Это определение подграфа мы будем называть сильным

* ''[[Линейный подграф графа|Линейный подграф]],''

* ''[[Остовный подграф]],''

* ''[[Порожденный подграф]],''

* ''[[Четный подграф]],''

* ''[[Поддерево]].''

* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

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

* Харари Ф. Теория графов. —  М.: Мир, 1973.