Teoría de grafos




Grafos







La teoría de grafos, también llamada teoría de gráficas, es una rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos. Los grafos no deben ser confundidos con las gráficas, que es un término muy amplio.













En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.​ Son objeto .


demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto regresando al punto de partida por caminos distintos en todo momento). En teoría de los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.


Entre otras muchas de sus obras Introdujo los símbolos e (como la inicial de su nombre), la letra pi para dicho número (el honor a la letra inicial de Pitágoras), f(x) para las funciones, el sumatoria (∑) y el cálculo de i como la raíz cuadrada de Argumentó que el infinito separaba los números positivos de los negativos de forma similar a como lo hace el cero. Definió las funciones logarítmicas y exponenciales. Elaboró e introdujo la integración doble. Descubrió el teorema de la composición de integrales elípticas. Amplió y perfeccionó la geometría plana y de sólidos. Fue el primero en considerar el seno y el coseno como funciones. Introdujo los factores integrantes en las ecuaciones diferenciales. Generalizó la congruencia de Fermat, introduciendo una expresión que Gauss denominó “indicador”.

Considerado como el padre de la Teoría de Gráficas y como uno de los más grandes matemáticos de todos los tiempos.

Euler vivió casi durante los diecisiete últimos años de su vida en una ceguera total. Ni siquiera esta tragedia consiguió interrumpir sus investigaciones y publicaciones, que continuó al mismo e incluso a mayor ritmo hasta 1783.

En San Petersburgo el 18 de septiembre de 1783, en que, a la edad de setenta y seis años, murió de manera repentina mientras tomaba el té y jugaba con uno de sus nietos.

La teoría de gráficas o teoría de grafos es aplicada entre otras, en áreas tales como ciencias sociales, ciencias físicas, ingeniería de comunicación; pero, básicamente juega un papel importante en las ciencias de la computación, tales como inteligencia artificial, lenguajes formales, teoría de cambio y lógica de diseño, gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación de información, en lo que respecta al modelado de problemas, indicando sus características de manera muy objetiva.

El concepto de grafo o gráfica es muy diferente a los trazos realizados en matemática sobre los ejes x e y.

Entre otras aplicaciones se utiliza para:

. Cartografía (coloreado de mapas)


. Modelado matemático


. Determinación de tiempos en el desarrollo de proyectos


. Urbanistas


. Programación de exámenes en una institución educativa


.Programación de horarios en una entidad cualquiera


. Programación de distribución de servicios públicos (recolección de basuras en una ciudad, red de acueducto, de alcantarillado y de gas)






























. Diseño de boards o tarjetas plásticas para dispositivos electrónicos.  Redes de computadores

Los elementos de un grafo son los nodos o vértices y las aristas. Cada arista se forma por la unión de dos vértices. En decir, hay una relación entre las aristas y los nodos. Por ejemplo, si se usan grafos para la ejecución de un plan de actividades, los vértices se pueden asociar con las actividades y las aristas corresponderían al tiempo que tarda o a la probabilidad que se tiene para que se realice una actividad. En tal caso se trabaja en grafos dirigidos con peso.

Este capitulo pretende completar, de un modo organizado, los conceptos y términos sobre grafos que aparecen en este tema, los cuales inciden, fundamentalmente en el tratamiento algorítmico de los problemas planteados.
1 Conceptos básicos de la teoría de grafos
Concepto de grafo


Sea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas (pares de vértices); se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, pondrán entre llaves.
Clasificación de los grafos
Grafo dirigido


Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.


Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w) ; es decir,











Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.









Grafo no dirigido


Un grafo no dirigido (vea figura 10.1b) consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado (vea figura 10.1d).


Ejemplo


si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.
Grafo dirigido con peso


Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.


.3.4 Grafo mixto


Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas (vea figura 11.1d).











Según la figura 11.1c se podría interpretar por ejemplo, que para pasar de la actividad 1 a la 3 se tarda un tiempo p2; que pasar de actividad 3 a la 2 se tarda un tiempo p3 y, de la actividad 2 a la 1 se tardaría un tiempo p1. Un grafo no dirigido puede dibujarse con aristas dirigidas haciendo que cada lado les corresponda aristas invertidas.
Vértices adyacentes


Son aquellos que conforman un lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado.


Ejemplo 1: en G2 de la figura 11.2, son adyacentes los vértices 1 y 3. Así que la arista {1,3} incide sobre los vértices 1 y 3


En G1 de la figura 11.2: 1 es adyacente hacia 2 ó 2 es adyacente desde 1, donde la arista (1,2) incide sobre los vértices 1 y 2.


Ejemplo 2


en el grafo de la figura 11.2 la arista e1 incide sobre los vértices 1 y 2; igualmente, e7 incide sobre los vértices 5 y 6.











Representación de grafos


De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.











Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.
Representación gráfica de grafos


Los diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande. Para tal fin, puede utilizar los siguientes diagramas:









Los grafos G2, G3 y G4 son grafos no dirigidos; G1 es un grafo dirigido







Cuando un vértice se dirige a él mismo, se denomina “bucle”. Si un grafo no tiene bucles o si a lo sumo existe una arista uniendo 2 vértices cualesquiera, se denomina


















ejemplos de grafos