Gráficas

Recordemos que, en general, una gráfica es un conjunto finito y no vacío de puntos relacionados entre sí. La relación, como se suele hacer en matemáticas, se determina como un conjunto de parejas ordenadas de estos puntos. Un punto $x$ estará relacionado con otro $y$ siempre que $(x,y)$ sea un elemento del conjunto de parejas.

Los puntos de la gráfica son llamados vértices o nodos, y los elementos de la relación aristas. Lo anterior se debe a que podemos hacer un dibujo donde la relación entre dos vértices dados se indique uniéndolos mediante una línea dirigida o flecha (no necesariamente recta).

Denotamos $G(V,E)$ a la gráfica compuesta por el conjunto $V$ de vértices y con $E$ como aristas (del inglés edges). Como $E$ es una relación entre los elementos de $V$ con sigo mismos, entonces $E\subset V\times V$.

Si existe algún vertice $v\in V$ tal que $(v,v)\in E$ diremos que la gráfica tiene un lazo en $v$, en tanto hay una arista, quizá un poco extraña, que sale de un vértice y regresa al mismo punto.

Cuando trabajamos con gráficas podemos especificar si distinguimos o no el sentido de las aristas, es decir, si nos importa o no que cada arista determine sólo la ida pero no el regreso entre los dos vértices que conecta. Cuando sí nos importa el sentido, estaremos considerando un digráfica o gráfica dirigida. Si no importa el sentido de las aristas hablaremos entonces de un gráfica no dirigida o simplemente gráfica, ya que lo usual es precisar sólo cuando se trata de un digráfica.

En las gráficas (no dirigidas) usamos segmentos o arcos para dibujar las aristas en lugar de flechas. En este caso, $G(V,E)$ es tal que $(v_1,v_2)\in E$ sí y solo si $(v_2,v_1)\in E$. Esto último nos muestra que cualquier digráfica puede convertirse en una gráfica (no dirigida), simplemente haciendo que $E$ tenga la propiedad anterior.

Algo que es importante notar es que aunque los vértices se encuentren divididos en grupos, o incluso aislados, de modo que no haya aristas que los conecten, tenemos de todas formas una gráfica. Lo anterior se debe a que, en principio, no existen restricciones para la relación $E$, que puede ser cualquiera, incluso $E=\emptyset$. Así, llamaremos gráficas conexas a aquellas donde podemos encontrar un camino entre cualquier par de vértices. Entendemos por camino entre dos vértices una sucesión finita de aristas (de la gráfica no dirigida asociada) que los conecta.

Dada una gráfica, podemos hablar del grado de un vértice, que denotaremos por $\hbox{grad}(v)$, para $v\in V$, que definimos como el número de aristas que concurren en ese vértice. También podemos hablar de ciclos al interior de una gráfica, que son caminos que salen de un vértice, tocan otro y regresan al primero por un camino diferente.

A continuación se muestran una digráfica y una gráfica. Ambas gráficas son planas, lo que significa que es posible reacomodar las posiciones de los vértices para que las aristas no se toquen. Comprueba que ambas gráficas son planas desplazando y reacomodando los puntos. Dado que las posiciones se escogen al azar, es conveniente asegurarse de que los puntos no cayeron accidentalemte sobre una línea.

En esta actividad podrás notar que es posible acomodar los vértices de la gráfica derecha (puntos azules) de modo que un vértice quede más abajo que el resto y colocando los demás en renglones a diferentes alturas. La forma que se obtiene se asemeja a las ramas de un árbol.

Es importante notar que hemos representado las aristas mediante segmentos de recta, pero en realidad, como mencionamos arriba, es posible usar tambien curvas o cualquier tipo de recurso gráfico que determine con precisión la relación entre dos nodos.

Aplicaciones

Las gráficas nos ayudan a modelar matemáticamente situaciones asociadas a problemas concretos. La teoría de gráficas nos provee de una buena cantidad de resultados teóricos que permiten resolver problemas de construcción y optimización, entre muchos otros.

Esta teoría puede usarse para estudiar y resolver muy eficazmente problemas relacionados con la interconexión de redes eléctricas, de comunicaciones y de transporte a todos los niveles y en múltiples facetas. También es muy útil para buscar formas óptimas y eficientes de ordenar, almacenar y recuperar información de cualquier índole.

Una herramienta importante para lo anterior la constituye el estudio de una clase particular de gráficas, los árboles.