Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Tipos de problemas
Conectividad: Consiste en saber decir si un grafo es conexo o no. Se trata de un problema básico ya que la solución a algunos otros problemas dependen de esta respuesta.
Alcanzabilidad: El problema de la alcanzabilidad está relacionado con la conexión. En él se nos dan un grafo G(V, E), un vértice origen s ∈ V y un vértice destino d ∈ V y tenemos que decir si existe un camino de s a d (s ⇝ d).
-
Caminos más cortos: Partiendo del caso anterior es posible llegar a d
desde s por varios caminos. Es posible que nos interese el camino más corto (G no-dirigido), de menor coste (G ponderado), etc…
Hay variantes
de un origen s a un solo destino d.
de un origen s a todos los posibles destinos d, uno a uno.
∀(u, v) | u, v ∈ V se nos pide encontrar el camino más corto de u
a v.
A grandes rasgos un grafo es un conjunto de vértices y uno de aristas que conectan esos vértices. Existen grafos de distinto tipo en función de las características en las que nos fijemos:
-
-
-
-
Definición
En un grafo no dirigido se llama grado de un vértice al número de aristas que inciden en el. En un grafo dirigido hablamos de grado de entrada y grado de salida.
La longitud de un camino es el número de aristas del mismo, o lo que es
lo mismo n − 1. Se pueden permitir caminos de un vértice a sí mismo.
Se llama grafo conexo o conectado a uno no-dirigido que tiene un camino desde cualquier vértice a cualquier otro. Si el grafo fuera dirigido,
entonces se le llama fuertemente conexo.
Operaciones básicas
First (v): Devuelve el índice del primer vértice adyacente a v. Si no hay ninguno, se devuelve un valor que represente un vértice nulo.
Next (v, i): Devuelve el índice posterior a i de entre los vértices adyacentes a v.
Vertex (v, i): Devuelve el vértice cuyo índice i está entre los vértices adyacentes a v.
Lista de adyacencia
Si el grafo no es denso (disperso ) se usa una lista de adyacencia.
Cada vértice mantiene una lista de todos los vértices adyacentes.
De este modo, una operación muy habitual en grafos como es encontrar todos los vértices adyacentes a uno dado consiste en recorrer la lista de adyacencia del vértice en cuestión.
Implementación
Usaremos grafos dirigidos, los no dirigidos se pueden representar de manera similar.
Matriz de adyacencia
Una primera representación consiste en hacer uso de una matriz de adyacencia.
Árboles de expansión
Consiste en encontrar un árbol de expansión en el grafo. Este se define como: dado un grafo conexo y no-dirigido G = (V, E), un árbol de expansión es un subconjunto acíclico T ⊆ E que conecta todos los vértices de G.
Ordenación topológica
Consiste en ordenar los vértices de un grafo dirigido acíclico, de manera que si hay un camino desde vi a vj entonces
vj aparece después de vi en la ordenación.
Árbol de expansión
mínima
Un árbol de expansión de un grafo no dirigido G = (V, E) es un árbol formado por todos los vértices de G y algunas de (pueden ser todas) las aristas de G, de manera que no hay ciclos.
En problemas de disciplinas como la informática, las matemáticas, diversas ingenierías, etc. A menudo necesitamos representar relaciones entre objetos.