4.0: Preludio a la teoría de las gráficas

Última actualización
Guardar como PDF

Page ID: 115800

$ \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}}$

Template:MathJaxLevin

¡Investiga!

En la época de Euler, en la localidad de Königsberg en Prusia, había un río que contenía dos islas. Las islas estaban conectadas a las orillas del río por siete puentes (como se ve a continuación). Los puentes eran muy hermosos, y en sus días libres, la gente del pueblo pasaba tiempo caminando sobre los puentes. Con el paso del tiempo, surgió una pregunta: ¿era posible planificar una caminata para que cruzaras cada puente una vez y solo una vez? Euler pudo responder a esta pregunta. ¿Eres tú?

$gt-bridges-art.svg$

La Teoría de las Gráficas es un área relativamente nueva de las matemáticas, estudiada por primera vez por el súper famoso matemático Leonhard Euler en 1735. Desde entonces se ha convertido en una poderosa herramienta utilizada en casi todas las ramas de la ciencia y actualmente es un área activa de investigación matemática.

El problema anterior, conocido como los Siete Puentes de Königsberg, es el problema que originalmente inspiró la teoría gráfica. Considera un problema “diferente”: A continuación se muestra un dibujo de cuatro puntos conectados por algunas líneas. ¿Es posible trazar sobre cada línea una vez y solo una vez (sin levantar el lápiz, comenzar y terminar en un punto)?

$gt-bridges-graph.svg$

Hay una conexión obvia entre estos dos problemas. Cualquier camino en el dibujo de puntos y líneas corresponde exactamente a un camino sobre los puentes de Königsberg.

Las imágenes como el dibujo de puntos y líneas se llaman gráficas. Las gráficas están compuestas por una colección de puntos llamados vértices y líneas que conectan esos puntos llamados bordes. Cuando dos vértices están conectados por un borde, decimos que son adyacentes. Lo bueno de mirar gráficos en lugar de cuadros de ríos, islas y puentes es que ahora tenemos un objeto matemático que estudiar. Hemos destilado las partes “importantes” de la imagen del puente para los fines del problema. No importa cuán grandes sean las islas, de qué están hechos los puentes, si el río contiene caimanes, etc. Todo lo que importa es qué masas de tierra están conectadas a qué otras masas de tierra, y cuántas veces. Esta fue la gran perspicacia que tuvo Euler.

Volveremos a la cuestión de encontrar caminos a través de gráficas más adelante. Pero primero, aquí hay algunas otras situaciones que puedes representar con gráficas:

Ejemplo$\PageIndex{1}$

Al, Bob, Cam, Dan y Euclid son todos miembros del sitio web de redes sociales Facebook. El sitio permite que los miembros sean “amigos” entre sí. Resulta que Al y Cam son amigos, al igual que Bob y Dan. Euclides es amigo de todos. Representar esta situación con una gráfica.

Solución

Cada persona estará representada por un vértice y cada amistad estará representada por una arista. Es decir, dos vértices serán adyacentes (habrá una arista entre ellos) si y sólo si las personas representadas por esos vértices son amigas. Obtenemos la siguiente gráfica:

$gt-facebook.svg$

Ejemplo$\PageIndex{1}$

Each of three houses must be connected to each of three utilities. Is it possible to do this without any of the utility lines crossing?

Solution

We will answer this question later. For now, notice how we would ask this question in the context of graph theory. We are really asking whether it is possible to redraw the graph below without any edges crossing (except at vertices). Think of the top row as the houses, bottom row as the utilities.

$gt-k33.svg$