Что такое кликовые многочлены? [Учебное пособие по теории графов]

Что такое многочлены клик? Это видео знакомит вас с многочленами клик и рассматривает их интересные свойства. В нем показано, как на примерах найти многочлен клик графа. Многочлены клик строятся из числа клик в неориентированном простом графе. Многочлен клик неориентированного графа G определяется как (c_0) + (c_1)x^1 + (c_2)x^2 + ... + (c_n)x^n, где c_i — число i-кликов в G. Обратите внимание, что c_0, или число 0 клик, всегда равно 1 для любого графа, и что этот многочлен заканчивается членом, соответствующим наибольшей клике (кликам) в графе, n-клике. Чтобы найти многочлен клик графа, сначала нужно подсчитать число клик каждого размера в графе, а затем применить каждый из них в качестве коэффициента к члену той же степени, что и размер этой клики. Различные (неизоморфные) графы могут иметь один и тот же кликовый многочлен, но изоморфные графы всегда имеют один и тот же кликовый многочлен. Кроме того, мы можем найти кликовый многочлен некоторых произведений графов на основе кликовых многочленов фактор-графов. Наконец, существует несколько способов определить, может ли многочлен быть кликовым многочленом какого-либо графа или нет, и мы рассмотрим их в этом видео. См. эти ссылки для получения дополнительной информации: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.401.2886&rep=rep1&type=pdf https://arxiv.org/abs/1910.11196 https://mathworld.wolfram.com/CliquePolynomial.html Спасибо за просмотр!