Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
ciclos y caminos
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.
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.
-
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.
-
Algorittmos
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.
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.
Recorridos
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.
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.
-
Matrices
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.
-
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.
-
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.
Tipos de grafos
-
-
-
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 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.
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 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.
-
