6.2: Gráficas

Última actualización
Guardar como PDF

Page ID: 110635

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Gráficas de dibujo

Ejemplo 1

Aquí hay una porción de un desarrollo habitacional de Missoula, Montana [1]. Como parte de su trabajo, el inspector de césped del desarrollo tiene que caminar por todas las calles del desarrollo asegurándose de que el paisajismo de los propietarios se ajuste a los requisitos de la comunidad.

$clipboard_e3234824b359f527fc7293e4adc684a2c.png$

Solución

Naturalmente, quiere minimizar la cantidad de caminar que tiene que hacer. ¿Es posible que ella camine por todas las calles de este desarrollo sin tener que hacer ningún retroceso? Si bien es posible que puedas responder esa pregunta con solo mirar la imagen por un tiempo, sería ideal poder responder a la pregunta para cualquier imagen independientemente de su complejidad.

Para ello, primero necesitamos simplificar la imagen en una forma con la que sea más fácil trabajar. Podemos hacerlo dibujando una línea simple para cada calle. Donde las calles se cruzan, colocaremos un punto.

$clipboard_efd3110477b5288027be3334e3b6f4634.png$ $gt2.svg$

Este tipo de imagen simplificada se llama gráfica.

Gráficas, vértices y aristas

Una gráfica consiste en un conjunto de puntos, llamados vértices, y un conjunto de aristas que conectan pares de vértices.

Si bien dibujamos nuestra gráfica original para que se corresponda con la imagen que teníamos, no hay nada particularmente importante en el diseño cuando analizamos una gráfica. Ambas gráficas a continuación son equivalentes a la dibujada arriba ya que muestran las mismas conexiones de borde entre los mismos vértices que la gráfica original.

$gt3.svg$

Probablemente ya se dio cuenta de que estamos usando el término graph de manera diferente a lo que pudo haber usado el término en el pasado para describir la gráfica de una función matemática.

Ejemplo 2

$clipboard_e28b234701a5f1bdb02e13cff366ed8e3.png$ Allá por el ^siglo XVIII en la ciudad prusiana de Königsberg, un río atravesaba la ciudad y siete puentes cruzaban las horquillas del río. El río y los puentes se destacan en la imagen a la derecha [2].

Como diversión de fin de semana, los habitantes del pueblo verían si podían encontrar una ruta que los llevara a través de cada puente una vez y los devolviera a donde comenzaron.

Solución

Leonard Euler (pronunciado Oy-lur), uno de los matemáticos más prolíficos de la historia, miró este problema en 1735, sentando las bases para la teoría de grafos como campo de las matemáticas. Para analizar este problema, Euler introdujo aristas que representan los puentes:

$gt4.svg$

Dado que el tamaño de cada masa terrestre no es relevante para la cuestión de los cruces de puentes, cada uno puede ser reducido a un vértice que representa la ubicación:

$gt5.svg$

Observe que en esta gráfica hay dos aristas que conectan la orilla norte y la isla, correspondientes a los dos puentes del dibujo original. Dependiendo de la interpretación de aristas y vértices apropiados a un escenario, es completamente posible y razonable tener más de un borde conectando dos vértices.

Si bien aún no hemos respondido a la pregunta real de si existe o no una ruta que cruce cada puente una vez y regrese a la ubicación inicial, la gráfica proporciona la base para explorar esta pregunta.

Definiciones

Si bien antes definimos vagamente alguna terminología, ahora trataremos de ser más específicos.

Vertex

Un vértice es un punto en la gráfica que podría representar una intersección de calles, una masa de tierra, o una ubicación general, como “trabajo” o “escuela”. Los vértices suelen estar conectados por bordes. Tenga en cuenta que los vértices solo ocurren cuando un punto se coloca explícitamente, no cuando dos bordes se cruzan. Imagínese un paso elevado de autopista —la autopista y la calle lateral cruzan, pero no es posible cambiar de la calle lateral a la autopista en ese punto, por lo que no hay intersección y no se colocaría ningún vértice.

Bordes

Los bordes conectan pares de vértices. Un borde puede representar una conexión física entre ubicaciones, como una calle, o simplemente que existe una ruta que conecta las dos ubicaciones, como un vuelo de una aerolínea.

Bucle

Un bucle es un tipo especial de borde que conecta un vértice consigo mismo. Los bucles no se utilizan mucho en las gráficas de redes de calles.

$gt6.svg$

Grado de un vértice

El grado de un vértice es el número de aristas que se encuentran en ese vértice. Es posible que un vértice tenga un grado de cero o mayor.

$gt7.svg$

Camino

Un camino es una secuencia de vértices que utilizan los bordes. Por lo general nos interesa un camino entre dos vértices. Por ejemplo, a continuación se muestra una ruta desde el vértice A hasta el vértice M. Es uno de los muchos caminos posibles en esta gráfica.

$gt8.svg$

Circuito

Un circuito es un camino que comienza y termina en el mismo vértice. A continuación se muestra un circuito que comienza y termina en el vértice A.

$gt9.svg$

Conectado

Una gráfica está conectada si hay una ruta desde cualquier vértice a cualquier otro vértice. Cada gráfico dibujado hasta ahora ha sido conectado. El gráfico de abajo está desconectado; no hay manera de llegar de los vértices de la izquierda a los vértices de la derecha.

$gt10.svg$

Pesas

Dependiendo del problema que se resuelva, a veces se asignan pesos a los bordes. Los pesos podrían representar la distancia entre dos ubicaciones, el tiempo de viaje o el costo del viaje. Es importante señalar que la distancia entre vértices en una gráfica no corresponde necesariamente al peso de una arista.

Pruébalo ahora 1

La gráfica a continuación muestra 5 ciudades. Los pesos en los bordes representan el pasaje aéreo para un vuelo de ida entre las ciudades.

¿Cuántos vértices y aristas tiene la gráfica?
¿Está conectada la gráfica?
¿Cuál es el grado del vértice que representa LA?
Si vuelas de Seattle a Dallas a Atlanta, ¿es eso un camino o un circuito?
Si vuelas de Los Ángeles a Chicago a Dallas a Los Ángeles, ¿es eso un camino o un circuito?

$gt11.svg$

Contestar

a. 5 vértices, 10 aristas

b. Sí, está conectado

c. El vértice es grado 4

d. Un camino

e. Un circuito

[1] Sam Beebe. http://www.flickr.com/photos/sbeebe/2850476641/, CC-BY

[2] Bogdan Giuşcă. http://en.Wikipedia.org/wiki/File:Ko...rg_bridges.png