Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Polinomios Cromáticos.

No description
by

Adolfo Urbina

on 10 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Polinomios Cromáticos.

photo credit Nasa / Goddard Space Flight Center / Reto Stöckli
Polinomios Cromáticos.
¿Que es un polinomio cromático?
Cuenta el numero de maneras en las puede ser coloreado un grafo usando nada mas que un numero de colores dado.
Si G es una gráfica y X >=0 es un entero, sea P G (X) el numero de formas de obtener una coloración propia de G con X o menos colores. Como P G (X) es un numero definido para cada X, se observa que PG es una función.
Teorema 1:
Gracias por su atención!!!
Si G es una gráfica disconexa con componentes G1, G2, ..., Gm, entonces
PG(x)=PG1(x)PG2(x)....PGm(x), el producto de los polinomios cromáticos para cada componente.
Teorema 2:
Sea G={V, E, y } una gráfica sin aristas múltiples , y e pertenece a E, es decir, e={a, b}, se a Ge la subgráfica de G obtenida al eliminar e, y sea G^e la gráfica cociente de G al unir los extremos de e entonces:
PG(x)=PGe(x)-PG^e(x)
Ejemplo:
Para cualquier n>=1, considere la gráfica completa Kn, suponga que de nuevo se puede utilizar x colores para colorear Kn. si x<n, no es posible obtener una coloración propia . Así, x>=n. Se puede colorear el vértice V1 con cualquiera de los X colores, para el vértice V2 solo restan X-1 ya que V1 esta conectado con V2, solo se puede colorear a V3 con X-2 ya que V3 esta conectado con V1 y V2 y no se pueden utilizar de nuevo los colores de V1 y V2.



Utilizando el principio de multiplicación de conteo, se determina que Pkn (x)= x(x-1)(x-2)... (x-n+1. Esto demuestra que X(Kn)=n. Observe que si al menos existen n colores, entonces Pkn(x) es el numero de permutaciones de x objetos tomados de n en n.
Full transcript