Combinatorics">
Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 2K vistas

    Ejercicio 1, 2, 3 y 4 - Unidad 3 - Hugo Avilez

    Cargado por

    Andres Brisson
    El documento describe varios conceptos relacionados con grafos y árboles. Define formalmente un grafo, calcula los grados de sus vértices y verifica una propiedad. Explica la diferencia entre dígrafo, grafo y multígrafo, y determina si una representación corresponde a un grafo o multígrafo. También describe formalmente un grafo dado por una matriz de adyacencia y analiza un árbol, identificando sus nodos hoja, rama, raíz y las relaciones entre sus vértices.

    Copyright:

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

    Ejercicio 1, 2, 3 y 4 - Unidad 3 - Hugo Avilez

    Cargado por

    Andres Brisson
    2K vistas7 páginas
    El documento describe varios conceptos relacionados con grafos y árboles. Define formalmente un grafo, calcula los grados de sus vértices y verifica una propiedad. Explica la diferencia entre dígrafo, grafo y multígrafo, y determina si una representación corresponde a un grafo o multígrafo. También describe formalmente un grafo dado por una matriz de adyacencia y analiza un árbol, identificando sus nodos hoja, rama, raíz y las relaciones entre sus vértices.

    Descripción original:

    Título original

    Ejercicio 1, 2, 3 y 4 - Unidad 3 _ Hugo Avilez (1)

    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 describe varios conceptos relacionados con grafos y árboles. Define formalmente un grafo, calcula los grados de sus vértices y verifica una propiedad. Explica la diferencia entre dígrafo, grafo y multígrafo, y determina si una representación corresponde a un grafo o multígrafo. También describe formalmente un grafo dado por una matriz de adyacencia y analiza un árbol, identificando sus nodos hoja, rama, raíz y las relaciones entre sus vértices.

    Copyright:

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

    Ejercicio 1, 2, 3 y 4 - Unidad 3 - Hugo Avilez

    Cargado por

    Andres Brisson
    El documento describe varios conceptos relacionados con grafos y árboles. Define formalmente un grafo, calcula los grados de sus vértices y verifica una propiedad. Explica la diferencia entre dígrafo, grafo y multígrafo, y determina si una representación corresponde a un grafo o multígrafo. También describe formalmente un grafo dado por una matriz de adyacencia y analiza un árbol, identificando sus nodos hoja, rama, raíz y las relaciones entre sus vértices.

    Copyright:

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

    ESTUDIANTE B

    1. Con el siguiente grafo:

    a. Describa formalmente el grafo.

    El grafo G_2 = (V, E,)


    Conjunto de vértices: V(G_2) = {G, H, F, I}
    Conjunto de aristas: E(G_2) = {(G, H), (G, F), (I, H), (I, F), (H, F)}

    b. Halle el grado y paridad de cada vértice.

    deg ( G ) =2
    deg ( H ) =3
    deg ( F )=3
    deg ( I )=2
    Grado total de G2=2+3+3+ 2=10

    c. Verifique si cumple que la suma de los grados de los vértices de un grafo


    es igual a dos veces el número de aristas.

    ∑ deg ( u )=2∗Card (E (G ))
    u ∈V (G )

    ∑ deg ( G2 )=2∗E(G2)
    u ∈G2

    ∑ deg ( G2 )=2∗5=10
    u ∈G2

    En el desarrollo del ejercicio nos podemos dar cuenta que la sumatoria


    total de los grados es 10 y el número de aristas es 5 cumpliendo con el
    Teorema.

    2.
    a. Responda lo siguiente: ¿Cuál es la diferencia entre dígrafo, grafo y
    multígrafo?

    Dígrafo: Es lo mismo que un multígrafo, solo que cada arista e de G


    tiene una dirección asignada o, en otras palabras, cada arista (e) está
    identificada por un par ordenado (u, v) de
    nodos (G) en vez del par desordenado [u. v].

    Grafo: Es un conjunto de puntos denominados vértices o nodos, unidos


    por líneas, llamadas aristas.

    Multígrafo: Se diferencia del grafo en que el conjunto de aristas (A)


    puede tener múltiples aristas y/o puede existir aristas cuyo extremo sea el
    mismo vértice, esto se denomina bucles.

    b. Determine gráficamente si el multígrafo G2= {V, E}, es grafo o


    multígrafo, donde
    V = {a, b, c, d} y E = {(a, b), (a, c), (a, d), (b, c), (c, d), (d, c)}

    a b

    G2

    c d

    Nos podemos dar cuenta que es un multígrafo.

    3. Realice el grafo a partir de la información dada en la matriz de adyacencia y


    descríbalo formalmente:

    a b
    e

    c d

    El grafo G_3 = (V, E,)

    Conjunto de vértices o nodos: V(G_3) = {a, b, c, d, e}

    Conjunto de aristas o arcos: E(G_3) = {(a, a), (a, c), (a, e), (b, c), (b, e), (c, a), (c,
    c), (c, d), (c, e), (d, b), (d, d), (e, b), (e, d)}

    4. Para el siguiente árbol:

    Determine:

    a. Nodos hoja, nodos rama.

    Nodos hoja: Son todos aquellos nodos que no tienen hijos, los cuales
    siempre se encuentran en los extremos de la estructura.
    En el anterior ejemplo son: A, F, G, J, L

    Nodos rama: Estos son todos aquellos nodos que no son la raíz y que
    además tiene al menos un hijo.
    En el anterior ejemplo son: C, E, H, B, I, K
    b. La raíz del árbol.

    Se refiere al primer nodo de un Árbol, solo un nodo del Árbol puede ser
    la Raíz.
    En el anterior ejemplo es: D

    c. Las relaciones entre vértices de un árbol enraizado.

     D es la raíz

     C es hijo de D
    E es hijo de D
    H es hijo de D
    B es hijo de C
    A es hijo de B
    F es hijo de E
    G es hijo de E
    I es hijo de H
    J es hijo de I
    K es hijo de H
    L es hijo de K

     D es padre de C
    D es padre de E
    D es padre de H
    C es padre de B
    B es padre de A
    E es padre de F
    E es padre de G
    H es padre de I
    I es padre de J
    H es padre de K
    K es padre de L

     C, E y H son hermanos.
    F y G son hermanos.
    I y K son hermanos.

     A, F, G, J, L son nodos terminales en hojas.

     C, E, H, B, I, K son nodos interiores.

     El grado del nodo D es 3


    El grado del nodo C es 1
    El grado del nodo B es 1
    El grado del nodo A es 0
    El grado del nodo E es 2
    El grado del nodo F es 0
    El grado del nodo G es 0
    El grado del nodo H es 2
    El grado del nodo I es 1
    El grado del nodo J es 0
    El grado del nodo K es 1
    El grado del nodo L es 0

     El nivel del nodo A es 1


    El nivel del nodo C, E y H es 2
    El nivel del nodo B, F, G, I y K es 3
    El nivel del nodo A, J y L es 4

    d. Subárboles.

    Conocemos como Sub-Árbol a todo Árbol generado a partir de una


    sección determinada del Árbol, Por lo que podemos decir que un Árbol
    es un nodo Raíz con N Sub-Árboles.

    E H H

    F G I K I K

    J L

    e. La altura del árbol.

    Le llamamos altura al número máximo de niveles de un Árbol.


    La altura es = 4

    5. Explique el concepto de árbol enraizado y las relaciones entre vértices de un


    árbol enraizado del árbol del ejercicio anterior.
    Enlace del Video:

    También podría gustarte