Grafos

Grafos

1. Formado por vértices

   • Representa relaciones que existen entre pares de objetos
     • Se conforman por
       • Aristas
         • Se dividen en
           • Arista dirigida
             • Son
               • Par ordenado de vertices
           • Arista no dirigida
             • Son
               • Par no ordenado de vertices

2. Se divide en

   • Grafos dirigidos
     • Definición
       • Relaciones asimétricas. Ejemplo: Herencias, vuelos entre ciudades,
   • Grafos no dirigidos
     • Definición
       • Relaciones simétricas. Ejemplo: relaciones de colaboración, relaciones de transporte
   • Tipos
     • Grafos simples
       • Definición
         • No tiene aristas paralelas o múltiples que unan el mismo par de vértices
     • Multigrafos
       • Definición
         • Es el que cuenta con múltiples aristas entre dos vértices

3. G=(V,A), los vértices u y v pertenecientes a V; y una arista (u,v) perteneciente a A;

   • Incidencia
     • La arista (u,v) es incidente con los vértices u y con v
   • Adyacencia
     • Dos vértices u y v son adyacentes si existe una arista cuyos vértices sean u y v
       • El vértice u es adyacente a v
       • El vértice v es adyacente desde u
   • Grado vertice
     • El grado de vértices u es el número de vértices adyacentes a u
       • Se dividen en
         • Grado(v)
         • GradoE(v) GradoS(v)

4. Camino, bucle y ciclo

   • Camino
     • Secuencia que alterna vértices y aristas que comienza por un vértice y termina en vértice que cada arista es incidente a su vértice predecesor y sucesor.
   • Bucle
     • Camino de longitud 1 que comienza y termina en el mismo vértice
   • Ciclo
     • Es un camino simple<v0...vk> que cumple con ciertas restricciones

5. Grafo conexo

   • Es un grafo no dirigido (conexo) si existe un camino entre dos vértices cualquiera

6. Grafos valorados y grafos etiquetados

   • Es una terna<V, A, f> donde <V, A> es un grafo y f es una función cualquiera denominada función de coste
     • Grafo etiquetado
       • La función f tiene como imagen un conjunto de etiquetas no numéricas
     • Peso de un camino
       • En un grafo con peso, es la suma de los pesos de todas las aristas atravesadas

Imágenes y archivos del mapa