Tutte, polinomio di

Tutte, polinomio di

Tutte, polinomio di in teoria dei grafi, polinomio in due variabili associato a un grafo non orientato G = (X, A). Prende il nome da W.Th. Tutte ed è così definito:

in cui la sommatoria varia su tutti i grafi parziali (X, B) di G, e k(B) denota il numero delle componenti connesse di ogni grafo parziale (X, B). Il polinomio di Tutte dà informazioni sulle connessioni del grafo, nel senso che a grafi isomorfi è associato lo stesso polinomio di Tutte, anche se il viceversa non è vero.