Grafos - created from Mind Map

Page 1

Formado por vértices

Se divide en

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

Camino, bucle y ciclo

Grafo conexo

Grafos valorados y grafos etiquetados

Representa relaciones que existen entre pares de objetos

Se conforman por

Aristas

Se dividen en

Arista dirigida

Arista no dirigida

Son

Par ordenado de vertices

Son

Par no ordenado de vertices

Grafos dirigidos

Grafos no dirigidos

Tipos

Definición

Relaciones asimétricas. Ejemplo: Herencias, vuelos entre ciudades,

Definición

Relaciones simétricas. Ejemplo: relaciones de colaboración, relaciones de transporte

Grafos simples

Multigrafos

Definición

No tiene aristas paralelas o múltiples que unan el mismo par de vértices

Definición

Es el que cuenta con múltiples aristas entre dos vértices

Incidencia

Adyacencia

Grado vertice

La arista (u,v) es incidente con los vértices u y con v

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

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)

Camino

Bucle

Ciclo

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.

Camino de longitud 1 que comienza y termina en el mismo vértice

Es un camino simple<v0...vk> que cumple con ciertas restricciones

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

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

Peso de un camino

La función f tiene como imagen un conjunto de etiquetas no numéricas

En un grafo con peso, es la suma de los pesos de todas las aristas atravesadas