Grafos. Elementos y Características

...

Obsérvese que si se hicieran todas las permutaciones, suponiendo un caso muy reducido de diez casas, se tendrían más de 3 millones de permutaciones (10!). Si cada casa es representada por un vértice y cada camino entre par de casas por una arista ponderada por la distancia mínima entre pares de casas, tendremos un grafo completo y simétrico (cuando no hay calles flechadas).

El problema se reduce entonces, a obtener un camino hamiltoniano óptimo. Todo algoritmo conocido para encontrar ciclos hamiltonianos requiere al menos un tiempo exponencial de cálculo, o factorial en el peor de los casos. Otro ejemplo para el que grafos provee un natural modelo matemático: Supongamos que el siguiente grafo representa una red de líneas de teléfonos (o de comunicaciones).

Estamos interesados en la vulnerabilidad respecto a interrupciones accidentales. Problema 1: identificar esas líneas y centros de conecciones que deben permanecer en servicio para evitar la desconección de la red. No existe ninguna línea que eliminada desconecte el grafo (red), pero hay un vértice, el vértice d, cuya desaparición (ruptura) desconecta el grafo. Problema 2: encontrar un conjunto mínima de aristas necesarias para conectar los 6 vértices. [pic 8]

Hay varios conjuntos mínimos posibles. Uno de ellos es el conjunto mínima: {(a,b),(b,c),(c,d),(d,e),(d,f)}. Podemos enunciar el siguiente resultado general: dado un grafo G de n vértices, el conjunto mínimo de conexión de G (si existe) siempre tiene n–1 aristas.

A continuación ya definido el origen de los grafos por el matemático Euler daremos apertura a sus aplicaciones en la Telemática, Redes o Comunicaciones, Tránsito Terrestre o Área Marítima, Sistema GPS, Organigramas, la Informática u otros.

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).

- Definición de Términos

1.1 Grafos

Es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

1.2 Elementos y CaracterísticasA partir de esta figura se definen los siguientes elementos:

- Vértices (nodos)[pic 9]

Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a, b, c, d}.

- Lados (ramas o aristas)

Son las líneas que unen un vértice con otro y se les asigna una letra, un número o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.

- Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P= {2,3}.

- Lazo

Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}

- Valencia de un vértice

Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2

Valencia (b)=4

Valencia (c)=2

Valencia (d)=3

Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.

1.3 Componentes

- Aristas :

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

- Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

- Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

- Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

- Cruce: Son dos aristas que cruzan en un punto.

- Vértices :

Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

- Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

- Vértice Aislado: Es un vértice de grado cero.

- Vértice Terminal: Es un vértice de grado 1.

1.4 Tipos de Grafos

- Grafos Simples

Son aquellos grafos que no tienen lazos ni lados paralelos.

[pic 10]

- Grafo Completo de N Vértices (Kn)

Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como (kn) en donde n es el número de vértices del grafo.[pic 11]

La valencia en cada uno de los vértices de los grafos completos es (n–1), y el número de lados está dado por la expresión:

[pic 12]

en donde n es el número de