Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Tipos de grafos
-
-
-
Grafo bipartito
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.
-
Grafo completo
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.
-
Grafo conexo
Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.
-
Grafo denso
Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.
-
Grafo dirigido
Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.
-
Camino de euler
Camino euleriano es un camino que contiene todas las aristas, apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de ellos tienen grado impar.
-
-
Algorittmos
Algoritmo kruskal
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
-
Algoritmo de prim
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
-
Algoritmo dijkstra
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.
-
Camino de longitud
Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor.
-
Algoritmos de recorridos
Recorrido de anchura
El recorrido en anchura, generalización del recorrido por niveles de un árbol. Explora sistemáticamente las aristas del grafo de forma que primero se visitan los vértices más “cercanos” al que estamos explorando.
-
Recorrido de profundidad
El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente.
-
un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
-
Matriz de adyacencia
Matriz cuadrada de orden NxN asociada a un grafo de orden N, donde sus filas y columnas se identifican con los vértices del grafo y en las celdas se indican la cantidad de aristas (o arcos salientes si es un dígrafo) a los nodos asignado a la fila y columnas en cuestión.
Definición.
Sea el grafo G=<V,A> de orden N al mismo se asocia una matriz cuadrada M de NxN tal que:
-A cada fila se asocia un nodo de V.
-A cada columna se asocia un nodo de V.
-La celda Mi,j contiene la cantidad de aristas de A de la forma {i,j} ó (i, j).
-
Matriz de incidencia
La matriz de incidencia es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias. MATRIZ DE ADYACENCIA Construcción de la matriz a partir de un grafo: 1. Las columnas de la matriz representan las aristas del grafo.
-
Ciclo Hamiltoriano
Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.
-
