Temas


•Grafo
◊¿qué es un grafo?
◊¿De que consta?
•Lazo o Bucle
•Camino, camino cerrado, camino simple
•Ciclo
•Grafo Conexo
•Árbol
•Grafica Completa.
•Grafica Etiquetada.
•Multígrafo.
•Matriz de adyacencia.








En muchas partes de la ciencia de los computadores y de la informática aparecen los grafos, especialmente los grafos de árbol y los grafos dirigidos.

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos.




Grafo de 5 vértices y 6 aristas



Podemos concluir que:


“un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o
arcos”.



Grafos se pueden usar para modelar, estudiar y optimizar muchos tipos de redes y sistemas por ejemplo: redes de routers en internet, carreteras que conectan ciudades, redes y circuitos eléctricos, redes de alcantarillados, manejo de proyectos complejos, etc.







Un grafo consta de dos cosas:
Aristas (segmentos o aristas)
Son las líneas con las que se unen los vértices de un grafo y con la que se construyen también caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.

Vértices (nodos, vértices o puntos)
Son los puntos o nodos con los que está conformado un grafo.
Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• Vértice Aislado: Es un vértice de grado cero.
• Vértice Terminal: Es un vértice de grado 1.



Image and video hosting by TinyPic


Informalmente un grafo se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas. Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.
Representamos de una manera natural los grafos por diagramas en el plano. O sea, cada nodo (V) se representa por un punto (o pequeño círculo) y cada segmento (E) se representa por una curva que conecta sus terminales.








Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.




Si una arista une un mismo vértice se trata de un lazo o bucle.











Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor.




Camino {A, B, D, E, A, C}[rojo]


Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el último; un camino es cerrado si sus extremos coinciden.




Camino Cerrado {A, B, D, E, A}[rojo]


Un camino es simple si en la sucesión de vértices no hay ninguno repetido.




Camino Simple{B, D, E, A, C}[rojo]



La longitud de un camino es el número de enlaces que tiene el camino. Por ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.









Un ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 son los lazos (o bucles). En el ejemplo, C1 = (1, 2, 3, 4, 5, 2, 1) es un ciclo de longitud 6.






Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el nodo del comienzo solo aparece una vez más y como nodo final, y los demás solo aparecen una vez. En el grafo C2 = (1, 5, 2, 1) es un ciclo simple.







Un grafo se dice acíclico si no contiene ningún ciclo simple.









Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro.




Otra definición que dejaría esto más claro sería:


“un grafo conexo es un grafo no dirigido de modo que para cualquier par de
nodos existe al menos un camino que los une”









Es un conjunto de de uno o más nodos en donde cada nodo tiene un subconjunto de particiones T1, T2, T3,…, etc; en donde cada T es un árbol.






Un árbol es un grafo en donde se cumplen los siguientes requisitos:
1) El numero de nodos es igual al número de arcos más uno.
2) Entre cualquier par de nodos, existe una trayectoria.
3) La trayectoria es simple
4) Todos los nodos tiene grado interno uno a excepción de la raíz que tiene grado interno cero.
5) Es un grafo aciclico, es decir, que no tiene ciclo alguno.

Entre las características de los árboles, están:
Árbol dirigido, es aquel que contiene un nodo llamado raíz con grado de entrada cero, mientras todos los demás tienen grado de entrada 1.
• si un nodo tiene grado de salida cero es un nodo terminal u hoja, a todos los demás nodos se les llama ramas.
• El nivel de un nodo es la longitud de su trayectoria desde la raíz.













Un grafo completo es un grafo simple en el que cada nodo es adyacente a cualquier todo otro nodo.

El grafo completo en n nodos se denota a menudo por Kn. Tiene n(n-1)/2 enlaces.









Se dice que una grafica esta etiquetada si sus aristas tienen asignado un valor. Si cada arista a tiene un valor numérico no negativo u(a), llamado peso o longitud de a, se dice que G tiene peso. En este caso, cada camino P de G tendrá asociado un peso o longitud que será la asuma de los pesos de las aristas que forman el camino P.











Una grafica se denomina multigráfica si al menos dos de sus vértices están conectados por dos aristas. En este caso, las aristas reciben el nombre de aristas múltiples o paralelas.





El grafo anterior es multigráfico ya que hay dos aristas que unen los vértices 2 y 3


A1= (2, 3) y
A2= (3, 2)









Se puede representar un grafo como una matriz de adyacencia, como una lista de adyacencia o como un conjunto de enlaces.

Matriz de adyacencia
Se emplea una matriz cuadrada (V-1, V-1) donde V es el número de nodos:

1)Se coloca un “1” en (v, w) si existe un enlace de v hacia w; 0 en caso contrario.
2)La matriz es simétrica si el grafo no es dirigido.
3)Si no se aceptan lazos, la diagonal está formada por ceros.





Ejemplo:
Grafo:





Matriz de adyacencia:






Lista de adyacencia
Para cada nodo (de 0 a V-1) se listan los nodos adyacentes.

Ejemplo:
Grafo:




Lista de adyacencia: