What are Clique Polynomials? [Graph Theory Tutorial] скачать в хорошем качестве

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!