Grafos

Instituto Tecnológico
de Villahermosa
Instituto Tecnológico
de Villahermosa

Materia:
Estructura de Datos

Profesor:
Fidelio Castillo Romero

Carrera:
Ing. En Sistemas Computacionales



Grafos
Conceptos y Aplicaciones

Grafo:
Un Grafo no es más que un conjunto de nodos o vértices que se encuentranrelacionados con unas aristas. Además los vértices tienen un valor y en ocasiones las aristas también y se le conoce como el costo.
Arco: Liga que une dos nodos del grafo.
Nodos adyacentes: Dos nodos son adyacentes si hay un arco que los conecte.
Camino: Secuencia de nodos, en la que cada par de nodos son adyacentes.
Camino simple: Es un camino en el que todos los nodos contenidos sondiferentes, con la posible excepción del primero y el último, que podrían ser el mismo.
Grafo no dirigido: Los arcos en el grafo no tienen una dirección particular, es decir son bidireccionales.
Grafo dirigido (digrafo): Los arcos en el grafo tienen una dirección asociada. El primer elemento del arco es el origen y el segundo es el destino.
Grafo ponderado: Cada arco del grafo tiene asociado un peso ovalor.
Ciclo: En un grafo dirigido, el ciclo es un camino donde el nodo de inicio y el nodo de terminación son el mismo.
Grafo conectado: Un grafo no dirigido es conectado si hay un camino de cualquier nodo hacia cualquier otro.

Representación Grafica de un Grafo



Grafo Dirigido

Grafo no dirigido: Los arcos en el grafo no tienen una dirección particular, es decir sonbidireccionales.

Grafo No Dirigido
Grafo dirigido (digrafo): Los arcos en el grafo tienen una dirección asociada. El primer elemento del arco es el origen y el segundo es el destino.

Adyacencia
El vértice n es adyacente al m, si existe un arco o arista de m a n
* Adyacencia:
B es adyacente a A
D es adyacente a A
C es adyacente a A
A es adyacente a A
C es adyacente a D
E es adyacente a CIncidencia
El vértice n es incidente al arco o arista x, si n es uno de los vértices relacionados con el arco o arista x . Del mismo modo , se dice que el arco o arista x es incidente al vértice n.
Incidencia:
B es incidente al arco (A,B)
(A,B) es incidente a B

Grado de un Vértice

Sobre el Vértice D:
Grado de Entrada: 3
Grado de Salida: 2
Grado del Nodo: 5

Grafo A cíclico y CíclicoSi un grafo contiene al menos un ciclo se llama cíclico.
Un grafo a cíclico es aquel que no tiene ningún circuito o ciclo.

Caminos
Caminos entre Vértices
Existe un camino de longitud k desde el vértice A al B , si existe una secuencia de k+1 vértices n1,n2,...,nk+1 , donde n1=A, nk+1=B y (ni,ni+1) son adyacentes para todo i entre 1 y k.
En un grafo no orientado, al camino se le llamacadena.

Caminos entre los vértices A y C:
Camino de longitud 1: (A,C)
Camino de longitud 2: (A,D,C)
Camino de longitud 2: (A,A,C)
Camino de longitud 3: (A,A,D,C)

Camino entre Nodos

¿Existe un camino de longitud mayor que 1 entre los vértices C y B?

Camino de longitud 3: (C, B, A, B)
Camino de longitud 4: (C, B, A, C, B)

Camino Simple
Entre dos vértices existe un caminosimple si todos los vértices, excepto posiblemente el primero y el último, son distintos dos a dos.
O sea, un camino simple es aquel en el que no se repiten los arcos.

Ejemplo:
(A, B, D)
(A, B, A, C)

Un ciclo, o también circuito, es un camino simple de cualquier longitud de un vértice así mismo. Si el ciclo es de longitud 1, entonces se denomina bucle o lazo.
Ejemplo:
Ciclo: A,D,C,ABucle: A,A

Operaciones Básicas de los Grafos
En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.
Insertar vértice
La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una...