Аноним

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

Материал из WikiGrapp
нет описания правки
(Новая страница: «'''Constructible graph''' --- конструируемый граф. Graph <math>G</math> is '''constructible''' if it can be built vertex-by-vertex so that a vert…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Constructible graph''' --- конструируемый граф.  
'''Constructible graph''' — ''[[конструируемый граф]].''


Graph <math>G</math> is '''constructible''' if it can be built vertex-by-vertex
[[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>.
so that a vertex <math>x</math> can be added to the currently constructed
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 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
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
<math>\leq</math> on <math>V(G)</math> such that every vertex <math>x</math> which is not the
vertices of <math>\,G</math> induced by <math>\,\leq</math>, will be called a '''[[constructing order]]''' and a '''[[constructing enumeration]]''', respectively.
smallest element of <math>(V(G),\leq)</math> is ''dominated'' by some vertex <math>y
==See also==
\neq x</math> in the subgraph of <math>G</math> induced by the set <math>\{z \in V(G): z
* ''[[Dismantlable graph]]''.
\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==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
*also ''Dismantlable graph''.