Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 12 vistas

    Matrices Asociadas A Un Grafo

    Cargado por

    carlaoquendo
    Matrices asociadas a un grafo pueden representar la estructura del grafo. La matriz de adyacencia muestra las conexiones entre vértices mediante unos y ceros, mientras que la matriz de incidencia relaciona vértices con aristas. Ambas son útiles para analizar caminos y cadenas en el grafo.

    Copyright:

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

    Matrices Asociadas A Un Grafo

    Cargado por

    carlaoquendo
    12 vistas3 páginas
    Matrices asociadas a un grafo pueden representar la estructura del grafo. La matriz de adyacencia muestra las conexiones entre vértices mediante unos y ceros, mientras que la matriz de incidencia relaciona vértices con aristas. Ambas son útiles para analizar caminos y cadenas en el grafo.

    Descripción original:

    ALGEBRA LINEAL ESPOL

    Título original

    Matrices Asociadas a Un Grafo

    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?

    Matrices asociadas a un grafo pueden representar la estructura del grafo. La matriz de adyacencia muestra las conexiones entre vértices mediante unos y ceros, mientras que la matriz de incidencia relaciona vértices con aristas. Ambas son útiles para analizar caminos y cadenas en el grafo.

    Copyright:

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

    Matrices Asociadas A Un Grafo

    Cargado por

    carlaoquendo
    Matrices asociadas a un grafo pueden representar la estructura del grafo. La matriz de adyacencia muestra las conexiones entre vértices mediante unos y ceros, mientras que la matriz de incidencia relaciona vértices con aristas. Ambas son útiles para analizar caminos y cadenas en el grafo.

    Copyright:

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

    Matrices asociadas a un grafo.

    Definición: Dado un grafo G = (V, E) con n vértices {v 1,..., vn} su matriz de adyacencia
    es la matriz de orden n×n, A(G)=(a ij) donde aij es el número de aristas que unen los
    vértices vi y vj.

    Una forma muy útil de representar un grafo G = (V,A) es mediante su matriz de


    vecindades (o matriz de adyacencia).Si el conjunto de vértices es V = {v1,...,vn}, el
    grafo se puede describir mediante una matriz n × n:

    En la posición (vi, vj ) pondremos un 1 si {vi, vj} ∈ A, y un 0 en caso contrario. La


    matriz tendr´a ceros en la diagonal (porque no permitimos lazos) y será simétrica: si en
    la posición (vi, vj ) aparece un 1 es porque {v i, vj} ∈ A y por tanto en la posición (v j , vi)
    deberá aparecer también un 1. Así que un grafo G simple y sin lazos con n vértices es
    exactamente lo mismo que una matriz n × n simétrica de ceros y unos con ceros en la
    diagonal.

    Recorrido de grafos.

    Cadena (concepto no orientado): Es una secuencia de aristas de G, tal que cada arista de
    la secuencia tiene un extremo común con el arco precedente y otra con el siguiente.

    Largo de una cadena, es el número de aristas de la secuencia.

    Cadena elemental, es aquella que no repite vértices.

    Cadena simple, es aquella que no repite aristas.

    Camino (concepto orientado) Es una cadena µ = {u1, u2,..., uq} en la que para todo ui
    (con i < q) el extremo terminal de ui coincide con el extremo inicial de ui+1.
    Las definiciones de largo de un camino, camino elemental y camino simple son
    análogas a las de cadenas, con la salvedad de la orientación.

    Sendero, es un camino elemental (que no repite nodos).

    Vía, es un camino cuyos arcos se pueden recorrer en su sentido directo o contrario.

    Definición Dado un grafo simple G = (V, E) con n=|V| vértices {v 1, ..., vn} y m=|E|
    aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(b ij), donde
    bij=1 si vi es incidente con ej y bij=0 en caso contrario.

    La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista
    incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El
    número de unos que aparece en cada fila es igual al grado del vértice correspondiente.
    Una fila compuesta sólo por ceros corresponde a un vértice aislado. He aquí un ejemplo:

    Ilustración 1 Grafo simple con su matriz de incidencia

    Definición. Dado un grafo dirigido o dígrafo D = (V, E) con n vértices {v 1, ..., vn} su
    matriz de adyacencia es la matriz de orden n×n, A(D)=(a ij) donde aij es el número de
    arcos que tienen a vi como extremo inicial y a vj como extremo final.

    Ilustración 2 Dígrafo dirigido con su matriz de adyacencia


    La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número
    de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice
    y el número de unos que aparecen en una determinada columna es igual al grado de
    entrada del correspondiente vértice.

    Teorema 2.8.1 Si A es la matriz de incidencia de una gráfica dirigida, la componente ij


    de A2 da el número de 2-cadenas de un vértice i a un vértice j.

    Trayectoria corta entre dos vértices

    Teorema Sea A una matriz de incidencia de una gráfica dirigida. Sea a ij(n) la
    componente ij de An. iii) Si aij(n) 5 k, entonces existen exactamente k n-cadenas del
    vértice i al vértice j. iii) Más aún, si a ij(m) 5 0 para toda m < n y a ij(n) Z 0, entonces la
    cadena más corta del vértice i al vértice j es una n-cadena.

    También podría gustarte