Nella teoria dei grafi viene utilizzato un numero cromatico per mostrare il numero di colori necessari per colorare nei vertici di un grafo, cioè, i punti di intersezione, senza qualsiasi vertici adiacenti, avendo lo stesso colore. Ad esempio, un triangolo avrebbe un numero cromatico di tre, ma un quadrato avrebbe un numero cromatico di due. Un polinomio cromatico è un concetto simile nella teoria dei grafi, ma cerca il maggior numero di modi che un grafico può essere colorato usando un certo numero di colori. Polinomi cromatici sono noti solo per alcuni tipi di grafici.
Istruzioni
• Capire il polinomio cromatico per un grafico di triangolo con la seguente formula: t ((t − 1) ^ 2)(t − 2), dove "t" è il numero di colori da utilizzare. Un grafico di triangolo Mostra una forma fatta di molti K al potere 2rd dei triangoli. Basta inserire il numero di colori che si desidera il grafico per avere nella formula per trovare il polinomio cromatico. Ad esempio, per cinque colori, il numero cromatico è: 5((5-1)^2)(5-2), che è: 240.
• Trovare il polinomio cromatico di un grafo completo, che è una forma con ogni coppia di vertici distinti collegati da un bordo. Utilizzare la seguente formula: t(t-1)(t-2) su fino a t-n, dove "n" è il numero di archi del grafo e "t" è il numero di colori per rappresentare graficamente i vertici. Per un grafo completo con quattro colori e due bordi, il polinomio cromatico è: 4(4-1)(4-2) = 24.
• Calcolare il polinomio cromatico per un grafico dell'albero con la formula:
t (t − 1) ^(n − 1)
Un grafico dell'albero è costituito da nodi o vertici che si diramano da uno a altro come rami di un albero. In questa formula, "n" è il numero di vertici dell'albero. Così un grafico dell'albero con cinque vertici e due colori avrebbe un polinomio cromatico di: 2(2-1) ^(5-1) = 16.
• Calcolare il polinomio cromatico per un grafico del ciclo, che visualizza un numero di vertici connessi a forma di anello. Utilizzare questa formula:
(t − 1) ^ n + (1)^(n) − (t − 1)
In questa formula, "n" è il numero di vertici e "t" è il numero di colori. Un grafico di ciclo con due vertici e due colori ha un polinomio cromatico di: (2-1)^2+(-1)^2)(2-1) = 2.
• Calcolare l'ultimo tipo di grafico per il quale la formula del polinomio cromatico è noto, il grafico di Peterson, con la formula seguente, che vieta:
t(t − 1) (t − 2) (t7 − 12t6 + 67t5 − 230t4 + 529t3 − 814t2 + 775t − 352)
Un grafico di Peterson è un grafico con 10 vertici e 15 bordi. In questa formula, "t" è il numero di colori da utilizzare per il grafico. Così un polinomio cromatico con due colori per un grafico di Peterson--2 (2 − 1) (2 − 2) (2− 7 1226 + 672− 5 23024 + 5292− 3 81422 + 7752 − 352) - è 0, perché la prima parte dell'equazione è uguale a zero e Annulla la seconda parte. Ciò ha senso perché un polinomio cromatico esprime il numero di colori necessari affinché nessun due vertici adiacenti hanno lo stesso colore. Questo non funziona nel grafico Peterson perché i vertici sono accoppiati uno accanto a altro.