Русская Википедия:Многочлен Боллобаша — Риордана
Материал из Онлайн справочника
Многочлен Боллобаша — Риордана — это инвариантный многочлен графов на ориентируемых поверхностях от трех переменных или инвариант Шаблон:Нп3 от четырех переменных, обобщающий многочлен Татта.
История
Эти многочлены открыли Бела Боллобаш и Оливер Риордан в 2001 году.
Определение
Многочлен Боллобаша — Риордана от трех переменных задаётся следующей формулой:
- <math>R_G(x,y,z) =\sum_F x^{r(G)-r(F)}y^{n(F)}z^{k(F)-bc(F)+n(F)}</math>
где
- v(G) — это число вершин графа G;
- e(G) — это число ребер графа G;
- k(G) — это число компонент связности графа G;
- r(G) — это ранг графа G, r(G) = v(G) − k(G);
- n(G) — это контурный ранг графа, n(G) = e(G) − r(G);
- bc(G) — это число связанных компонентов грани графа G.
См. также
Литература
