2631374
Grafos
- 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
- Par ordenado de vertices
- Son
- Arista no dirigida
- Son
- Par no ordenado de vertices
- Par no ordenado de vertices
- Son
- Arista dirigida
- Se dividen en
- Aristas
- Se conforman por
- Representa relaciones que existen
entre pares de objetos
- Se divide en
- Grafos dirigidos
- Definición
- Relaciones asimétricas. Ejemplo:
Herencias, vuelos entre ciudades,
- Relaciones asimétricas. Ejemplo:
Herencias, vuelos entre ciudades,
- Definición
- Grafos no dirigidos
- Definición
- Relaciones simétricas. Ejemplo:
relaciones de colaboración,
relaciones de transporte
- Relaciones simétricas. Ejemplo:
relaciones de colaboración,
relaciones de transporte
- Definición
- Tipos
- Grafos simples
- Definición
- No tiene aristas paralelas o múltiples
que unan el mismo par de vértices
- No tiene aristas paralelas o múltiples
que unan el mismo par de vértices
- Definición
- Multigrafos
- Definición
- Es el que cuenta con múltiples
aristas entre dos vértices
- Es el que cuenta con múltiples
aristas entre dos vértices
- Definición
- Grafos simples
- Grafos dirigidos
- 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
- 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
- El vértice u es adyacente a v
- Dos vértices u y v son adyacentes si
existe una arista cuyos vértices sean u y v
- 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)
- Grado(v)
- Se dividen en
- El grado de vértices u es el número de vértices adyacentes a u
- Incidencia
- 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.
- 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
- 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
- Es un camino simple<v0...vk> que
cumple con ciertas restricciones
- Camino
- Grafo conexo
- Es un grafo no dirigido (conexo) si existe un
camino entre dos vértices cualquiera
- Es un grafo no dirigido (conexo) si existe un
camino entre dos vértices cualquiera
- 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
- 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
- En un grafo con peso, es la suma de los
pesos de todas las aristas atravesadas
- Grafo etiquetado
- Es una terna<V, A, f> donde <V, A> es un
grafo y f es una función cualquiera
denominada función de coste
Medienanhänge
Möchten Sie kostenlos Ihre eigenen Mindmaps mit GoConqr erstellen? Mehr erfahren.