Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS 1200px-Fish_graph.svg - Coggle Diagram
GRAFOS
Implementación
Usaremos grafos dirigidos, los no dirigidos se pueden representar de manera similar.
Una primera representación consiste en hacer uso de una matriz de adyacencia.
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.
Operaciones básicas
Next (v, i)
Vertex (v, i)
First (v)
Ordenación topológica
Consiste en ordenar los vértices de un grafo dirigido acíclico.
Si hay un camino desde vi a vj entonces
vj aparece después de vi
Tipos de problemas
Recorrido
Caminos mas cortos
Alcanzabilidad
variantes
Conectividad
Árboles de expansión
. Consiste en encontrar un árbol de expansión en el grafo.
Si el grafo es ponderado este problema se transforma en encontrar el árbol de expansión mínima.
Descripción de un grafo
Etiquetados y no etiquetados.
Aleatorios.
Dirigidos y no dirigidos.
Cíclicos y acíclicos.
A grandes rasgos un grafo es un conjunto de vértices y uno de aristas que conectan esos vértices.
Árbol de expansión mínima
Un árbol de expansión de un grafo no dirigido es un árbol
Formado por todos los vértices de G y algunas de (pueden ser todas)
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.
