arboles y grafos









INVESTIGACION:

UNIDAD 4: Arboles y grafos.











Equipo:
Luis Manuel Domínguez González 262013
Dilan Ricardo Solano Martínez 257189
Sylvia cristina Lara Clift 262032
ARBOLES Y GRAFOS

GRAFO
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlacesllamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas conotras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).


BUCLE
En teoría de grafos, un bucle o loop es una arista que conecta un vértice consigo mismo. Un grafo simple no posee bucles.
Dependiendo delcontexto, un grafo o multigrafo puede estar definido o no para permitir en él la presencia de bucles


CICLO
En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices sedenota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.

TRAYECTORIAS
Una trayectoria en un grafo es una secuencia de una o más aristas que conecta a dos nodos.

LONGITUD
En Teoría de Grafos, se llama Camino a una secuencia de vértices dentro de un grafo tal que existauna arista entre cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. Dos vértices pueden estar conectados por varios caminos. El número de aristas dentro de un camino es su longitud. Así, los vértices adyacentes están conectados por un camino de longitud 1, y los segundos vecinos por un camino de longitud 2.
Siun camino empieza y termina en el mismo vértice se le llama ciclo.


GRAFO DIRIGIDO
Un grafo dirigido o digrafo es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida1 , a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.

GRADO INTERNO Y EXTERNO DE UN GRAFO

Grado Interno: Es la cantidad de arcos salientes a n. (Esdecir los arcos que apuntan al nodo).

Grado Externo: Es la cantidad de arcos salientes de n. (Es decir los arcos que apuntan hacia otro nodo.


MATRIZ DE ADYACENCIAS
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
1. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
2. Por cada arista que une ados nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.
Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.
Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).
Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas ocolumnas), y viceversa.

Grafo no dirigido
Matriz de adyacencia






MULTILISTAS
La implementación de un grafo usando multilistas sólo tiene sentido para grafos dirigidos. Su objetivo es mejorar el coste de la operación que pasa a tener coste q(n) en lugar del coste q(n+e) que tiene con listas de adyacencia. También se reduce a q(n) el coste.

RECORRIDO EN PROFUNDIDAD...