Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 2K vistas

    Problemas Resueltos Teoria de Grafos

    Cargado por

    jeison123411
    El documento contiene 15 preguntas sobre conceptos de grafos y teoría de grafos. Se presentan ejercicios relacionados con caminos eulerianos, distancias en digrafos, isomorfismos de grafos y el teorema de los cuatro colores. Se provee la solución detallada para cada pregunta.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Problemas Resueltos Teoria de Grafos

    Cargado por

    jeison123411
    2K vistas4 páginas
    El documento contiene 15 preguntas sobre conceptos de grafos y teoría de grafos. Se presentan ejercicios relacionados con caminos eulerianos, distancias en digrafos, isomorfismos de grafos y el teorema de los cuatro colores. Se provee la solución detallada para cada pregunta.

    Descripción original:

    problemas

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento contiene 15 preguntas sobre conceptos de grafos y teoría de grafos. Se presentan ejercicios relacionados con caminos eulerianos, distancias en digrafos, isomorfismos de grafos y el teorema de los cuatro colores. Se provee la solución detallada para cada pregunta.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    2K vistas4 páginas

    Problemas Resueltos Teoria de Grafos

    Cargado por

    jeison123411
    El documento contiene 15 preguntas sobre conceptos de grafos y teoría de grafos. Se presentan ejercicios relacionados con caminos eulerianos, distancias en digrafos, isomorfismos de grafos y el teorema de los cuatro colores. Se provee la solución detallada para cada pregunta.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 4

    10. Sea G un grafo conexo cuyos vrtices son {v1, v2, v3, v4, v5}.

    La
    v1
    v2
    sucesin (v1,v2,v3,v5,v1,) es:
    A) Un camino euleriano
    v3
    B) Un ciclo hamiltoniano
    C) Ninguno de los anteriores
    v4
    Solucin: el subgrafo asociado al camino es el de la figura.
    v5
    Un camino euleriano es un camino que contiene todas las
    aristas apareciendo cada una de ellas exactamente una vez.
    En nuestro caso desconocemos todas las aristas del grafo, no podemos asegurar
    que sea euleriano.
    x
    11. Dado el digrafo etiquetado
    2
    1
    1
    3

    7
    2

    1
    1
    2
    2

    y
    Cul es la distancia entre x e y?
    A)
    B) 5 C)12
    Solucin: siguiendo el algoritmo de Dijkstra y colocando en cada vrtice la
    distancia desde x, obtenemos:

    0
    1

    2
    2
    3

    5
    12. Cul de los siguientes grafos no se puede dibujar sin levantar el lpiz del papel y
    sin dibujar dos veces la misma arista?
    A)

    B)

    C)

    Solucin: para resolver este ejercicio hay que analizar el grado de cada vrtice.
    Para que se pueda dibujar en las condiciones pedidas debe ocurrir una de:
    Todos los grados son pares, entonces es un grafo euleriano, es decir, admite un
    circuito euleriano.
    Dos y exactamente dos vrtices tienen grado impar, entonces se podra dibujar un
    camino eulariano que parta de uno de los vrtices de grado impar y termine en el
    otro.
    Grafo A:
    3
    4
    2

    3
    4
    Admite un camino euleriano, partiendo de uno de los vrtices sealados por una
    flecha y terminando en el otro
    Grafo B:

    2
    Igual situacin que en el grafo A.
    Grafo3C:

    3
    4

    5
    4

    3
    3

    Tiene ms de dos vrtices con grado impar, luego no admite camino euleriano y no
    se puede dibujar sin levantar el lpiz del papel y sin dibujar dos veces la misma
    arista
    13. Los grafos de la figura, son isomorfos?

    A) No, porque uno es plano y el otro no

    B) S, pues existe un isomorfismo entre ellos.


    C) S, porque tienen el mismo nmero de vrtices y aristas.
    Solucin: son isomorfos puesto que se puede establecer un isomorfismo.
    La correspondencia a travs de los nmeros:
    2
    1

    8 6

    7
    8

    3
    10

    10
    5

    produce el mismo grafo G=(V,E), donde:


    V={1,2,3,4,5,6,7,8,9,10}
    E={12,19,16,24,23,3A,35,48,47,57,56,68,79,8A,9A}
    Se trata de un isomorfismo.

    14. Los dos grafos de la figura

    A) Son isomorfos pues tienen el mismo nmero de vrtices y de aristas.

    B) Son isomorfos porque se puede establecer un isomorfismo entre ellos


    C) No son isomorfos pues en uno hay dos vrtices de grado 2 y en el otro hay tres
    vrtices de grado 2.
    Solucin: analizando los grados de los vrtices
    Grados del grafo 1: 2, 3, 4, 2, 3, 4

    Grados del grafo 2: 2, 4, 2, 4, 2, 4


    Si existiera un isomorfismo se tendra que conservar el grado de los vrtices
    isomorfos.
    Dado que no se pueden hacer corresponder biunvocamente los vrtices de grado 2
    (por ejemplo), no puede existir un isomorfismo.
    15. Sea el mapa M de la figura

    A) M se puede colorear con tres colores diferentes.

    B) M necesita ms de tres colores para ser coloreado.

    C) Son necesarios ms de cuatro colores para colorear M.


    Solucin: segn el teorema de los cuatro colores, como mximo son necesarios
    cuatro colores para colorear un mapa.
    Las tres regiones internas de nuestro mapa necesitan tres colores distintos, dado
    que estn en contacto entre s.
    Como cada una de estas regiones internas toca a tres ms va a ser necesario un
    color ms para colorear el mapa.
    Una solucin con cuatro colores sera:
    4
    3

    4
    1

    También podría gustarte