Investigaciones

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 deobjetos distintos.
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 GrafoDirigido (o digrafo) G es un 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 devértices de G, y cada elemento es 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 mismo arco.
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 lasecuencia
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 tienevo=vk y el
camino contiene 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 sondistintos.
• Grafo acíclico es aquel que 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 componentesconexas de un grafo son las clases de equivalencia
bajo la relación “es alcanzable”. En otras palabras, son los conjuntos
de vértices alcanzables entre si.
• Un grafo dirigido es fuertemente...