Programacion imperativa modular Graphos.

Un Grafo dirigido es una pareja (V , E ) donde V es un conjunto finito de nodos (v´ertices) y E  es una relacio´n binaria sobre V. Las parejas en E se denominan arcos (edges ).[pic 7]

V ={1, 2, 3, 4, 5, 6}

E ={(1, 2), (2, 2), (2, 4), (2, 5)

(4, 1), (4, 5), (5, 4), (6, 3) }

En un Grafo no dirigido (V , E ), las parejas en E  no est´an ordenadas y pueden verse como conjuntos de 2 nodos aunque se acostumbra usar la notacio´n de parejas con los dos elementos diferentes.

Los nodos u y v son adyacentes si (u, v ) ∈ E[pic 8]

El grado de un nodo es el nu´mero de arcos que llegan a (o salen de) ´el.

Si el grado es 0, el nodo est´a aislado.

Un camino de longitud k entre los nodos p y q en (V , E ) es una sucesio´n de nodos v0 , v1 , . . . , vk  tal que[pic 9]

p = v0 , q = vk  y (vi−1 , vi ) ∈ E para 1 ≤ i ≤ k.

Siempre hay un camino de longitud 0 entre el nodo v

y s´ı mismo.

Un camino es simple si todos sus nodos son diferentes.

El nodo q es alcanzable desde el nodo p si existe un camino que comienza en p y termina en q.

Un camino v0 , v1 , . . . , vk forma un ciclo si v0 = vk . Un grafo es ac´ıclico si no tiene ciclos.

Un grafo no dirigido es conexo si cada nodo es alcanzable a partir de todos los dem´as.[pic 10]

Un subconjunto de nodos de un grafo es una componente conexa si los nodos son alcanzables entre s´ı.

Un grafo no dirigido es completo si cualquier par de nodos son adyacentes.

[pic 11]

Un bosque es un grafo ac´ıclico no dirigido

Un ´arbol (libre) es un grafo ac´ıclico, no dirigido y conexo

Sea G = (V , E ) un grafo no dirigido. Las siguientes proposiciones son equivalentes:

G  es un ´arbol libre.[pic 12]

Cualquier par de nodos de G  est´an conectados por un u´nico camino simple.[pic 13][pic 14]

G es conexo, pero si se retira cualquier arco de E , el grafo resultante no es conexo.[pic 15]

G es conexo y |E | = |V | − 1[pic 16]

...