Teoría de Grafos: Teoría de Grafos

Teoría de Grafos

La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

Grafo

Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro.

Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

Se considera la característica de "grado" (positivo o negativo) de un vértice, como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de b es 1.

La figura 8.1.4 muestra una gráfica dirigida. Las aristas dirigidas se indican por flechas. La arista e1 se asocia con el par ordenado de vértices (v2, v1) y la arista e7 se asocia con el par ordenado de vértices (v6, v6). La arista e1 se denota (v2, v1), y la arista e7 se denota (v6, v6).

La definición 8.1.1 permite que diferentes aristas se asocien con el mismo par de vértices. Por ejemplo, en la figura 8.1.5, las aristas e1 y e2 se asocian ambas con el par de vértices {v1, v2}. Estas aristas se llaman aristas paralelas. Una arista incidente en un mismo vértice se llama lazo. Por ejemplo, en la figura 8.1.5, la arista e3 =(v2, v2) es un lazo. Un vértice como v4 en la figura 8.1.5, que no incide en ninguna arista, se llama vértice aislado. Una gráfica sin lazos ni aristas paralelas se llama gráfica simple.

Se dará un ejemplo que muestra cómo se utiliza un modelo de gráficas para analizar un problema de manufactura.

Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de metal (vea la figura 8.1.6). Luego se atornillan las componentes a estas hojas de metal. Los agujeros se perforan usando un taladro controlado por computadora. Para ahorrar tiempo y dinero, el taladro debe moverse tan rápido como sea posible. Se modelará la situación como una gráfica. Los vértices de la gráfica corresponden a los agujeros (figura 8.1.7). Cada par de vértices se conecta por una arista. En cada arista se escribe el tiempo para mover el taladro entre los hoyos correspondientes. Una gráfica con números en las aristas (como en la figura 8.1.7) se llama gráfica ponderada.

Suponga que en este problema se requiere que la trayectoria comience en el vértice a y termine en el vértice e. Se puede encontrar la ruta de longitud mínima numerando todas las rutas posibles de a a e que pasan por todos los vértices justo una vez y eligiendo la menor (vea la tabla 8.1.1). Se ve que la ruta que visita los vértices a, b, c, d, e, en ese orden, tiene longitud mínima. Por supuesto, un par diferente de vértices de inicio y terminación produciría una ruta aún más corta.

EJERCICIO:

En un torneo, el Nieve venció a loa Faisanes una vez, el Rascacielos venció al Tuna una vez, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron a el Tuna una vez, y los Faisanes vencieron al Rascacielos una vez, en los ejercicios del 1 al 4, use una gráfica para modelar el torneo, los equipos son los vértices. Describa el tipo de gráfica usada, (no dirigida, dirigida, simple).

1.Hay una arista entre los equipos , si los equipos jugaron.