Date post: | 15-Oct-2015 |
Category: |
Documents |
Upload: | alexander-pl |
View: | 95 times |
Download: | 0 times |
of 16
5/25/2018 Polinomio cromatico
1/16
Coloracin de vrtices
Polinomio Cromtico
5/25/2018 Polinomio cromatico
2/16
Coloracin de vrtices
Si dispongo de k colores, de cuntas formas
distintas puedo colorear los vrtices de un grafo?
1942, Birkhoff and Lewis introducen el polinomio cromtico ensu intento de demostrar el teorema de los 4 colores
Polinomio cromtico Dado un grafo G y un conjunto de colores k,
definimos la funcin P(G, k)como el nmero de formas distintas de
colorear G usando los k colores.
5/25/2018 Polinomio cromatico
3/16
Coloracin de vrtices
Propiedades
P(G,0)=0
Si H es un subgrafo recubridorde G P(G,k) P(H,k)
P(G,k)>0 si y slo si G es k-coloreable
P( Gi, k)= P(Gi, k), Gi disjuntos dos a dos.r
i 1
r
i 1
si k
5/25/2018 Polinomio cromatico
4/16
P(On, k)=kn, con Ones el grafo trivial de n vrtices
P(Kn, k)=k(k-1)(k-2)(k-n+1)
Coloracin de vrtices
Polinomios cromticos de algunas familias de grafos
conocidas
P(Ln, k)=k(k-1)n-1
, con Ln el grafo camino de n vrtices
Observacin: si G tiene n vrtices:
K(k-1)(k-2)(k-n+1) P(G,k) kn
P(An, k)= ejerc., con An un rbol con n vrtices.
5/25/2018 Polinomio cromatico
5/16
Coloracin de vrtices
K colores
C4 k
5/25/2018 Polinomio cromatico
6/16
Coloracin de vrtices
k colores
C4 k
k-1
5/25/2018 Polinomio cromatico
7/16
Coloracin de vrtices
k colores
C4 k
k-1
k-1
5/25/2018 Polinomio cromatico
8/16
Coloracin de vrtices
k colores
C4 k
k-1
k-1
k-1?
5/25/2018 Polinomio cromatico
9/16
Coloracin de vrtices
k colores
C4 k
k-1
k-1
K-2?
Depende
Cmo calculamos el polinomio cromtico de C4?
5/25/2018 Polinomio cromatico
10/16
Coloracin de vrtices
Operaciones que se usan en el clculo del polinomio cromtico
Eliminacin de una arista
Contraccin de una arista: Dado el grafo Gy sea a={u,v} una aristasuya, llamaremos contraccin de la arista adel grafo Ga la operacin
resultante de considerar los vrtices uy vcomo un nico vrtice
a
v
u
5/25/2018 Polinomio cromatico
11/16
Coloracin de vrtices
Operaciones que se usan en el clculo del polinomio cromtico
Eliminacin de una arista
Contraccin de una arista: Dado el grafo Gy sea a={u,v} una aristasuya, llamaremos contraccin de la arista adel grafo G (Ga) a la
operacin resultante de considerar los vrtices uy vcomo un nico
vrtice.
u
a
v
G
vu
Ga
5/25/2018 Polinomio cromatico
12/16
Coloracin de vrtices
Teorema: Sean G un grafo, a={u,v} una arista suya y k un nmero
natural, entonces:
P(G,k) = P(G-a,k) - P(Ga,k)
Algoritmo Eliminacin-contraccin (come aristas)
Algoritmo Adicin-contraccin
Recursivamente
5/25/2018 Polinomio cromatico
13/16
Coloracin de vrtices
= -a
Ga=C4
G- aG = -
= +
GG- aC4 = +
5/25/2018 Polinomio cromatico
14/16
Coloracin de vrtices
Ejercicio: Obtener el polinomio cromtico de Cn, para cualquier n.
= -
Cn-1LnCn = -
a a
P(Cn,k)=(k-1)n+(-1)n(k-1)
5/25/2018 Polinomio cromatico
15/16
Coloracin de vrtices
Teorema: Para un grafo simple G de orden n y tamao m,
P(G,k) verifica que:
es un polinomio de grado n en k con coeficientes enteros su trmino independiente es 0
sus coeficientes alternan el signo
y el coeficiente de kn-1esm.
5/25/2018 Polinomio cromatico
16/16
Coloracin de vrtices
Otra informacin que podemos obtener del polinomio cromtico:
el nmero de componentes conexas del grafo coincide con el menor
grado de los sumandos del polinomio cromtico
el nmero cromtico es el nmero entero ms pequeo para el que
el polinomio cromtico es distinto de 0
Ojo!!, el polinomio cromtico no caracteriza el grafo