Constructible graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

See also


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