Grafos

UNIVERSIDAD TÉCNICA

DE

COMERCIALIZACIÓN Y DESARROLLO

INVESTIGACION DE OPERACIONES

GRAFOS

PROFESOR

Ing. Magno Ayala

ALUMNA

JULIETA MARTINEZ

Fdo. De la Mora - Paraguay

2014

Introducción

La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos, estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.

La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología.

Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.

En el presente trabajo estudiaremos la definición de grafo y también conoceremos los tipos de grafos.

Aprenderemos además las terminologías o propiedades de los grafos, así como también hablaremos acerca de sus diferentes usos y sus múltiples aplicaciones en distintas áreas.

Un poco de historia

La teoría de grafos es una disciplina antigua con muchas aplicaciones modernas. Sus ideales básicos fueron introducidos por el gran matemático suizo Leonhard Euler (1700-1783) en el siglo XVIII. L. Euler utilizó los grafos para resolver el famoso problema de los puentes de Königsberg que se considera el primer trabajo sobre esta materia.

Los grafos se emplean para resolver problemas de diversas áreas. Pueden utilizarse, por ejemplo, para determinar si se puede o no implementar un circuito sobre una placa de una sola capa, para estudiar la estructura de una red de Internet, para determinar si dos ordenadores están conectados o no dentro de una red informatizada, para hallar el camino más corto entre dos ciudades en una red de transportes, para trazar rutas de vuelo en un espacio aéreo concreto.

El primer ejemplo de trabajo con grafos fue este trabajo que surgió para resolver un problema en la ciudad de Königsberg (Rusia). La ciudad estaba dividida en cuatro partes por dos brazos del río Pregel estando conectadas por siete puentes.

La pregunta que se hizo L. Euler fue: ¿Es posible recorrer los siete puentes pasando por todos ellos una única vez, partiendo y llegando al mismo sitio?.

Para intentar resolver este problema representó esquemáticamente las áreas de tierra por puntos y los puentes por líneas conectando esos puntos. El resultado fue el siguiente grafo:

Grafo. “Informalmente, 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.”

Definición formal. “Un grafo es un par G = (V,E), donde V es un conjunto finito no vacío, cuyos elementos se llaman vértices o nodos y, E es una familia, cuyos elementos se llaman aristas. Una rasita es un par no ordenado de vértices de V.”

Tipos de grafos.

Grafos simples. Un grafo simple es un conjunto de vértices y aristas. Las aristas unen pares de vértices, no habiendo dos aristas que conecten el mismo par.

Multigrafos. Son grafos que contienen dos aristas que conectan el mismo par de vértices.

Pseudografos. Son multigrafos que permiten la existencia de lazos o aristas que unen un vértice consigo mismo.

Grafos dirigidos. Son grafos que, indistintamente de si son simples, multigrafos, o pseudografos, tienen aristas con dirección o aristas dirigidas. Los grafos sin aristas dirigidas son grafos no dirigidos.

Terminologías o propiedades.

Etiquetado. Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto, es decir, asignarle a cada vértice o arista un nombre. Quedan registrados los vértices A y B y la arista que los une como e1.

Adyacencia. Se dice que dos vértices son adyacentes si hay una arista que los conecte entre ellos. A y B son adyacentes.

Grado de un vértice. El grado de un vértice es un número natural de 0 al infinito que designa el número de aristas le conectan con otros vértices. El grado de A es 2.

Incidencia. Una arista es incidente a un vértice si ésta lo une a otro. E1 es una arista incidente entre A y B.

Ponderación. Corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. El valor ponderado de la arista entre A y B es 6.

Camino. Un camino es una secuencia de aristas que comienzan en un vértice del grafo y recorren parte o la totalidad del grafo conectando vértices adyacentes. E,R,T,Y,U,I es un camino del grafo.

Circuito. Cuando existe un camino que empieza y acaba en el mismo vértice. El siguiente grafo contiene el circuito V,B,N,M,V.

Isomorfismo. Si dos grafos son isomorfos sólo varía la apariencia, es decir, que se mantienen las adyacencias, estructura, caminos, ciclos, número de vértices y número de aristas. Los dos grafos son isomorfos.

Conexo.

...