Многочлен Боллобаша — Риордана
Многочлен Боллобаша — Риордана — это инвариантный многочлен графов на ориентируемых поверхностях от трех переменных или инвариант Шаблон:Нп3 от четырех переменных, обобщающий многочлен Татта.
История
Эти многочлены открыли Бела Боллобаш и Оливер Риордан в 2001 году.
Определение
Многочлен Боллобаша — Риордана от трех переменных задаётся следующей формулой:
где
- 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.