What are Clique Polynomials? [Graph Theory Tutorial]
What are clique polynomials? This video introduces you to clique polynomials and covers their interesting properties. It shows you how to find the clique polynomial of a graph through examples.
Clique polynomials are built from the number of cliques in an undirected simple graph. The clique polynomial of an undirected graph G is defined as (c_0) + (c_1)x^1 + (c_2)x^2 + ... + (c_n)x^n, where c_i is the number of i-cliques in G. Note that c_0, or the number of 0 cliques, is always 1 for any graph, and that this polynomial terminates with the term corresponding to the largest clique(s) in the graph, an n-clique. To find the clique polynomial of a graph, you would first count the number of cliques of each size in the graph and then apply each as the coefficient of the term with the same degree as the size of that clique. Different (non-isomorphic) graphs can have the same clique polynomial, but isomorphic graphs always have the same clique polynomial. Also, we can find the clique polynomial of certain graph products based off the clique polynomials of the factor graphs. Finally, there are several ways to tell whether a polynomial could be a clique polynomial of some graph or not, and we'll cover them in this video.
See these links for more info:
https://citeseerx.ist.psu.edu/viewdoc...
https://arxiv.org/abs/1910.11196
https://mathworld.wolfram.com/CliqueP...
Thanks for watching!
Смотрите видео What are Clique Polynomials? [Graph Theory Tutorial] онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Vital Sine 17 Май 2021, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 1,093 раз и оно понравилось 28 людям.