Lista de incidencia
El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.
Matriz de incidencia
El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).
Representación por adyacenciaListas de adyacencia
El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.
Matriz de adyacencia
Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V2)).
Representación Gráfica
Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos
correspondientes mediante una línea, ejemplo:
Ejemplos
El ciclo euleriano
La ciudad de Königsberg esta atravesada por un rio que tiene 2 islas y 7 puentes como muestra la figura 1. Se pregunta si es posible partir del sector A y, haciendo una caminata, pasar por cada puente una sola vez volviendo al punto de partida. En el grafo de la figura 2 el problema se traduce en partir de A y recorrer las 7 ramas sin repertir ninguna y volver a A (ciclo euleriano). Este problema fue encarado por Euler en 1736 y es el origen de la teoria de grafos.
Coloreado de mapas
La figura 4 muestra un mapa con 4 districtos A, B, C y D. Se trata de pintar cada districto con un color de forma que dos regiones con un borde comun (que no sea un punto) tengan distintos colores y queremos hacer esto usando un minimo numero de colores. La figura 5 muestra un grafo homeomorfo al mapa, en el sentido que los vertices del grafo se corresponden con las regiones del mapa y dos vertices estan conectados por una rama cuando las regiones correspondientes tienen un borde comun. El problema se traduce en el grafo a minimizar el numero de colores al asignar un color a cada vertice de forma que cualquier rama tenga extremos de distinto color.
No hay comentarios.:
Publicar un comentario