TEORÍA DE GRAFOS
La teoría de grafos es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos, estructuras que constan de dos partes:
A. El conjunto de vértices: Nodos o puntos.
B. El conjunto de aristas: Lineas o lados.
ORIGEN:
la teoría de grafos se remonta al siglo xvii con el problema de los puentes de Konigsberg, el cual consistía en encontrar un camino que recorriera los 7 puentes del rió Pregel en la ciudad de Konigsberg, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. Este trabajo fue titulado (la solución de un problema relativo a la geometría de la posición). En 1736, fue considerado el primer resultado de la teoría de grafos resuelto por Leonard Euler.
TIPOS DE GRAFOS:
1. Grafo Simple: Es aquel que acepta una sola arista uniendo dos vértice cualesquiera. Esto es equivalente a decir que una arista cualquiera es la uncia que une dos vértices específicos. Es la definición estándar de un grafo.
2. Multigrafo: Es el que acepta mas de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos.
3. Pseudografo: Se incluye algún lazo.
4. Grafo Dirigido: Son grafos en los cuales se ha añadido una orientación a las aristas, que es representada gráficamente por una flecha.
5. Grafo No Dirigido: Son grafos en los cuales no se ha añadido orientación, no son flechas.
6. Grafo Etiquetado: Grafos en los cuales se ha añadido un peso a las aristas (numero entero generalmente) o un etiquetado a los vértices.
7. Grafo Aleatorio: Grafo donde cuyas aristas están asociadas a una probabilidad.
8. Hipergrafo: Grafos en los cuales las aristas tienen mas de dos extremos, es decir, las aristas son incidentes a 3 o mas vértices.
9. Grafo Infinito: Grafos con conjuntos de vértices y aristas de cardinal infinito.
3. Pseudografo: Se incluye algún lazo.
4. Grafo Dirigido: Son grafos en los cuales se ha añadido una orientación a las aristas, que es representada gráficamente por una flecha.
5. Grafo No Dirigido: Son grafos en los cuales no se ha añadido orientación, no son flechas.
6. Grafo Etiquetado: Grafos en los cuales se ha añadido un peso a las aristas (numero entero generalmente) o un etiquetado a los vértices.
7. Grafo Aleatorio: Grafo donde cuyas aristas están asociadas a una probabilidad.
8. Hipergrafo: Grafos en los cuales las aristas tienen mas de dos extremos, es decir, las aristas son incidentes a 3 o mas vértices.
9. Grafo Infinito: Grafos con conjuntos de vértices y aristas de cardinal infinito.
CONSTRUCCIÓN DE UNA MATRIZ A PARTIR DE UN GRAFO:
1. Se crea una matriz cero, cuyas columnas y filas representan la cantidad de nodos del grafo.
2. Por cada arista que une a dos 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.
3. Finalmente se obtiene una matriz que representa el numero de aristas (relaciones) entre cada par de nodos.
EJEMPLO 1:
A. Lo primero que hacemos es construir la matriz de tamaño igual a los nodos del grafo, en este caso la matriz seria de 5x5.
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (a) y (b) están unidos por una arista, por lo tanto agregamos un 1 a la posición (a,b) e igualmente a la posición (b,a) ya que es un grafo no dirigido.
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron.
D. Y finalmente obtenemos la matriz de nuestro grafo.
EJEMPLO 2:
A. Lo primero que hacemos es construir la matriz de tamaño igual a los nodos del grafo, en este caso la matriz seria de 5x5.
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (b) y (c) están unidos por una arista, por lo tanto agregamos un 1 a la posición (b,c), sin embargo en este caso vemos que es un grafo dirigido con flechas, que nos indica que (b) se dirige a (c) pero que (c) no se dirige a (b), por lo tanto en la posición (c,b) agregaríamos un 0.
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron, siempre teniendo en cuenta las aristas que están dirigidas de un nodo a otro.
D. Y finalmente obtenemos la matriz de nuestro grafo.
EJEMPLO 3:
A. Lo primero que hacemos es construir la matriz de tamaño igual a los nodos del grafo, en este caso la matriz seria de 5x5.
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (V5) y (V3) están unidos por una arista, por lo tanto agregamos un 1 a la posición (V5,V3) e igualmente a la posición (V3,V5) ya que es un grafo no dirigido, sin embargo vemos que en este grafo hay aristas que tienen un bucle, lo que hacemos en este caso es agregar un dos, vemos que los nodos (V1) y (V2) están unidos por un bucle, por lo tanto agregamos un 2 a la posición (V1, V2) e igualmente a la posición (V2,V1).
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) o (2) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron, siempre teniendo en cuenta las aristas que están como un bucle.
D. Y finalmente obtenemos la matriz de nuestro grafo.
A. Lo primero que hacemos es construir la matriz de tamaño igual a los nodos del grafo, en este caso la matriz seria de 5x5.
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (a) y (b) están unidos por una arista, por lo tanto agregamos un 1 a la posición (a,b) e igualmente a la posición (b,a) ya que es un grafo no dirigido.
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron.
D. Y finalmente obtenemos la matriz de nuestro grafo.
EJEMPLO 2:
A. Lo primero que hacemos es construir la matriz de tamaño igual a los nodos del grafo, en este caso la matriz seria de 5x5.
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (b) y (c) están unidos por una arista, por lo tanto agregamos un 1 a la posición (b,c), sin embargo en este caso vemos que es un grafo dirigido con flechas, que nos indica que (b) se dirige a (c) pero que (c) no se dirige a (b), por lo tanto en la posición (c,b) agregaríamos un 0.
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron, siempre teniendo en cuenta las aristas que están dirigidas de un nodo a otro.
D. Y finalmente obtenemos la matriz de nuestro grafo.
EJEMPLO 3:
B. Buscamos las aristas que unen dos nodos y en esta posición agregamos un 1, vemos que los nodos (V5) y (V3) están unidos por una arista, por lo tanto agregamos un 1 a la posición (V5,V3) e igualmente a la posición (V3,V5) ya que es un grafo no dirigido, sin embargo vemos que en este grafo hay aristas que tienen un bucle, lo que hacemos en este caso es agregar un dos, vemos que los nodos (V1) y (V2) están unidos por un bucle, por lo tanto agregamos un 2 a la posición (V1, V2) e igualmente a la posición (V2,V1).
C. Repetimos el proceso anterior con cada par de nodos que están unidos por una arista hasta tener todos los (1) o (2) en la matriz, luego de esto agregamos (0) a las posiciones que quedaron, siempre teniendo en cuenta las aristas que están como un bucle.
D. Y finalmente obtenemos la matriz de nuestro grafo.
No hay comentarios:
Publicar un comentario