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