Constructible graph: различия между версиями

'''Constructible graph''' — ''[[конструируемый граф]].''

[[graph, undirected graph, nonoriented graph|Graph]] <math>\,G</math> is '''constructible''' if it can be built vertex-by-vertex so that a [[vertex]] <math>\,x</math> can be added to the currently constructed [[induced (with vertices) subgraph|induced subgraph]] <math>\,G_{x}</math> of <math>\,G</math> if there exists a vertex <math>\,y</math> of <math>\,G_{x}</math> which is [[adjacent vertices|adjacent]] in <math>\,G</math> to <math>\,x</math> and to all neighbors of <math>\,x</math> belonging to <math>\,G_{x}</math>.

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

vertices of <math>\,G</math> induced by <math>\,\leq</math>, will be called a '''[[constructing order]]''' and a '''[[constructing enumeration]]''', respectively.

==See also==

* ''[[Dismantlable graph]]''.

 

 

* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.