setGraphTree

Definiciones: conjuntos, grafos, y
árboles
Agustín J. González
ELO 320: Estructura de Datos y
Algoritmos. 2002

1

Conjuntos (sets) y Grafos (graphs)
•
•

Un Conjunto es una colección de objetosdistintos.
No hay diferencia con lo ya aprendido en teoría de conjuntos en matemáticas.

•

Grafos: los hay de dos “sabores” grafos dirigidos y grafos no dirigidos.

•

Un Grafo Dirigido (o digrafo) G esun par (V,E), donde V es un conjunto
finito y E es una relación binaria sobre V. Es decir, E es una subconjunto del
producto cartesiano VxV.
V es llamado el conjunto de vértices de G, y cada elementoes llamado vértice.
E es llamado el conjunto de arcos de G, y cada elemento es llamado arco.
En un grafo dirigido es posible tener arcos apuntando al mismo nodo de salida
(u,v), con u=v.

•
•
•

••

Un Grafo No Dirigido G =(V,E) de arcos E consiste de pares no ordenados.
Es decir un arco es un conjunto {u, v}. Se acostumbra anotar (u,v) en lugar de
{u,v}; (u,v) y (v,u) son considerados el mismoarco.
No hay arcos al mismo nodo en un grafo no dirigido. u≠ v.
2

Otras definiciones en grafos
• Camino de largo k desde un vértice u a otro u’ es la secuencia
de vértices tal que u=vo,u’=vk, y (vi-1,vi) pertenece a E
para i=1,2,..k.
• Camino simple si todos los vértices son distintos en el camino.
• Ciclo en grafo dirigido: es un camino tiene vo=vk y el
caminocontiene al menos un arco.
• Ciclo en grafo no dirigido: es un camino de largo tres o más que
conecta un vértice con el mismo.
• Un ciclo es simple si v1, v2, .., vk son distintos.
• Grafo acíclico es aquelque no tiene ciclos

3

Definiciones en grafos (Cont)
• Un Grafo no dirigido es conexo si cada par de vértices están
conectados por un camino.
• Las componentes conexas de un grafo son las clases deequivalencia
bajo la relación “es alcanzable”. En otras palabras, son los conjuntos
de vértices alcanzables entre si.
• Un grafo dirigido es fuertemente conexo si cada par de nodos es
alcanzable...

Leer documento completo

Regístrate para leer el documento completo.