10 Abril, 2020, 15:01 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Grafos - Polinomio cromático  (Leído 6806 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Alvarodt88
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 79


Ver Perfil
« : 07 Febrero, 2008, 17:56 »

Buenas! no sabía bien dónde exponer mi duda, el ejercicio es que te dan una matriz de adyacencia, por ejemplo,

0 1 0 1 0 1 0
1 0 1 0 1 0 1
0 1 0 1 0 1 0
1 0 1 0 1 0 1
0 1 0 1 0 1 0
1 0 1 0 1 0 1
0 1 0 1 0 1 0

Imagino que hemos de dibujar el grafo asociado (si con la matriz basta agradecería me lo indicarais), y luego lo que no sé es como obtengo el polinomio cromático (creo que este grafo es bipartido y por tanto su número cromático es 2, pero lo que quiero saber es como hacerlo para cualquiera)

Muchas gracias
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 08 Febrero, 2008, 05:58 »

Hola

 Que aparezca un [texx]1[/texx] el la posición [texx]i,j[/texx] significa que el vértice [texx]i[/texx] está unido con el [texx]j[/texx].

 Por tanto en tu caso se están uniendo todos los vértices pares con los impares, así que efectivamente se trata de un grafo bipartito [texx]K_{3,4}[/texx].

 No estoy seguro de que haya un método manejable y sistemático para calcular el polinomio cromático de cualquier grafo. Ahi alguna relación recursiva, que permite ir reduciendo el número de aristas pero en la práctica ese sistema es inviable por pesado.

 En el caso de un grafo bipartito puedes razonar de la siguiente forma. Lo haré para tu caso particular, pero puede extenderse en general.

 Supongamos que tenemos [texx]x[/texx] colores. Si para los [texx]3[/texx] vértices pares usamos [texx]y[/texx] colores para los [texx]4[/texx] restantes podremos usar [texx]x-y[/texx] colores, y por tanto estos pueden colorearse de (x-y) formas distintas.

 - Para y=1. Hay [texx]x[/texx] formas de escoger 1 color entre los colore totales y una única forma de colorear los 3 vértices. Por tanto en este caso las formas posibles de colorear el grafo son:

[texx]x(x-1)^4[/texx]

 - Para y=2. Hay [texx]x(x-1)[/texx] formas de escoger 2 colores ordenados entre los colores totales. El primero se usará en un único vértice y el segundo en los otros dos. Hay tres formas de elegir cual es el vértice del color único. Por tanto en este caso las formas posibles de colorear el grafo son:

[texx]3x(x-1)(x-1)^4[/texx]

 - Para y=3. Hay [texx]x(x-1)(x-2)[/texx] formas de escoger 3 colores ordenados entre los colores totales. En ese mismo orden los usamos para colorear los vértices 2,4,6. Por tanto en este caso las formas posibles de colorear el grafo son:

[texx]x(x-1)(x-2)(x-1)^4[/texx]

 En definitiva el polinomio cromático es:

[texx]p(x)=x(x-1)^4+3x(x-1)^5+x(x-1)^5(x-2)[/texx]

 Hay una forma de sistematizar esto para cualquier grafo bipartito [texx]p,q[/texx]. Sólo hay que usar un poco de teoría combinatoria (no muy difícil si se ha cursado algo de matemática discreta) que involucra a los número de Stirling.

Saludos.
En línea
Alvarodt88
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 79


Ver Perfil
« Respuesta #2 : 08 Febrero, 2008, 10:22 »

Muchas gracias el_manco, esto es de matemática discreta, me examino a las 5 y concretamente combinatoria es el tema que he dejado de lado porque me ha parecido imposible, entiendo ciertos problemas pero porque los tengo resueltos, y ya lo demás si lo llevo bien así que espero que de combinatoria caiga lo mínimo
En línea
getdan
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 102



Ver Perfil
« Respuesta #3 : 08 Febrero, 2008, 13:45 »

acordate de los numeros cromaticos de grafos famosos también, por ejemplo de un grafo completo es igual a la cantidad de vertices, de un grafo arbol creo que 2, un camino simple 2, un ciclo 2 también, hacete el dibujo del grafo y analiza como lo podes pintar(queda más intuitivo), para combinatoria si no sabes mucho lo bueno es hacer muchos ejercicios porque hay muchos que son similiares.
Bueno Saludos.
En línea
Alvarodt88
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 79


Ver Perfil
« Respuesta #4 : 09 Febrero, 2008, 10:59 »

Gracias por vuestra ayuda, al final creo que he suspendido el exámen porque ha caido uno de un polinomio cromático como me temía y no supe hacerlo, luego otro de combinatoria que tampoco... y uno superraro de dar las dos últimas cifras de 37^2008 pero ya me han comentado como se hacía

Sí teneis algún enlace a ejercicios resueltos de combinatoria o buenas explicaciones, porque me he pasado el día buscando en google y no he visto nada interesante
En línea
getdan
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 102



Ver Perfil
« Respuesta #5 : 09 Febrero, 2008, 11:53 »

mira aca tenes la pagina de mi facultad:
http://imerl.fing.edu.uy/matdisc1/practico.htm tiene los prácticos con las soluciones no te fundamenta mucho pero al menos te dice cuanto dan y eso, luego te recomiendo para combinatoria el Ralp Grimaldi ese tema lo tiene muy pulido y lleno de ejemplos con explicación para los otros temas como grafos no te recomiendo mucho el Grimadi ni tampoco para congruencias si es que distes por eso ultimo que decís, pero combinatoria muy bueno esta.
Bueno suerte para la próxima.
Saludos
En línea
Alvarodt88
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 79


Ver Perfil
« Respuesta #6 : 09 Febrero, 2008, 13:03 »

Gracias getdan, estan muy bien, es una lástima que no se explique como se hacen
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!