14: Colorear Gráfica
- Page ID
- 114396
\( \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}}\)
- 14.1: Colorear Bordes
- Supongamos que te han dado el trabajo de programar un torneo de tenis round robin con n jugadores. Una forma de abordar el problema es modelarlo como una gráfica: los vértices de la gráfica representan a los jugadores y los bordes representan los partidos que deben jugarse. Ya que se trata de un torneo de todos contra todos, cada jugador debe jugar a cualquier otro jugador para que la gráfica esté completa. Crear el horario equivale a asignar un tiempo a cada uno de los bordes, representando el tiempo que se jugará el partido.
- 14.2: Teoría de Ramsey
- Aunque la Teoría Ramsey es una parte importante de la Combinatoria (junto con la Enumeración, la Teoría de Gráficas y la Teoría del Diseño), este curso la tocará solo muy a la ligera. La idea básica es que si un objeto muy grande se corta en dos piezas (o un pequeño número de piezas), entonces al menos una de las piezas debe contener un subconjunto muy agradable.
- 14.3: Coloración de vértices
- Supongamos que se le ha dado la tarea de asignar frecuencias de difusión a torres de transmisión. Se le ha dado una lista de frecuencias que se le permite asignar. Hay una restricción: a las torres que están demasiado juntas no se les puede asignar la misma frecuencia, ya que interferirían entre sí. Una forma de abordar este problema es modelarlo como una gráfica.
- 14.4: Resumen
- Esta página abarca el resumen de los temas tratados en el Capítulo 14.