grafos

GRAFOS
CREACIÓN DE ÍNDICES EN GOOGLE DE
LOS SITIOS DE LA RED DE INTERNET





INDICE



1. Introducción

2. Conceptos matemáticos con ejemplos

3. Resolución de ejercicios

4. Ejercicios con Maxima

5. Explicación del modelo ilustrada con un ejemplo

6. Ejercicios propuestos sobre el tema

7. Bibliografía















1. Introducción

La teoría degrafos 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. Puedenutilizarse, 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…

Elprimer 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:



2. Conceptos matemáticos con ejemplos

Grafo. “Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relacionesbinarias entre elementos de un conjunto.” 1

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.” 2

Tipos de grafos.

Grafos simples. Un grafo simple es un conjunto de vértices y aristas. Las aristas unenpares 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, tienenaristas 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 aristaincidente 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....