Ensayo De Grafos

Hoy en día podemos relacionar la teoría de los grafos con actividades de nuestra vida cotidiana como lo son: la construcción de planos, las líneas telefónicas, los circuitos electrónicos, entre otros. Todas estas actividades forman parte de las matemáticas y de las ciencias de la computación; y la podemos llamar teoría de grafos; característicamente un grafo esta conformado por vértices y aristas, a la vez se encuentra representado por una serie de puntos conectados por líneas. La teoría de grafos es conocida también como teoría de las gráficas.

Los grafos desde sus inicios se han empleado para resolver problemas de diversas índoles. Dicha disciplina se puede utilizar para determinar la viabilidad de implementar un circuito en la computación; se puede estudiar las estructuras de redes de internet, manejo de estructuras de datos, entre otras aplicaciones.

En el presente trabajo se explicará de manera sencilla el concepto de grafos, así como sus elementos, clasificaciones, características, importancia y aplicaciones en actividades cotidianas para su mayor entendimiento; pues consideramos importante comprender este tema para que cuando lo utilicemos en nuestro quehacer diario conozcamos sobre el tema.

Los grafos lo podemos definir de una manera muy sencilla, como lo menciona Thomson (1989): "son un conjunto finito no vacío, de objetos llamados nodos o vértices conectados por líneas llamadas aristas (arcos) que pueden tener una orientación. Comúnmente los grafos se representan a través de una serie de puntos unidos por líneas." o sea son elementos que permiten expresar de una forma visualmente efectiva las relaciones que se generan entre elementos de muy diversa índole.

Los elementos que componen los grafos son:

1. Vértices: vienen hacer los puntos que conforman un grafo; el grado de los vértices van hacer el número de aristas de las que son extremo, estas podrían ser par o impar. Estos se pueden clasificar de la siguiente manera: vértice adyacente, aislado y terminal.

2. Aristas: son líneas que unen a los vértices consecutivos. estos se clasifican de la siguiente manera: aristas adyacentes (convergen en el mismo vértice), paralelas (si el vértice inicial y final son el mismo), cíclicas (parte de un vértice para entrar en el mismo) y cruce (cruzan en un punto).

Los grafos se pueden clasificar de la siguiente manera: A) Dirigidos (cada arco está representado por un par de vértices, y así representar dos arcos diferentes) y B) no dirigidos (el par de vértices que representa un arco no esta ordenado). Los grafos se caracterizan por ser: simples (una arista une dos vértices), conexos (cada par de vértices esta conectado por un camino), completos (las aristas unen todos los posibles pares de vértices), bipartitos (sus vértices son la unión de dos grupos de vértices) y bucles (el nodo inicial y el final coinciden).

Existen diferentes clases de grafos entre los que podemos mencionar: 1) multigrafo: tienen varias aristas entre dos vértices, 2) pseudografo: las aristas tienen el mismo extremo, 3) dígrafo: a cada arista se le indica un sentido mediante una flecha, 4) multidigrafos: son las combinaciones de las mencionadas anteriormente.

Los diferentes tipos de

...