15: Gráficas Planares
- Page ID
- 114427
\( \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}}\)
- 15.1: Gráficas Planas
- Visualmente, siempre existe el riesgo de confusión cuando se dibuja una gráfica de tal manera que algunos de sus bordes se cruzan entre sí. Además, en las realizaciones físicas de una red, dicha configuración puede generar costos adicionales (piense en construir un paso elevado en comparación con construir una intersección). Por lo tanto, es útil poder determinar si una gráfica en particular se puede dibujar o no de tal manera que no se crucen bordes.
- 15.2: Fórmula de Euler
- A Euler se le ocurrió una fórmula que es válida para cualquier incrustación plana de un gráfico conectado. Si intentas probar la fórmula de Euler por inducción sobre el número de vértices, eliminar un vértice podría desconectar la gráfica, lo que significaría que la hipótesis de inducción no se aplica a la gráfica resultante. Sin embargo, existe una operación gráfica diferente que reduce el número de vértices en 1 y mantiene la gráfica conectada. Esta operación se llama contracción de borde.
- 15.3: Colorear Mapa
- Supongamos que tenemos un mapa de una isla que ha sido dividida en estados. Tradicionalmente, los creadores de mapas colorean los diferentes estados para asegurar que si dos estados comparten una frontera, no se coloquen con el mismo color. La pregunta es, sin saber de antemano cómo será el mapa, ¿hay algún límite sobre cuántos colores se requerirán para colorearlo? Si es así, ¿qué es eso atado? En otras palabras, ¿cuál es el mayor número de colores que podrían requerirse para colorear algún mapa?
- 15.4: Resumen
- Esta página contiene el resumen de los temas tratados en el Capítulo 15.