4624
правки
K-Нумерация: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''K-Нумерация''' (''[[K-Numbering]]'') | '''K-Нумерация''' (''[[K-Numbering]]'') — | ||
''[[нумерация вершин]]'' [[уграф|уграфа]] <math>G</math>, которая определяется как последний член | ''[[нумерация вершин]]'' [[уграф|уграфа]] <math>\,G</math>, которая определяется как последний член | ||
<math>K_{[n]}</math> (<math>n</math> | <math>\,K_{[n]}</math> (<math>\,n</math> — число вершин в <math>\,G</math>) последовательности нумераций | ||
<math>K_{1}, \; K_{2}, \; \ldots, \; K_{n}</math> в которой <math>K_{1}</math> | <math>K_{1}, \; K_{2}, \; \ldots, \; K_{n},</math> в которой <math>\,K_{1}</math> — | ||
''обратная нумерация'' <math>G</math> и для любых <math>i \in [1,n)</math> и [[вершина|вершин]] <math>p | ''обратная нумерация'' <math>\,G</math> и для любых <math>i \in [1,n)</math> и [[вершина|вершин]] <math>\,p, q</math> | ||
справедливы два свойства: если <math>K_{i}(p) \in [1,i)</math>, то | справедливы два свойства: если <math>K_{i}(p) \in [1,i)</math>, то | ||
<math>K_{i+1}(p) = K_{i}(p)</math>; если <math>K_{i}(p), \; K_{i}(q) \in | <math>\,K_{i+1}(p) = K_{i}(p)</math>; если <math>\,K_{i}(p), \; K_{i}(q) \in | ||
[i,n]</math>, то <math>K_{i+1}(p) < K_{i+1}(q)</math> тогда и только тогда, когда | [i,n]</math>, то <math>\,K_{i+1}(p) < K_{i+1}(q)</math> тогда и только тогда, когда | ||
либо <math>p \in K_{i}\langle i\rangle</math> и <math>q \not \in K_{i}\langle i\rangle</math>, либо <math>K_{i}(p) < | либо <math>p \in K_{i}\langle i\rangle</math> и <math>q \not \in K_{i}\langle i\rangle</math>, либо <math>\,K_{i}(p) < | ||
K_{i}(q)</math> и <math>\{p,q\} \subseteq K_{i}\langle i\rangle</math> или <math>\{p,q\} \cap | K_{i}(q)</math> и <math>\{p,q\} \subseteq K_{i}\langle i\rangle</math> или <math>\{p,q\} \cap | ||
K_{i}\langle i\rangle = \emptyset</math>. | K_{i}\langle i\rangle = \emptyset</math>. | ||
Относительно обозначений см. ''[[F-область]]''. | Относительно обозначений см. ''[[F-Область|F-область]]''. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
