En el ejercicio 2 de la parte de MO del segundo parcial de julio de 2015 se pide ver si α (Definido como el tamaño máximo de una anticadena) tiene determinado valor. Pero no estoy seguro de cómo se define el tamaño máximo de una anticadena. Pienso que es la máxima cantidad de vértices posibles tales que no existe una cadena entre ninguno de ellos, pero no lo tengo muy claro.
En respuesta a Franco Sebastián Biardo Sienra
Re: Anticadena más larga
Hola,
Aqui te paso al link del pizarrón de la clase de hoy, al final de todo agregué la resolución de ese ejercicio, Cualquier cosa preguntá .
https://jamboard.google.com/d/1176hOF_EVTwajIfpCWqwRciZjraTd4fc0IjZ46-MPig/edit?usp=sharing
Saludos,
Paula
Aqui te paso al link del pizarrón de la clase de hoy, al final de todo agregué la resolución de ese ejercicio, Cualquier cosa preguntá .
https://jamboard.google.com/d/1176hOF_EVTwajIfpCWqwRciZjraTd4fc0IjZ46-MPig/edit?usp=sharing
Saludos,
Paula
En respuesta a Paula Isabel Cardoso Garcia
Re: Anticadena más larga
Paula, buenos días.
Con respecto al ejercicio 4 del parcial junio 2018 (cantidad de subgrafos de G homeomorfos a K2):
¿Por qué en el caso de V se toman dos caminos por cada par de vértices?
Por ejemplo, el subgrafo formado por V = {1,2} y su arista e = {1,2} es el mismo que nombrar {2,1} ... no entiendo la "multiplicación x 2" en el conteo.
Espero tu respuesta
Saludos
Con respecto al ejercicio 4 del parcial junio 2018 (cantidad de subgrafos de G homeomorfos a K2):
¿Por qué en el caso de V se toman dos caminos por cada par de vértices?
Por ejemplo, el subgrafo formado por V = {1,2} y su arista e = {1,2} es el mismo que nombrar {2,1} ... no entiendo la "multiplicación x 2" en el conteo.
Espero tu respuesta
Saludos
En respuesta a Gonzalo Javier Diaz Ferreira
Re: Anticadena más larga
Buenas tardes Javier,
Ahi la multiplicación por dos corresponde a los dos subgrafos posibles que podemos formar con dos extremos dados. Por ejemplo con los vertices 1 y 2 como extremos podemos formar el subgrafo que vos decis o el dado por el camino (1,2',3,2). Este último es un grafo homemorfo a K2 porque se obtiene a partir de K2 haciendo subdivisiones elementales. Osea no solo tenemos que identificar los subgrafos isomorfos a K2 sino también los que solamente sean homemorfos (que son los de la forma Pn).
Ahi modifique la pizarra con unos dibujitos para explicar esto, capaz se entiende mejor ahi.
Saludos,
Paula
Ahi la multiplicación por dos corresponde a los dos subgrafos posibles que podemos formar con dos extremos dados. Por ejemplo con los vertices 1 y 2 como extremos podemos formar el subgrafo que vos decis o el dado por el camino (1,2',3,2). Este último es un grafo homemorfo a K2 porque se obtiene a partir de K2 haciendo subdivisiones elementales. Osea no solo tenemos que identificar los subgrafos isomorfos a K2 sino también los que solamente sean homemorfos (que son los de la forma Pn).
Ahi modifique la pizarra con unos dibujitos para explicar esto, capaz se entiende mejor ahi.
Saludos,
Paula
En respuesta a Paula Isabel Cardoso Garcia
Re: Anticadena más larga
Entiendo,
En realidad estaba restringiendo sólo a W = {1,2,2'} pero con esos vértices también está el camino que contiene a 3, y es 1 - 2 ... entonces en realidad es un camino con los vértices de W.
Muchas gracias por la respuesta
Saludos.-