Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 35 vistas

    MATEMATICAS DISCRETAS II Seccion 1.2 Parte I

    Cargado por

    GAEL ALEXANDRE LOPEZ ORTEGA
    Este documento presenta conceptos básicos sobre teoría de grafos como clasificación de grafos, longitud de cadenas, grado de vértices, aristas paralelas y un ejemplo de problema de logística para encontrar la ruta más económica usando un grafo. También asigna como tarea calcular grados de vértices de un grafo y resolver un problema de logística similar.

    Copyright:

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

    MATEMATICAS DISCRETAS II Seccion 1.2 Parte I

    Cargado por

    GAEL ALEXANDRE LOPEZ ORTEGA
    35 vistas8 páginas
    Este documento presenta conceptos básicos sobre teoría de grafos como clasificación de grafos, longitud de cadenas, grado de vértices, aristas paralelas y un ejemplo de problema de logística para encontrar la ruta más económica usando un grafo. También asigna como tarea calcular grados de vértices de un grafo y resolver un problema de logística similar.

    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 conceptos básicos sobre teoría de grafos como clasificación de grafos, longitud de cadenas, grado de vértices, aristas paralelas y un ejemplo de problema de logística para encontrar la ruta más económica usando un grafo. También asigna como tarea calcular grados de vértices de un grafo y resolver un problema de logística similar.

    Copyright:

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

    MATEMATICAS DISCRETAS II Seccion 1.2 Parte I

    Cargado por

    GAEL ALEXANDRE LOPEZ ORTEGA
    Este documento presenta conceptos básicos sobre teoría de grafos como clasificación de grafos, longitud de cadenas, grado de vértices, aristas paralelas y un ejemplo de problema de logística para encontrar la ruta más económica usando un grafo. También asigna como tarea calcular grados de vértices de un grafo y resolver un problema de logística similar.

    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 8

    INSTITUTO TECNOLÓGICO DE TLÁHUAC II

    MATERIA GRUPO CARRERA


    MATEMÁTICAS DISCRETAS II 2A ITIC
    PROFESOR: M. EN C. E. ROBERTO CALDERÓN JUÁREZ

    ALUMNO: López Ortega Gael Alexandre

    UNIDAD 1. TEORÍA DE GRAFOS

    Sección 1.2 Clasificación ( Parte I )

    Propiedad 1 de los Grafos:


    La longitud de una cadena es igual al número de vértices que contiene ésta menos uno

    Por ejemplo; calcular la longitud de la cadena: 6 -1 = 5


    𝑣1 ; 𝑣2 ; 𝑣4 ; 𝑣3 ; 𝑣2 ; 𝑣4

    𝑣2

    𝑣3

    𝑣1

    𝑣5 𝑣4

    El grado de un vértice, notación 𝑔𝑟𝑎𝑑(𝑣), es el número de aristas que contienen a 𝑣.

    ** Observación 1. Si 𝑔𝑟𝑎𝑑(𝑣) = 0, es decir, si el vértice 𝑣 no pertenece a ninguna arista


    decimos que es un vértice aislado.

    ** Observación 2. Un bucle cuenta como si fuera dos aristas.

    𝑬𝒋𝒆𝒎𝒑𝒍𝒐 𝟏 𝑔𝑟𝑎𝑑(𝑣4 ) = 0
    𝑣2

    𝑣4

    𝑣1

    𝑣3

    𝑬𝒋𝒆𝒎𝒑𝒍𝒐 𝟐 𝑔𝑟𝑎𝑑(𝑣1 ) = 2 + 2 = 4

    𝑣2
    𝑣4

    𝑣1

    𝑣3

    𝑬𝒋𝒆𝒎𝒑𝒍𝒐 𝟑 Calcular el grado de cada vértice que conforma el siguiente grafo

    𝑣2 𝑣6

    𝑣3

    𝑣1

    𝑣5 𝑣4

    𝑺𝒐𝒍𝒖𝒄𝒊ó𝒏 Tenemos la siguiente tabla

    Grados de los vértices del grafo


    𝑔𝑟𝑎𝑑(𝑣1 ) = 4 𝑔𝑟𝑎𝑑(𝑣2 ) = 4 𝑔𝑟𝑎𝑑(𝑣3 ) = 2
    𝑔𝑟𝑎𝑑(𝑣4 ) = 3 𝑔𝑟𝑎𝑑(𝑣5 ) = 3 𝑔𝑟𝑎𝑑(𝑣6 ) = 0
    Dos aristas son paralelas si tienen los mismos vértices en sus extremos

    𝑬𝒋𝒆𝒎𝒑𝒍𝒐 𝟒 El siguiente grafo contiene tres aristas paralelas: 𝑨𝟏 , 𝑨𝟐 , 𝑨𝟑

    𝑣4
    𝑨𝟏

    𝒗𝟑
    𝒗𝟏
    𝑨𝟐

    𝒗𝟓
    𝒗𝟐

    𝑨𝟑

    𝑪𝒍𝒂𝒔𝒊𝒇𝒊𝒄𝒂𝒄𝒊ó𝒏 𝒅𝒆 𝒈𝒓𝒂𝒇𝒐𝒔

    Un grafo 𝐺 = 〈 𝕍 ; 𝔸 〉 es simple si no contiene bucles ni aristas paralelas, esto es, cada


    par de vértices { 𝑣3 ; 𝑣4 } del grafo contiene a lo más una arista.

    Por ejemplo:

    𝑣2 𝑣6

    𝑣3

    𝑣1

    𝑣5 𝑣4

    Un grafo 𝐺 = 〈 𝕍 ; 𝔸 〉 es compuesto si existen aristas que son paralelas


    Por ejemplo:

    𝑣2 𝑣6

    𝑣3

    𝑣1

    𝑣5 𝑣4

    𝑬𝒋𝒆𝒎𝒑𝒍𝒐 𝟓 𝐿𝑜𝑔í𝑠𝑡𝑖𝑐𝑎: Hay varias rutas de transporte en que se puede trasladar una
    mercancía desde el centro de producción A hasta los distintos puntos de centros de
    almacenaje antes de que llegue al consumidor B, pero cada una de ellas tiene un costo
    de envío sintetizado en el siguiente grafo:

    25
    20

    30 50 25

    10
    5
    20 10
    A 5 30
    35 10
    5

    5
    5 B
    50 15
    20
    𝑷𝒓𝒐𝒃𝒍𝒆𝒎𝒂: Encontrar la ruta de transporte que deberá seguir la mercancía para que el
    envío sea el óptimo (más económico).

    𝒔𝒐𝒍𝒖𝒄𝒊ó𝒏 𝐿𝑜𝑔í𝑠𝑡𝑖𝑐𝑎: ruta de transporte óptimo en que se puede trasladar una


    mercancía desde el centro de producción A hasta los distintos puntos de centros de
    almacenaje antes de que llegue al consumidor B.

    25
    20

    30 50 25

    10
    5
    20 10
    A 5 30
    35 10
    5

    5
    5 B
    50 15
    20

    ** TAREA # 4 **

    𝐓𝐀𝐑𝐄𝐀 𝟒 − 𝟏 Calcular el grado de cada uno de los vértices que conforma el grafo:

    𝑣2 𝑣5
    𝑣7

    𝑣4
    𝑣8
    𝑣1

    𝑣3 𝑣6
    𝑻𝒂𝒓𝒆𝒂 𝟒 − 𝟐 𝐿𝑜𝑔í𝑠𝑡𝑖𝑐𝑎: Hay varias rutas de transporte en que se puede trasladar una
    mercancía desde el centro de producción A hasta los distintos puntos de centros de
    almacenaje antes de que llegue al consumidor B, pero cada una de ellas tiene un costo
    de envío sintetizado en el siguiente grafo:

    40
    30

    75 120 70

    25
    5
    40 30
    A 5 80
    75 50
    10

    5
    25 B
    75 80
    40

    𝑷𝒓𝒐𝒃𝒍𝒆𝒎𝒂: Encontrar la ruta de transporte que deberá seguir la mercancía para que el
    envío sea el óptimo (más económico).

    FECHA DE ENTREGA: domingo 10 de octubre de 2021


    (((((((Ϯ fin Ϯ))))))))

    LA TAREA ESTA ABAJO

    |
    V

    También podría gustarte