Constructible graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Constructible graph''' --- конструируемый граф. Graph <math>G</math> is '''constructible''' if it can be built vertex-by-vertex so that a vert…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | ||
* | |||
Текущая версия от 10:48, 24 октября 2018
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
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.