6: Teoría de las Gráficas
- Page ID
- 109942
\( \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}}\)
La teoría gráfica trata de problemas de ruteo y red y si es posible encontrar una “mejor” ruta, ya sea que eso signifique la menos costosa, la menor cantidad de tiempo o la menor distancia. Algunos ejemplos de problemas de ruteo son rutas cubiertas por trabajadores postales, conductores de UPS, policías, personal de eliminación de basura, lectores de contadores de agua, censistas, autobuses turísticos, etc. Algunos ejemplos de problemas de red son las redes telefónicas, sistemas ferroviarios, canales, carreteras, ductos y chips de computadora.
- 6.1: Teoría gráfica
- Algunas definiciones son importantes de entender antes de profundizar en la Teoría de Gráficas: (1) Una gráfica es una imagen de puntos llamados vértices y líneas llamadas bordes. (2) Un borde que comienza y termina en el mismo vértice se llama bucle. (3) Si hay dos o más bordes que conectan directamente los mismos dos vértices, entonces estos los bordes se llaman múltiples aristas. (4) Si hay una manera de llegar de un vértice de una gráfica a todos los demás vértices de la gráfica, entonces la gráfica se conecta, de lo contrario se desconecta.
- 6.2: Redes
- Una red es una conexión de vértices a través de aristas. Internet es un ejemplo de una red con computadoras como vértices y las conexiones entre estas computadoras como bordes.
- 6.3: Circuitos de Euler
- Leonhard Euler discutió y utilizó por primera vez los caminos y circuitos de Euler en 1736. En lugar de encontrar un árbol de expansión mínimo que visite cada vértice de una gráfica, se puede usar una ruta o circuito de Euler para encontrar la manera de visitar cada borde de una gráfica una y solo una vez. Esto sería útil para verificar los parquímetros a lo largo de las calles de una ciudad, patrullar las calles de una ciudad o entregar correo.
- 6.4: Circuitos Hamiltonianos
- El problema del vendedor ambulante (TSP) es cualquier problema en el que debes visitar cada vértice de una gráfica ponderada una vez y solo una vez, y luego terminar de nuevo en el vértice inicial. Ejemplos de situaciones de TSP son entregas de paquetes, fabricación de placas de circuitos, programación de trabajos en una máquina y hacer recados por la ciudad.
Miniaturas: Gráfica Königsberg (CC BY-SA 3.0; Booyabazooka vía Wikipedia)