Grafos(ejemplos)

Índice

Teoría de grafos

1. Algoritmo de Dijkstra.
1.1- Creador
1.2-Definición
1.2.1-Notacion
1.3-Empresa
1.4-Problema
1.5-Solución
1.6- Conclusiones

2. Algoritmo de Árbol de Expansión Mínima.
2.1-Creador
2.2-Definición
2.3-Empresa
2.4-Problema
2.5-Solución
2.6- Conclusiones

3. Algoritmo de Flujo Máximo.
3.1- Creador
3.2-Definición3.3-Empresa
3.3-Problema
3.4-Solución

4. Conclusiones

TEORÌA DE GRAFOS

CONCEPTO:

La teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas).
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, ungrafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Estructuras de Datos en la representación de grafos:

Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas

ESTRUCTURA DE LISTA

Lista de incidencia - Las aristas son representadas con un vector de pares(ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.

Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

ESTRUCTURAS MATRICIALES

Matriz deincidencia - 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 (1 - conectado, 0 - no conectado)
Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de locontrario, es 0.
Grafos simples - Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigrafo o Gráfo múltiple.
Grafos conexos - Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquierpar de vértices (a, b), existe al menos un camino posible desde a hacia b.
Grafos completos - Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.
Grafos bipartitos - Un grafo G es bipartito si puede expresarse como (es decir, sus vértices son la unión de dos grupos de vértices), bajo lassiguientes condiciones:
- V1 y V2 son disjuntos y no vacíos.
- Cada arista de A une un vértice de V1 con uno de V2.
- No existen aristas uniendo dos elementos de V1; análogamente para V2.
Grafos Orientados - En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristasserá ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados.

Árboles - Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas. Su importancia radica en que los árboles son grafos queconectan todos los vértices utilizando el menor número posible de aristas.

2.- ALGORITMO DE DIJKSTRA

2.1 CREADOR:

Edsger Wybe Dijkstra
Nació el 11 de mayo, 1930 fue un científico de la computación de origen holandés.
Dijkstra estudió física teórica en la Universidad de Leiden. Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de...