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

¡Te damos la bienvenida a Scribd!

  • 410 vistas

    Grafos Tarea 03

    Cargado por

    AndresC
    El documento define y explica diferentes tipos de caminos y circuitos en un grafo, incluyendo caminos, senderos, trayectorias, caminos cerrados, circuitos, circuitos simples y caminos hamiltonianos. También describe las propiedades de los grafos conexos y los circuitos de Euler. Finalmente, presenta ejercicios para poner en práctica estos conceptos.

    Copyright:

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

    Grafos Tarea 03

    Cargado por

    AndresC
    410 vistas5 páginas
    El documento define y explica diferentes tipos de caminos y circuitos en un grafo, incluyendo caminos, senderos, trayectorias, caminos cerrados, circuitos, circuitos simples y caminos hamiltonianos. También describe las propiedades de los grafos conexos y los circuitos de Euler. Finalmente, presenta ejercicios para poner en práctica estos conceptos.

    Título original

    Grafos_Tarea_03.docx

    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 define y explica diferentes tipos de caminos y circuitos en un grafo, incluyendo caminos, senderos, trayectorias, caminos cerrados, circuitos, circuitos simples y caminos hamiltonianos. También describe las propiedades de los grafos conexos y los circuitos de Euler. Finalmente, presenta ejercicios para poner en práctica estos conceptos.

    Copyright:

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

    Grafos Tarea 03

    Cargado por

    AndresC
    El documento define y explica diferentes tipos de caminos y circuitos en un grafo, incluyendo caminos, senderos, trayectorias, caminos cerrados, circuitos, circuitos simples y caminos hamiltonianos. También describe las propiedades de los grafos conexos y los circuitos de Euler. Finalmente, presenta ejercicios para poner en práctica estos conceptos.

    Copyright:

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

    Autoexamen

    1. Sea G un grafo y sean v y w vértices en G


    a) Un camino de v a w es: Una sucesión finita alternando vértices y aristas adyacentes de G.
    b) Un sendero de v a w es: A camino que no contiene una arista repetida.
    c) Una trayectoria de v a w es: Un sendero que no contiene un vértice repetido.
    d) Un camino cerrado es: Cualquier camino x-y donde x=y; esto es, inicia y termina en el
    mismo nodo.
    e) Un circuito es: Un camino cerrado que contiene al menos una arista y no contiene
    ninguna arista repetida.
    f) Un circuito simple es: Un circuito que no contenga vértices repetidos excepto el del inicio y
    el del final.
    g) Un camino trivial es: Un camino que solo contiene un vértice y ninguna arista.
    h) Los vértices v y w están conectados si y solo si: Existe un camino de v a w.
    2. Un grafo es conexo si y solo si: Cualesquiera dos vértices en el grafo, hay un camino de
    uno a los otros.
    3. La eliminación de una arista de un circuito en un grafo no: Desconecta al grafo.
    4. Un circuito de Euler, en un grafo es: Un circuito que incluye cada vértice y cada arista en el
    grafo.
    5. Un grafo tiene un circuito de Euler si y solo si: El grafo es conexo y cada vértice tiene grado
    par positivo.
    6. Dados los vértices v y w en un grafo, existe una trayectoria de Euler de v a w si y solo si:
    Grafo conexo, v y w tiene grado impar y todos los demás vértices tienen grado par
    positivo.
    7. Un circuito hamiltonanio en un grafo es: Un circuito simple que incluye todos los vértices
    del grafo.
    8. Si un grafo G tiene un circuito hamiltoniano, entonces G tiene un subgrafo H con las
    siguientes propiedades: H contiene todos los vértices de G, H es conexo, H tiene el mismo
    número de aristas que vértices, cada vértice de H tiene grado 2.
    9. Un problema del agente viajero consiste en encontrar un circuito hamiltoniano que
    minimice la distancia total recorrida por un grafo en la que cada arista está marcada con
    una distancia.
    Ejercicios
    1- En el grafo siguiente, determine si los caminos siguientes son senderos, trayectorias
    caminos cerrados, circuitos, circuitos simples o caminos simples.
    a) v0e1v1e10v5e9v2e2v1Camino simple
    b) v5e7v2e9v5e10v1e3v2e9v5 Sendero
    c) v2 Camino cerrado
    d) v5v2v3v4v4v5 Circuito
    e) v2v3v4v5v2v4v3v2 Camino cerrado
    f) e5e8e10e3 Trayectoria

    v3

    V0

    e1

    V1

    e10

    e8

    e9

    e2

    e3

    e4

    e7

    e5
    e6

    v5

    v2

    v4

    2- En el siguiente grafo determine si los caminos son senderos, rutas, caminos


    cerrados, circuitos, circuitos simples o caminos simples.
    a) V1e2v2e3v3e4v4e5v2e2v1e1v0 Ruta
    b) V2v3v4v5v2 Camino simple
    c) V4v2v3v4v5v2v4 Circuito simple
    d) V2v1v5v2v3v4v2 Camino cerrado
    e) V0v5v2v3v4v2v1 Ruta
    f) V5v4v2v1 Caminos

    3- Sea G el grafo
    e1

     e2

    V2

    V1

    ¿Este camino se puede escribir sin ambigüedades como v 1v2v1? ¿Por qué?

    Porque las aristas los conectan.

    ¿Este camino se puede escribir sin ambigüedades como e 1e2? ¿Por qué?

    Porque está conectado.

    4- Considera la siguiente gráfica.


    a) ¿Cuántas trayectorias existen de v1 a v4? 3
    b) ¿Cuantos senderos existen de v1 a v4? 2
    c) ¿Cuantos caminos existen de v1 a v4? 3

    También podría gustarte