Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 121 vistas

    S1 - 5 - Concepto de Grado en Grafos No Dirigidos PDF

    Cargado por

    JoseManuelSlater
    1. Se presenta un documento sobre el concepto de grado en grafos no dirigidos. Se define el grado de un vértice como el número de aristas incidentes y se introducen las notaciones para el grado máximo y mínimo de un grafo. 2. Se incluyen ejemplos para ilustrar el cálculo del grado de los vértices. 3. Se presenta el lema de "darse la mano", el cual establece que la suma de los grados es par y el número de vértices de grado impar también es par.

    Copyright:

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

    S1 - 5 - Concepto de Grado en Grafos No Dirigidos PDF

    Cargado por

    JoseManuelSlater
    121 vistas9 páginas
    1. Se presenta un documento sobre el concepto de grado en grafos no dirigidos. Se define el grado de un vértice como el número de aristas incidentes y se introducen las notaciones para el grado máximo y mínimo de un grafo. 2. Se incluyen ejemplos para ilustrar el cálculo del grado de los vértices. 3. Se presenta el lema de "darse la mano", el cual establece que la suma de los grados es par y el número de vértices de grado impar también es par.

    Título original

    S1_5_Concepto de grado en grafos no dirigidos.pdf

    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?

    1. Se presenta un documento sobre el concepto de grado en grafos no dirigidos. Se define el grado de un vértice como el número de aristas incidentes y se introducen las notaciones para el grado máximo y mínimo de un grafo. 2. Se incluyen ejemplos para ilustrar el cálculo del grado de los vértices. 3. Se presenta el lema de "darse la mano", el cual establece que la suma de los grados es par y el número de vértices de grado impar también es par.

    Copyright:

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

    S1 - 5 - Concepto de Grado en Grafos No Dirigidos PDF

    Cargado por

    JoseManuelSlater
    1. Se presenta un documento sobre el concepto de grado en grafos no dirigidos. Se define el grado de un vértice como el número de aristas incidentes y se introducen las notaciones para el grado máximo y mínimo de un grafo. 2. Se incluyen ejemplos para ilustrar el cálculo del grado de los vértices. 3. Se presenta el lema de "darse la mano", el cual establece que la suma de los grados es par y el número de vértices de grado impar también es par.

    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 9

    1.

    5 El concepto de grado
    en grafos no dirigidos

    Aplicaciones de la
    Teora de Grafos
    a la vida real

    Alberto Conejero y Cristina Jordn


    Depto. Matemtica Aplicada
    E.T.S. Ingeniera Informtica
    Universitat Politcnica de Valncia

    Aplicaciones de la Teora de Grafos a la vida real

    Ejemplo introductorio
    Nuevas preguntas sobre las 4 situaciones presentadas
    1. Grupo de alumnos
    Cuntos amigos tenan Guille, Marta y Lidia
    respectivamente cuando se form el grupo?

    2. Alumnos de intercambio
    A cuntos pases solicitaron ir,
    respectivamente, Eloy y Marta?

    3. Red de ordenadores
    Cuntos puertos de entrada se necesitan
    para realizar las conexiones en los
    ordenadores 3,4 y 6?
    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    El concepto de grado

    Sea G=(V,E) un grafo no dirigido


    Sea v un vrtice de G
    Se llama grado de v al nmero de aristas incidentes en v.
    Si la arista es un bucle en v, contribuye con dos unidades al valor del grado.
    Si un vrtice tiene grado cero diremos que es aislado.

    Notacin.

    (G) , el grado mximo de un grafo no dirigido

    (G) , el grado mnimo de un grafo no dirigido

    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Ejemplo 1

    Grafo no dirigido
    v3
    d(v1) = 4

    v2

    d(v2) = 4
    d(v3) = 2

    v1

    d(v4) = 3
    v5

    (G) 4

    v4

    d(v5) = 3

    1
    0

    0
    1

    1
    0

    1
    1 0 1 0

    1
    0
    1
    1

    0
    1
    0
    1

    0
    1
    1
    0

    Matriz de adyacencia

    (G) 2

    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Ejemplo 2

    Grafo no dirigido
    v3
    d(v1) = 4

    v2

    d(v2) = 3
    d(v3) = 1

    v1

    d(v4) = 0
    v5

    v4
    v4 es aislado

    d(v5) = 2

    1
    0

    0
    1

    1
    0

    0
    1 0 0 0

    1
    0
    1
    0

    0
    1
    0
    0

    0
    0
    0
    0

    Matriz de adyacencia

    (G) 4

    (G) 0

    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Darse la mano?
    Cmo modelizamos el siguiente enunciado?
    En una fiesta, el nmero de personas que dan la
    mano a un nmero impar de personas es par
    Representamos la situacin con un grafo G=(V,E) donde,
    V = { personas de la fiesta }
    E = { (u,v) / u,v V, u da la mano a v }
    G es un grafo no dirigido,
    d(u) = nmero de personas a las que u da la mano
    Con esta modelizacin el enunciado se transforma de la siguiente manera:
    En una fiesta,
    En un grafo no dirigido,
    el nmero de personas
    el nmero de vrtices
    que da la mano a
    de grado
    un nmero impar de personas
    impar
    es par.
    es par.
    En un grafo no dirigido, el nmero de vrtices de grado impar es par
    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Lema de darse la mano


    (Handshaking lemma)
    Grafos no dirigidos
    Sea G=(V,E) un grafo no dirigido.
    Se verifica:
    a) La suma de los grados de los vrtices de G coincide con el
    doble del nmero de sus aristas, es decir,

    vV

    d(v) 2 |E|

    b) El nmero de vrtices de grado impar es par

    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Lema de darse la mano


    (Handshaking lemma)
    Justificacin intuitiva del apartado b)
    El nmero de vrtices de grado impar es par
    Observemos:
    Impar
    Impar + Impar = Par
    (Impar + Impar) + Impar = Par + Impar = Impar
    (Impar + Impar + Impar)+Impar = Impar + Impar = Par

    Como segn el apartado a),

    vV

    d(v) 2 |E| ,

    es decir, la suma de grados debe ser un nmero par, entonces


    la cantidad de vrtices con grado impar debe ser par
    1.5. El concepto de grado en grafos no dirigidos

    Aplicaciones de la Teora de Grafos a la vida real

    Darse la mano?
    Cmo modelizamos el siguiente enunciado?
    En una fiesta, el nmero de personas que dan la
    mano a un nmero impar de personas es par
    Representamos la situacin con un grafo G=(V,E) donde,
    V = { personas de la fiesta }
    E = { (u,v) / u,v V, u da la mano a v }
    G es un grafo no dirigido,
    d(u) = nmero de personas a las que u da la mano
    Con esta modelizacin el enunciado se transforma de la siguiente manera:
    En una fiesta,
    En un grafo no dirigido,
    el nmero de personas
    el nmero de vrtices
    que da la mano a
    de grado
    un nmero impar de personas
    impar
    es par.
    es par.
    En un grafo no dirigido, el nmero de vrtices de grado impar es par
    1.5. El concepto de grado en grafos no dirigidos

    También podría gustarte