Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 46 vistas

    Problemario 3

    Cargado por

    ESTEBAN INFANTE GONZALEZ
    Este documento presenta una serie de problemas relacionados con la representación de grafos mediante listas de adyacencia y matrices de adyacencia. Se piden representar varios grafos utilizando estas estructuras y dibujar los grafos a partir de sus matrices de adyacencia. También se incluyen preguntas sobre grafos dirigidos y la validez de usar matrices booleanas simétricas como matrices de adyacencia.

    Copyright:

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

    Problemario 3

    Cargado por

    ESTEBAN INFANTE GONZALEZ
    46 vistas4 páginas
    Este documento presenta una serie de problemas relacionados con la representación de grafos mediante listas de adyacencia y matrices de adyacencia. Se piden representar varios grafos utilizando estas estructuras y dibujar los grafos a partir de sus matrices de adyacencia. También se incluyen preguntas sobre grafos dirigidos y la validez de usar matrices booleanas simétricas como matrices de adyacencia.

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta una serie de problemas relacionados con la representación de grafos mediante listas de adyacencia y matrices de adyacencia. Se piden representar varios grafos utilizando estas estructuras y dibujar los grafos a partir de sus matrices de adyacencia. También se incluyen preguntas sobre grafos dirigidos y la validez de usar matrices booleanas simétricas como matrices de adyacencia.

    Copyright:

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

    Problemario 3

    Cargado por

    ESTEBAN INFANTE GONZALEZ
    Este documento presenta una serie de problemas relacionados con la representación de grafos mediante listas de adyacencia y matrices de adyacencia. Se piden representar varios grafos utilizando estas estructuras y dibujar los grafos a partir de sus matrices de adyacencia. También se incluyen preguntas sobre grafos dirigidos y la validez de usar matrices booleanas simétricas como matrices de adyacencia.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 4

    A continuación se presentan un conjunto de problemas que se deberán resolver utilizando lo visto en clase.

    Cada
    ejercicio tiene una cantidad de puntos determinada los cuales se asignarán sólo si el ejercicio es correcto y completo.

    1. (4 puntos) Para cada grafos de la Figura 1, utiliza una lista de adyacencia para la representación computacional.

    (a) G1 (b) G2 (c) G3

    Vértice Vértices de Vértice Vértices de Vértice Vértices de


    Adyacencia Adyacencia Adyacencia
    a b, c, d a b, d a a, b, c, d
    b a, d b a, d, e b d
    c a, d c d, e c a, b
    d a, b, c d a, b, c d b, c, d
    e b, c

    (d) G4

    Figura 1: G1 - G4
    Vértice Vértices de
    Adyacencia
    a b, d
    b a, c, d, e
    c b, c
    d a, e
    e c, e

    2. (4 puntos) Representa cada grafo de la Figura 1, mediante una matriz de adyacencia.


    1.
    a b c d
    a 0 1 1 1
    b 1 0 0 1
    c 1 0 0 1
    d 1 1 1 0

    2.
    a b c d e
    a 0 1 0 1 0
    b 1 0 0 1 1
    c 0 0 0 1 1
    d 1 1 1 0 0
    e 0 1 1 0 0

    3.
    a b c d
    a 1 1 1 1
    b 0 0 0 1
    c 1 1 0 0
    d 0 1 1 1

    4.
    a b c d e
    a 0 1 0 1 0
    b 1 0 1 1 1
    c 0 1 1 0 0
    d 1 0 0 0 1
    e 0 0 1 0 1

    3. (4 puntos) Representa cada uno de los siguientes grafos mediante una matriz de adyacencia.
    1. K4
    0 1 1 1
    1 0 1 1
    1 1 0 1
    1 1 1 0
    2. K1,4
    0 1 1 1 1
    1 0 0 0 0
    1 0 0 0 0
    1 0 0 0 0
    1 0 0 0 0
    3. K2,3
    0 0 1 1 1
    0 0 1 1 1
    1 1 0 0 0
    1 1 0 0 0
    1 1 0 0 0
    4. C4
    0 1 0 1
    1 0 1 0
    0 1 0 1
    1 0 1 0
    5. W4
    0 1 0 1 1
    1 0 1 0 1
    0 1 0 1 1
    1 0 1 0 1
    1 1 1 1 0
    6. Q3
    0 1 1 0 1 0 0 0
    1 0 0 1 0 1 0 0
    1 0 0 1 0 0 1 0
    0 1 1 0 0 0 0 1
    1 0 0 0 0 1 1 0
    0 1 0 0 1 0 0 1
    0 0 1 0 1 0 0 1
    0 0 0 1 0 1 1 0

    4. (4 puntos) Dadas las matrices de adyacencia 1a, 1b y 1c, dibuje el grafo correspondiente.

    0 1 0
    1 0 1 (1a)
    0 1 0

    0 0 1 1
    0 0 1 0
    1 1 0 1
    1 1 1 0
    (1b)
    0 0 1 1
    0 0 1 0 (1c)
    1 1 0 1
    1 1 1 0

    5. (4 puntos) Por cada grafo de la Figura 2, represente cada uno de ellos utilizando una matriz de adyacencia.

    (a) G5 (b) G6 (c) G7

    Figura 2: G5 - G7
    a b c d a b c d
    a 0 0 1 0 a b c d
    a 0 3 0 1
    b 0 0 1 2 a 1 0 2 1
    b 3 0 1 0
    c 1 1 0 1 b 0 1 1 2
    c 0 1 0 3
    d 0 2 1 0 c 2 1 1 0
    d 1 0 3 0
    d 1 2 0 1

    6. (4 puntos) Dadas las matrices de adyacencia 2a, 2b y 2c, dibuje el grafo no dirigido correspondiente.
    1 3 3
    3 0 4 (2a)
    2 4 0

    1 2 0 1
    2 0 3 0 (2b)
    0 3 1 1
    1 0 1 0

    0 1 3 0 4
    ⎡12 1 3 0⎤⎥
    ⎢
    ⎢31 1 0 1⎥(2c)
    ⎢03 0 0 2⎥
    ⎣40 1 2 3⎦
    Teoría de Grafos Actividad 3 - Page of 10 Fecha: 2 de febrero de 2022

    7. (4 puntos) Para cada grafo de la Figura 3, halla la matriz de adyacencia del multigafo dirigido correspondiente.

    (a) G8 (b) G9 (c) G10


    a b c d
    a 0 1 0 0
    Figura 3: G8 - G10
    b 0 1 1 0
    c 0 1 1 1 a b c d
    a b c d
    d 1 0 0 0 a 1 1 2 1
    a 1 1 1 1
    b 1 0 0 2
    b 0 1 0 1
    c 1 0 1 1
    c 1 0 1 0
    d 0 2 1 0
    d 1 1 1 1
    8. (4 puntos) Dadas las matrices de adyacencia 3a, 3b y 3c, dibuje el grafo correspondiente.

    1 0 1
    0 0 1 (3a)
    1 1 1

    1 2 1
    2 0 0 (3b)
    0 2 2

    0 2 3 0
    1 2 2 1 (3c)
    2 1 1 0
    1 0 0 2

    9. (4 puntos) ¿Es cualquier matriz booleana cuadrada y simétrica con ceros en la diagonal la matriz de adyacencia
    de algún grafo simple?
    Sí, debido a que en un grafo dirigido, el grado de salida de un vértice V es el número de aristas con V como vértice
    inicial, se deduce que la suma de las entradas en la fila de la matriz de adyacencia de un grafo dirigido representa el
    grado de salida del vértice V
    10. (4 puntos) Utiliza una matriz de incidencia para representar los grafos G5, G6 y G7.
    G5

    También podría gustarte