Grafos
Un grafo es un tipo abstracto de datos que consiste en un grupo de nodos y uno de arcos, los cuales establecen una relación entre nodos.
Un ejemplo seria el de una ruta de trenes; las estaciones o paradas serian los nodos y los recorridos entre las estaciones son los arcos.
Pueden ser dirigidos y no dirigidos. Los dirigidos son aquellos cuyos pares (m,n) se ordenan por una flecha que va desde el nodo m al nodo n.
Los no dirigidos son los que se unen por medio de lineas que no tienen dirección.
Tipos de grafos:
- Grafo regular: Es aquel que tiene el mismo grado en sus vértices.
- Grafo Bipartito: Cuando los vértices pueden formar dos conjuntos de manera que no existan adyacencias entre los vértices que pertenecen a un mismo conjunto.
- Grafo Completo: Es el que tiene aristas en cada par de los vértices. Uno completo con n vértices es notado como Kn.
- Grafo nulo: Se genera un grafo nulo cuando los vértices no están conectados o son vértices aislados.
- Grafo Isomorfos: Son aquellos que tienen una correspondencia biunívoca, entre los vértices; es decir uno a uno de tal forma que se unen por una arista en común.
- Grafos Platónicos: Son los que están formados por vértices y aristas de cinco sólidos rectangulares, como lo son el cubo, el tetraedro, icosaedro, octaedro y el dodecaedro.
- Grafos Eulerianos: (Camino Euleriano es aquel que contiene todos los arcos del grafo). Son aquellos que contienen caminos euleriano.
- Grafos Conexos: Es el que no esta dirigido de modo que para cualquier par de nodos existe por lo menos un camino que los une
Representación por matrices:
Se pueden representar por medio de matrices en donde la N es el numero de vertices en el grafo, la matriz seria:
Implementación:
Se crea una clase grafo en la cual van cuatro miembros:
- Nodos: los cuales indicaran la cantidad de nodos.
- Vació: Se le da un valor verdadero si el nodo esta vació.
- Información: La información la que cada nodo puede acceder.
- Adyacente: Representa a lo que es la matriz en donde la celda va desde un nodo i a uno j si el valor es cero es que no existe arco.
El constructor creara un grafo con un numero de nodos que se predispone e inicia liza la matriz a cero.
Ejemplo de Árbol
