Mind map
Grafo

Map content
Grafo
V es el conjunto no vacío de vértices o nodos E es el conjunto de lados o aristas y G es el grafo. Así que si; G= (V, E) quiere decir que es una estructura de datos compuesta por los conjuntos V y E, y forman un conjunto de pares ordenados o desordenados de vértices o nodos.
- Partes de un Grafo
- Arista: Un arista es la línea con la que une otras aristas en un grafo, esto quiere decir que; también se pueden construir caminos. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
- Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
- Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
- Vértices: Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.
- Lazo: Es un arista cuyos extremos inciden sobre el mismo vértice
- Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
- Cruce: Son dos aristas que cruzan en un punto.
- Caminos: Se llama camino a una secuencia de vértices de un grafo tal que exista una arista, 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.
- Tipos de Grafos
- Un grafo dirigido G, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista se asocia con un par ordenado de vértices. Se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha. Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.
- Un grafo no dirigido consta de un conjunto de vértices y un conjunto de aristas tal que cada arista queda asociada a un par no ordenado de vértices. Es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A.
- Grafo dirigido es el que sus aristas tienen una etiqueta. Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato, el número asociado al arco se le denomina factor de peso. Ejemplo; se puede usar en un tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.
- Un grafo mixto es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas
- Un grafo cíclico 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 cíclico de n vértices se denota 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 al menos dos aristas incidentes
- Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartito si no hay ciclos de longitud impar.
- Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.
- Un grafo ponderado es aquel que asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.
- Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo. Además es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.
- Un grafo dirigido G, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista se asocia con un par ordenado de vértices. Se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha. Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.
- Representación de los Grafos
- Los grafos se pueden representar de diferentes maneras
- Representación por incidencia. 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).
- 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 adyacencia. Listas 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)).
- 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 computacional mediante arreglos
- Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo.
- Sintaxis: TipoDato nombre[]=new TipoDato[Total de elementos];
- Sintaxis: TipoDato nombre[]=new TipoDato[Total de elementos];
- Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo.
- Representación por incidencia. 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.
- Los grafos se pueden representar de diferentes maneras
- Algoritmos de Recorrido
- Algoritmo PRIM
- el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible.
- el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible.
- Algoritmo PRIM
- Representación de os Grafos
- Representación por incidencia. 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).
- 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).
- 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 adyacencia. Listas 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)).
- 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 Computacional
- Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo. Sintaxis: TipoDato nombre[]=new TipoDato[Total de elementos];
- Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo. Sintaxis: TipoDato nombre[]=new TipoDato[Total de elementos];
- Representación por incidencia. 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).
- Algoritmos de Recorrido
- Algoritmo PRIM
- El algoritmo PRIM es el que encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
- Función
- Se marca un vértice cualquiera. Será el vértice de partida. Se selecciona la arista de menor peso incidente en el vértice seleccionado anteriormente y se selecciona el otro vértice en el que incide dicha arista. Repetir el paso 2 siempre que la arista elegida enlace un vértice seleccionado y otro que no lo esté. Es decir, siempre que la arista elegida no cree ningún ciclo. El árbol de expansión mínima será encontrado cuando hayan sido seleccionados todos los vértices del grafo.
- Como se selecciona la arista de menor peso que incide en dicho vértice, es la arista EG. Como todos los vértices ya han sido seleccionados el proceso ha terminado. Se ha obtenido el árbol de expansión mínima con un peso de 39.
- Se marca un vértice cualquiera. Será el vértice de partida. Se selecciona la arista de menor peso incidente en el vértice seleccionado anteriormente y se selecciona el otro vértice en el que incide dicha arista. Repetir el paso 2 siempre que la arista elegida enlace un vértice seleccionado y otro que no lo esté. Es decir, siempre que la arista elegida no cree ningún ciclo. El árbol de expansión mínima será encontrado cuando hayan sido seleccionados todos los vértices del grafo.
- Función
- El algoritmo PRIM es el que encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
- Algoritmo Kruskal
- El algoritmo de Kruskal, dado un grafo conexo, no dirigido y ponderado, encuentra un árbol de expansión mínima. Es decir, es capaz de encontrar un subconjunto de las aristas que formen un árbol que incluya todos los vértices del grafo inicial, donde el peso total de las aristas del árbol es el mínimo posible.
- Funcionamiento
- Se selecciona, de entre todas las aristas restantes, la de menor peso siempre que no cree ningún ciclo. Se repite el paso 1 hasta que se hayan seleccionado |V| - 1 aristas. Siendo V el número de vértices.
- Como se selecciono la arista EG de peso 9. Fueron seleccionadas un número de aristas igual al número de vértices menos uno, el proceso ha terminado. Se ha obtenido el árbol de expansión mínima con un peso de 39.
- Se selecciona, de entre todas las aristas restantes, la de menor peso siempre que no cree ningún ciclo. Se repite el paso 1 hasta que se hayan seleccionado |V| - 1 aristas. Siendo V el número de vértices.
- Funcionamiento
- El algoritmo de Kruskal, dado un grafo conexo, no dirigido y ponderado, encuentra un árbol de expansión mínima. Es decir, es capaz de encontrar un subconjunto de las aristas que formen un árbol que incluya todos los vértices del grafo inicial, donde el peso total de las aristas del árbol es el mínimo posible.
- Algoritmo Dijsktra
- Es también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.
- Su función
- Sea V un conjunto de vértices de un grafo. Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v. Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo. Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v. Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido. Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.
- Sea V un conjunto de vértices de un grafo. Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v. Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo. Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v. Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido. Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.
- Su función
- Es también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.
- Algoritmo PRIM
- Algoritmos de Búsqueda
- EL CAMINO MAS CORTO
- La idea principal es realizar una búsqueda a lo ancho "ponderada" empezando por el vértice inicial f. De manera iterativa se construye un conjunto de vértices seleccionados S que se toman del conjunto de vértices candidatos C según la menor distancia desde f. El algoritmo termina cuando no hay más vértices de G fuera del conjunto formado. +El paradigma usado corresponde al método voraz, en el que se trata de optimizar una función sobre una colección de objetos. Se usa un vector d[v] para almacenar la distancia de 'v' a 'f'.
- Por anchura
- La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimizar, en los que se deba elegir la mejor solución entre varias posibles. Es equivalente a recorrer un árbol por niveles. Dado un nodo v, se visitan primero todos los nodos adyacentes a v, luego todos los que están a distancia 2 (y no visitados), a distancia 3, y así sucesivamente hasta recorrer todos los nodo
- Profundidad
- Una Búsqueda en profundidad es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa , de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.
- EL CAMINO MAS CORTO
- Partes de un Grafo
Images and files in the map
Information
- Description
- Mapa mental de Grafo
- Created by
- María Fernanda Villegas Ángeles
- Views
- 13
- Rating


























