Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 335 vistas

    Problemas Propuestos de Teoria de Grafos

    Cargado por

    franklin
    El documento presenta 17 problemas relacionados con la teoría de grafos. Los problemas incluyen encontrar caminos simples, el número de aristas en grafos completos y regulares, determinar el número de vértices dado el número de aristas y grados de los vértices, construir grafos con grados específicos, encontrar todos los grafos no isomorfos con un número dado de vértices y aristas, y determinar si un grafo puede ser recorrido de manera euleriana o tiene un ciclo hamiltoniano.

    Copyright:

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

    Problemas Propuestos de Teoria de Grafos

    Cargado por

    franklin
    335 vistas3 páginas
    El documento presenta 17 problemas relacionados con la teoría de grafos. Los problemas incluyen encontrar caminos simples, el número de aristas en grafos completos y regulares, determinar el número de vértices dado el número de aristas y grados de los vértices, construir grafos con grados específicos, encontrar todos los grafos no isomorfos con un número dado de vértices y aristas, y determinar si un grafo puede ser recorrido de manera euleriana o tiene un ciclo hamiltoniano.

    Descripción original:

    Compilacion (apuntes) de ejercicios propuestos de teoria de Grafos, "MATEMATICA DISCRETA"

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento presenta 17 problemas relacionados con la teoría de grafos. Los problemas incluyen encontrar caminos simples, el número de aristas en grafos completos y regulares, determinar el número de vértices dado el número de aristas y grados de los vértices, construir grafos con grados específicos, encontrar todos los grafos no isomorfos con un número dado de vértices y aristas, y determinar si un grafo puede ser recorrido de manera euleriana o tiene un ciclo hamiltoniano.

    Copyright:

    © All Rights Reserved
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    335 vistas3 páginas

    Problemas Propuestos de Teoria de Grafos

    Cargado por

    franklin
    El documento presenta 17 problemas relacionados con la teoría de grafos. Los problemas incluyen encontrar caminos simples, el número de aristas en grafos completos y regulares, determinar el número de vértices dado el número de aristas y grados de los vértices, construir grafos con grados específicos, encontrar todos los grafos no isomorfos con un número dado de vértices y aristas, y determinar si un grafo puede ser recorrido de manera euleriana o tiene un ciclo hamiltoniano.

    Copyright:

    © All Rights Reserved
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    de 3

    F.I.

    TEORIA DE GRAFOS
    1. ¿Cuántos y cuáles son los caminos simples que van desde b hasta f?
    b
    e
    f
    a Rpt. - 6 caminos simples

    c d g

    2. ¿Cuántas aristas hay en un grafo completo sin lazos K12 ?


    3. ¿Cuántos caminos simples de longitud 4 hay en un grafo completo K7 ?
    (Considere que el camino a �b�c�d �e es igual al camino e�d �c�b�a )
    4. Determine V para el grafo G que tiene 9 aristas y donde todos los vértices
    tienen grado 3.
    ( 2
    )
    Rpt. - � ,* es semigrupo

    5. ¿Cuántas aristas tiene un grafo que tiene cuatro vértices de grado 3, dos
    vértices de grado 5, dos de grado 6 y uno de grado 8? ( 2
    )
    Rpt. - � ,* es semigrupo

    6. Construir un grafo de orden 4 con vértices de grados 2, 3, 3, 4. ¿cuántas


    aristas tiene?
    7. Construir un grafo de orden 6 con vértices de grados 1, 2, 2, 3, 3, 4.
    ¿cuántas aristas tiene?
    8. Sea G = (V, E) un grafo. Hallar el complemento de los siguientes grafos:

    G1 G2 G3

    9. Sea V= { a,b,c,d ,e, f } ; dibuje tres grafos no dirigidos, no isomorfos y sin lazos
    G1 = ( V ,E1 ) ,G2 = ( V ,E2 ) y G3 = ( V ,E3 ) , tales que en los tres grafos se verifique:
    grad ( a ) = 3, grad ( b ) = grad ( c ) = 2, grad ( d ) = grad ( e ) = grad ( f ) = 1.

    ALGEBRA BASICA I
    F.I.
    10. Encontrar todos los grafos de 5 vértices y 2 aristas, no isomorfos entre
    sí.
    11. Encontrar todos los grafos con cuatro vértices o menos, no isomorfos
    entre sí. (Ayuda: Hay uno de 1 vértice, dos con 2, cuatro con 3 y once con 4
    vértices).
    12. Sean G1 = ( V1 ,E1 ) y G2 = ( V2 ,E2 ) dos grafos no dirigidos de la figura.
    Definir una función f : V1 � V2 de manera que G1 y G2 sean isomorfos.

    G1 G2

    13. Probar que los siguientes pares de grafos no son isomorfos.

    G1 G2 G1 G2

    14. Determine V para los siguientes grafos o multígrafos G.


    a) G tiene 9 aristas y todos los vértices tienen grado 3.
    b) G es 6-regular con 15 aristas.
    c) G tiene 10 aristas con dos vértices de grado 4 y los demás de grado 3.

    15. Si G= ( V ,E ) es un grafo conexo con E = 17 y el grado de los vértices son


    �3. ¿Cuál es el valor máximo que puede tomar V ?

    16. ¿Cuáles de los siguientes grafos se pueden recorrer de manera


    euleriana?

    ALGEBRA BASICA I
    F.I.

    G1 G2 G3

    17. ¿Tiene el siguiente grafo un ciclo hamiltoniano?

    a b c

    h
    i g

    f e d

    ALGEBRA BASICA I

    También podría gustarte