Многочлен Боллобаша — Риордана

Многочлен Боллобаша — Риордана — это инвариантный многочлен графов на ориентируемых поверхностях от трех переменных или инвариант Шаблон:Нп3 от четырех переменных, обобщающий многочлен Татта.

История

Эти многочлены открыли Бела Боллобаш и Оливер Риордан в 2001 году.

Определение

Многочлен Боллобаша — Риордана от трех переменных задаётся следующей формулой:

$R_G(x,y,z)=\sum _F{x}^{r(G)-r(F)}{y}^{n(F)}{z}^{k(F)-bc(F)+n(F)}$

где

• 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.

См. также

• Инвариант графа

Литература

• Шаблон:Citation
• Шаблон:Citation