Наследственное свойство графа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Наследственное свойство графа''' (''Hereditary property of a graph'') - свойство <math>P</math> г...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Наследственное свойство графа''' (''Hereditary property of a graph'') -
'''Наследственное свойство графа''' (''[[Hereditary property of a graph]]'')
свойство <math>P</math> графа <math>G</math> такое, что каждый подграф графа <math>G</math> также
свойство <math>P</math> [[граф|графа]] <math>G</math> такое, что каждый [[подграф]] графа <math>G</math> также
обладает этим свойством. Примерами наследственных свойств служат
обладает этим свойством. Примерами наследственных свойств служат
несвязность, ацикличность, двудольность, планарность.
[[несвязный орграф|несвязность]], [[ациклический граф|ацикличность]], [[двудольный граф|двудольность]], [[планарный граф|планарность]].
==Литература==
==Литература==
[Харари]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия от 11:46, 13 мая 2011

Наследственное свойство графа (Hereditary property of a graph) — свойство [math]\displaystyle{ P }[/math] графа [math]\displaystyle{ G }[/math] такое, что каждый подграф графа [math]\displaystyle{ G }[/math] также обладает этим свойством. Примерами наследственных свойств служат несвязность, ацикличность, двудольность, планарность.

Литература

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