Grafos

Grafos

Formado por vértices
1. Representa relaciones que existen entre pares de objetos
  1. Se conforman por
    1. Aristas
      1. Se dividen en
        Arista dirigida
        Son
        Par ordenado de vertices
        Arista no dirigida
        Son
        Par no ordenado de vertices
Se divide en
1. Grafos dirigidos
  1. Definición
    1. Relaciones asimétricas. Ejemplo: Herencias, vuelos entre ciudades,
2. Grafos no dirigidos
  1. Definición
    1. Relaciones simétricas. Ejemplo: relaciones de colaboración, relaciones de transporte
3. Tipos
  1. Grafos simples
    1. Definición
      1. No tiene aristas paralelas o múltiples que unan el mismo par de vértices
  2. Multigrafos
    1. Definición
      1. Es el que cuenta con múltiples aristas entre dos vértices
G=(V,A), los vértices u y v pertenecientes a V; y una arista (u,v) perteneciente a A;
1. Incidencia
  1. La arista (u,v) es incidente con los vértices u y con v
2. Adyacencia
  1. Dos vértices u y v son adyacentes si existe una arista cuyos vértices sean u y v
    1. El vértice u es adyacente a v
    2. El vértice v es adyacente desde u
3. Grado vertice
  1. El grado de vértices u es el número de vértices adyacentes a u
    1. Se dividen en
      1. Grado(v)
      2. GradoE(v) GradoS(v)
Camino, bucle y ciclo
1. Camino
  1. 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.
2. Bucle
  1. Camino de longitud 1 que comienza y termina en el mismo vértice
3. Ciclo
  1. Es un camino simple<v0...vk> que cumple con ciertas restricciones
Grafo conexo
1. Es un grafo no dirigido (conexo) si existe un camino entre dos vértices cualquiera
Grafos valorados y grafos etiquetados
1. Es una terna<V, A, f> donde <V, A> es un grafo y f es una función cualquiera denominada función de coste
  1. Grafo etiquetado
    1. La función f tiene como imagen un conjunto de etiquetas no numéricas
  2. Peso de un camino
    1. En un grafo con peso, es la suma de los pesos de todas las aristas atravesadas

Next up

Description

Resource summary

Media attachments

Similar

	Created by hor_dan almost 9 years ago

	Copied by Edgar Phye Parga almost 4 years ago