11.1: Antecedentes
- Page ID
- 114405
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
En combinatoria, lo que llamamos una gráfica no tiene nada que ver con los\(y\) ejes\(x\) y, y el trazado. Aquí, una gráfica es la forma más sencilla que se te ocurra para modelar una red. Una red podría ser una red informática, una red de carreteras, una red telefónica; no importa qué tipo de red sea. Conceptualmente, cualquier red consiste en un montón de cosas (llamémoslos nodos) que están siendo conectadas de alguna manera. Para modelar esto, dibujamos algunos puntos para los nodos, y dibujamos bordes entre nodos que tienen una conexión directa.
Leonhard Euler sentó las bases de la teoría gráfica en\(1735\), con su solución al problema del puente Königsberg. Königsberg, Prusia (ahora Kaliningrado, Rusia) era una ciudad en el río Pregel. La ciudad incluía dos islas en el río, así como terrenos a ambos lados del río, y había siete puentes que conectaban las distintas partes de la ciudad. El trazado de la ciudad y sus puentes se veían así:
Se había planteado la pregunta: ¿es posible que los residentes de Königsberg, salgan a pasear los domingos, crucen cada uno de los siete puentes exactamente una vez? Mejor aún, ¿pueden hacer esto y terminar en la misma parte de la ciudad donde empezaron?
Euler modeló el problema usando una gráfica, con un vértice para cada parte de la ciudad (uno para cada banco y otro para cada isla), y bordes que representan los puentes. Su modelo se veía así:
Los nodos\(A\) y\(C\) representan las dos orillas del río, mientras que\(B\) y\(D\) representan las islas. En el modelo, la pregunta se convierte en ¿podemos trazar todos los bordes de esta gráfica, sin levantar nuestra pluma del papel o pasar por encima de un borde más de una vez?
De hecho, Euler pudo encontrar un método fácil que puedes usar en cualquier gráfica, para determinar rápidamente si esto se puede hacer o no para esa gráfica. Además, a diferencia de lo que vimos en el Principio de Pigeonhole, su método es constructivo: si se puede hacer, su método te muestra cómo hacerlo. Repasaremos este método más adelante, en el Capítulo 13.