Mapa mental

GRAFOS

Jennifer Quizhpe Inglés

Contenido del mapa

GRAFOS

PUNTOS DE ARTICULACIÓN Y PUENTES
- Vértices de corte
  - G grafo no dirigido
    - Es vértice de corte v de G si el número de componentes conexas crecen al eliminar el vértices del grafo.
      - comp (G - { v }) > comp ( G )
  - Punto de articulación
- Arista de corte
  - G grafo no dirigido
    - Es arista de corte e de G si el número de componentes conexas crecen al eliminar la arista del grafo.
      - comp (G - { e }) > comp ( G )
  - Puente
- Caracterizaciones
  - G grafo no dirigido
    - G es árbol
      - v es vértice de corte si y solo si d (v) > 1
    - e -> Arista de corte
      - Si no pertenece a ningún ciclo
CORTADURAS DE VÉRTICES Y ARISTAS
- Cortadura de vértices
  - G grafo no dirigido
    - V1 c V es cortadura si G - V1 es no conexo
      - comp ( G - V1 ) > 1
    - CONECTIVIDAD de G
      - Menor valor para el que existe una cortadura de vértices.
- Cortadura de aristas
  - G grafo no dirigido
    - Todo conjunto de aristas [ S,S' ] tal que { S,S' } constituya una bipartición de V
      - [ S,S' ] es cortadura de aristas entonces G - [ S,S' ] es no conexo
        comp ( G - [ S,S'] ) > 1
    - ARISTOCONECTIVIDAD
      - Menor valor para el que existe una cortadura de aristas
TIPOS
- Bipartidos
  - G grafo no dirigido G = (V , E)
    - Cada arista de G tiene un extremo x1 en V1 el otro x2 en V2
    - No tiene ciclo de longitud impar
  - Completo
    - Cada vértice x1 de V1 es adyacente a todos los vértices de V2
- Ponderados
  - G grafo no dirigido G = (V , E), |V| = n
    - Cada arista (vi, vj) tiene un valor asociado p(vi,vj) al que se llama PESO o COSTE
    - Matriz de Costes
      - Matriz nxn P = (pij)
- Otros
  - G grafo no dirigido G = (V , E), |V| = n
    - k - Regular
      - Todos sus vértices tienen grado k
        n -1
    - Completo
      - Representan con Kn
      - Es simple y existe una arista entre cada par de vértices distintos.
ACCESIBILIDAD
- Camino
  - Toda cadena en la que no se repite ni vértices ni aristas
- Cadena
  - Toda sucesión finita alterna de vértices y aristas.
  - Cerrada
    - Toda cadena en la que los vértices inicial y final coinciden
  - Longitud
    - Número de aristas que la forman
- Ciclo
  - Cadena en la que no se repite ninguna arista, ni vértice a excepción del inicial y final.
- Alcanzabilidad
  - G = ( V,E )
    - El vértice u alcanza al vértice v en G si existe una cadena de longitud mayor o igual a cero de u a v
    - Matriz acceso
      - Matriz nxn A = { aij )
      - Obtención
        Búsqueda en extensión o anchura (BFS)
        Búsqueda en profundidad (DFS)
- Caminos mas cortos
  - Algoritmos
    - DIJKSTRA
      - G = ( V,E )
        Grafo ponderado positivo
    - FLOYD
      - G = ( V,E )
        Grafo ponderado sin ciclos negativos
CONEXION GRAFOS NO DIRIGIDOS
- Grafos Conexos
  - G = ( V,E ) grafo no dirigido
    - Vértice u está conectado al v si u alcanza a v
  - Componente conexa
    - Subgrafo inducido por los vértices de una clase equivalente
    - Subgrafo maximal conexo
  - Equivalencia
    - Vértices se alcanzan mutuamente
- Teoremas
  - 1
    - card ( V ) = n > 1
  - 2
    - card ( V ) = n > 1
      - Posee un ciclo o un vértices de grado 1
      - La arista e pertenece a un ciclo
        G - e es conexo
ÁRBOLES
- Definición
  - Grafo no dirigido
    - Es conexo y acílico
- Caracterización
  - G = ( V,E ) con |V| > 1
    - Equivalentes
      - G es un árbol
      - G es simple y existe un único camino entre cada par de vértice
      - G es acílico y card (E) = card (V) - 1
      - G es conexo y card (E) = card (V) - 1
- Propiedades
  - G grafo no dirigido con |V| > 1
    - G es conexo
      - Si |E| >_ |V| entonces G no es acílico
    - Posee al menos dos vértices de grado 1
- Generador de mínimo coste
  - G grafo no dirigido conexo ponderado G = ( V,E )
    - Todo subgrafo generador que sea conexo y acílico
      - Coste sea menor o igual que el de cualquier otro árbol
        No tiene porque ser único
    - Algoritmo de KRUSKAL
      - Proporciona un árbol generador de mínimo coste
      - Pesos distintos dos a dos el árbol generador de mínimo coste es único
- Dirigidos con raiz
  - Es un grafo acílico tal que todos los vértices
    - V0 tienen grado de entrada uno
    - V0 tienen grado de entrada cero
  - Arborescencias
  - Propiedades
    - G = ( V,E ) grafo dirigido con raiz V0 G = ( V,E ) grafo subyacente de G
      - Existe un camino y sólo uno desde V0 a cada uno de los demás vértices
      - |E| = |V| -1
      - G~ es acílico
      - Conexo
      - árbol
EMPAREJAMIENTO
- M de G = ( V,E )
  - Es un subconjunto de E, sin bucles, tal que que no hay dos aristas de M incidentes en el mismo vértice
    - M-Saturado
      - Es extremo de una arista de M
    - M-Insaturado
      - No es extremo de una arista de M
- TIPOS
  - Grafo no dirigido ponderado
    - Máximo
      - No existe ningún otro emparejamiento cuyo número de arista sea mayor que el de M
        No es perfecto
        Algoritmo Edmonds I
    - Perfecto
      - Todos los vértices de G son M-saturados
        Es máximo
    - Óptimo
      - Emparejamiento perfecto de mayor peso
- Perfeccionar emparejamiento
  - Proceso de encontrar un emparejamiento con número de aristas mayor que M
    - Caminos M-alternados
      - M-alternados
        Todo camino en G cuyas aristas pertenezcan alternativamente a M y E-M
      - M-incrementables
        Todo camino M-alternado en G cuyos extremos con M-insaturados
        Aristas del camino que son del emparejamiento se añaden a M
        Aristas del camino que son del emparejamiento se eliminan de M
        Emparejamiento con una arista más que M
    - TEOREMA
      - Grafo no dirigido G M emparejamiento en G
        M es máximo
        No existen caminos M-incrementables
- TEOREMAS
  - G = (( X,Y )) grafo biprtido
    - Teorema de Hall
      - Emparejamiento que satura todo X
    - Teorema del Matrimonio
      - G es k-regular, k > 0
        Emparejamiento perfecto
- ALGORITMOS
  - Grafos no ponderados
    - Húngaro
    - Edmonds I
      - Emparejamientos máximo
  - Grafos bipartido ponderados
    - Kuhn-Munkres
      - Emparejamiento óptimo en un grafo bipartido completo con card(X) = card(Y)
        Mathematica
    - Edmonds II
      - Emparejamiento máximo de máximo peso
        Java
RECUBRIMIENTO
- G = ( V,E ) grafo no dirigido
  - Todo conjuntos K, de vértices de G tal que toda arista de G posee al menos unos de sus extremos en K
    - Mínimo
      - No existe ningún otro recrubirmiento con más vértices que K
- TEOREMAS
  - Teorema
    - - M es máximo y K es mínimo
  - Koning
    - G = (( X,Y )) grafo bipartido
      - M es máximo y K es mínimo
        card (M) = card(K)