Ensayo “Grafos y sus aplicaciones”

[pic 1]

Nombre:

Luis Bryan Cordero Solis

Carrera:

Ingeniería de Sistemas

Grupo:

5202

Profesor(a):

Shirley Guisella Coque Villegas

Tema:

“Grafos y sus aplicaciones”[pic 2]

Definición de Grafos y aplicaciones

Los grafos fueron definidos en el siglo XVIII por el matemático L. Euler para decidir si era posible atravesar todos los puentes de la ciudad de Königsberg, Prusia (actualmente Kaliningrado, Rusia, ciudad bañada por un río que rodea una isla).

Los grafos son estructuras de datos que sirven para representar relaciones entre determinados objetos, no necesariamente son jerárquicas. Son aplicables generalmente en áreas de la Química, Geografía, Ingeniería eléctrica e industrial y modelado de redes de diferente tipo, tales como: de alcantarillado, eléctricas, etc.

El grafo es considerado como un conjunto de pares ordenados tales que los elementos de cada par cumplen el enunciado de la relación; los elementos del dominio de la relación se llaman vértices o nodos y el par que representa dos vértices relacionados se llama arista o arco.

Hay varios tipos de listas o de árboles, se dispone de diferentes modelos  de grafos. Concretamente, se definen cuatro TAD que surgen a partir de las cuatro combinaciones posibles según los dos criterios siguientes:

• Un grafo es dirigido algunas veces denominado también dígrafo, es un grafo en el que las aristas son parejas ordenadas de vértices. También si la relación no es simétrica se denomina dirigido; si lo es; se denomina no dirigido.

• Un grafo es etiquetado si la relación es valorada; si no lo es, se denomina no etiquetado. Los valores de la relación son sus etiquetas.

Existen distintos de grafos como son: [pic 3][pic 4][pic 5][pic 6]

[pic 7][pic 8]

Para la representación de los grafos existen ciertas notaciones. Se representan con G= (V, A); en donde la letra V representa el conjunto de vértices o nodos y la letra A representa las aristas. Ejemplo:

G1= {V1, A1}

V1= {1, 2, 3, 4, 5}

G1= {<1, 2>, <1, 5>, <1, 4>, <2, 3>, <3, 5>, <4, 3>, <4, 5>}

Conceptos claves:

• La longitud de un trayecto es el número  de aristas del trayecto (o el número de vértices).
• Un ciclo es un trayecto en el que el primer y último vértice coinciden y ninguna de las aristas se repite.
• Un grafo que no tenga ningún ciclo se denomina acíclico.
• Un grafo es simple si no tiene lazos, ni lados paralelos.
• Un grafo es regular, ya que desde cualquier vértice que se tome, siempre será la misma cantidad de vértices.
• Un grafo es completo porque cada nodo tiene relación con todos los nodos del grafo.
• Hay una clase particular de grafos, llamados grafos bipartitos, que pueden definirse sobre dos dominios distintos.

La aplicación de la teoría de grafos es aplicada en el diario vivir. Algunos ejemplos de estas aplicaciones son:

1. Los recorridos de un repartidor de pizza desde el punto de partida hasta el de llegada, el cual es la residencia del cliente.

1. Una topología totalmente conexa de computadoras, ya que se la considera como una cadena de redes de un grupo de nodos interconectados.

1. Los recorridos que hace un avión de un lugar hacia otro, en donde los nodos llegan a corresponder a ciudades donde el avión hace escalas, es decir, de donde sale y donde llega. Las líneas o aristas serían los lugares que recorre para llegar a dichos puntos.

Ejemplos con gráficos

En cada caso se dice cuál es el conjunto V  de vértices y el enunciado R de la relación.

...