Constructible graph

Материал из WikiGrapp
Версия от 13:17, 15 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Constructible graph''' --- конструируемый граф. Graph <math>G</math> is '''constructible''' if it can be built vertex-by-vertex so that a vert…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Constructible graph --- конструируемый граф.

Graph [math]\displaystyle{ G }[/math] is constructible if it can be built vertex-by-vertex so that a vertex [math]\displaystyle{ x }[/math] can be added to the currently constructed induced subgraph [math]\displaystyle{ G_{x} }[/math] of [math]\displaystyle{ G }[/math] if there exists a vertex [math]\displaystyle{ y }[/math] of [math]\displaystyle{ G_{x} }[/math] which is adjacent in [math]\displaystyle{ G }[/math] to [math]\displaystyle{ x }[/math] and to all neighbors of [math]\displaystyle{ x }[/math] belonging to [math]\displaystyle{ G_{x} }[/math].

A graph [math]\displaystyle{ G }[/math] is said to be constructible if there is a well-order [math]\displaystyle{ \leq }[/math] on [math]\displaystyle{ V(G) }[/math] such that every vertex [math]\displaystyle{ x }[/math] which is not the smallest element of [math]\displaystyle{ (V(G),\leq) }[/math] is dominated by some vertex [math]\displaystyle{ y \neq x }[/math] in the subgraph of [math]\displaystyle{ G }[/math] induced by the set [math]\displaystyle{ \{z \in V(G): z \leq x\} }[/math]. The well-order [math]\displaystyle{ \leq }[/math] on [math]\displaystyle{ V(G) }[/math], and the enumeration of the vertices of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ \leq }[/math], will be called a constructing order and a constructing enumeration, respectively.

See

  • also Dismantlable graph.