Digrafos






Introducción:
La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática y de la cual también se derivan otras. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas en la vida cotidiana y haciendo que el alumno aprenda a buscar modelos matemáticos adecuados para grannúmero de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional de un Ingeniero sea cual sea su rama de estudio.
El tratamiento que se pretende dar a este tema es práctico y la manera de como aprender a resolver cada uno de ellos.













Objetivo general:
Mediante este trabajo se emplea a conocer sobre los dígrafos y aprender cómo utilizar ydiferenciar cada tipo de dígrafos.


















Historia de grafos

LOS SIETE PUENTES DE LA ISLA KUEIPHOF

Se tiene referencia por primera de vez sobre lo que es Grafos en el año 1736 en donde un matemático suizo de nombre Leonard Euler, publicó un artículo en el cual daba una posible solución o respuesta al problema que tenían con el paso de los puentes.
La isla Kueiphof enKoenigsberg se dividía en dos brazos y en los que se encontraban alrededor de 7 puentes y para la población de ese lugar les era difícil conocer el itinerario de los puentes hasta regresar donde comenzaron, además, esto era después de haber cruzado los puentes una vez por cada uno de ellos. (Departamento de Matemáticas / Centro de Sistema Inteligentes ITESM, ps.2-3)
Según el INSTITUTO TECNOLOGICODE MONTERREY. (2008 pg. 204) Dice que Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas.
Estudió si una figura lineal se podía dibujar con un solo trazo, sin levantar ellápiz del papel y sin pasar dos veces por el mismo sitio.






Teoría de Grafos:
Según la edición UPC (2001) [PDF] consulta (pag.110) expresa que Los grafos nos son de mucha ayuda en la vida porque se pueden utilizar en diversas áreas o campos de trabajo para hacer relaciones entre diferentes objetos, esta teoría permite modelar de forma simple cualquier sistema en el cual exista unarelación y es por esto que su ámbito de aplicación es muy general.

Definiciones básicas:
Dígrafos o grafos dirigidos:
La definición de Dígrafos es la que deriva del grafo este exige que las aristas E sean pares ordenados para los vértices V.

Un dígrafo es una terna G = (V,E)
V es el conjunto de vértices.
E el conjunto de aristas o arcos
y & la función de incidencia: & : A  VXV
Eneste caso la función de incidencia se dice dirigida.

En los dígrafos como en los grafos estos poseen recorrido, camino y ciclo. Por ejemplo un camino es desde el vértice inicial hasta el siguiente. La distancia de un dígrafo no tiene propiedad simétrica ya que d(u,v) no es igual a d(v,u).
En un dígrafo se pueden distinguir diferentes tipos de conectividad.
-El dígrafo G es débilmenteconexo si el grafo (multígrafo) que resulta suprimir las direcciones de los arcos es conexo.
-G es unilateralmente conexo si para todo u,v E V(G) existe un camino de u hacia v o un camino de v hacia u.
-El dígrafo G es fuertemente conexo si para todo u,v E V(G) existe un camino de u hacia v.
FUNCIÓN GRADO EN UN DÍGRAFO:
Comencemos por enunciar algunas definiciones relativas al grado de un vértice.GRADO POSITIVO: cantidad de aristas que inciden positivamente en el vértice (son las que “entran” al vértice).
Se denota g+(v)
GRADO NEGATIVO: cantidad de aristas que inciden negativamente en el vértice (son las que “salen” del vértice).
Se denota g-(v)
GRADO TOTAL: es la suma de los grados positivo y negativo. Se denota g(v)

GRADO NETO: es la diferencia entre el grado positivo y el...