Minor of a graph

Материал из WikiGrapp
Версия от 14:44, 2 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Minor of a graph''' --- минор графа. A graph <math>H</math> obtained from <math>G</math> by a series of vertex deletions, edge deletions and '' contra…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Minor of a graph --- минор графа.

A graph H obtained from G by a series of vertex deletions, edge deletions and contractions of an edge. A class of graphs {\mathcal
F} is called minor-closed if for every graph G in {\mathcal F}, every minor of G is also a member of {\mathcal F}. For a class of graphs {\mathcal F}, a finite obstruction set S is a finite set of minors such that a graph is a member of {\mathcal F} if and only if it does not contain an element of S as a minor.

The graphs in every minor-closed class of graphs are recognizable in {\mathcal O}(n^{3}) time.