12: Moviéndose a través de gráficos
- Page ID
- 114449
\( \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}}\)
- 12.1: Gráficas dirigidas
- Algunas redes incluyen conexiones que solo permiten viajar en una dirección. Estos se pueden modelar usando gráficas dirigidas. Al dibujar un dígrafo, dibujamos una flecha en cada arco para que apunte desde el primer vértice del par ordenado hasta el segundo vértice. Al igual que los multígrafos, no vamos a estudiar dígrafos en este curso, pero debes estar al tanto de la definición básica. Muchos de los resultados que cubriremos en este curso, se generalizan al contexto de los dígrafos.
- 12.2: Paseos y conectividad
- Las gráficas se pueden conectar o desconectar. Intuitivamente, esto corresponde a que la red esté conectada o desconectada — ¿es posible viajar de cualquier nodo a cualquier otro nodo? Cuando se desconecta una gráfica (o red), se ha dividido en cierto número de componentes conectados separados, las piezas que aún están conectadas. Dado que esto es matemática, requerimos definiciones más formales, para asegurar que los significados no estén abiertos a malentendidos.
- 12.3: Caminos y Ciclos
- Recordemos la definición de un paseo. Como vimos en el Ejemplo 12.2.1, los vértices y aristas en una caminata no necesitan ser distintos. Hay muchas circunstancias en las que tal vez no queramos permitir que se vuelvan a visitar aristas o vértices. La eficiencia es una posible razón para ello. Tenemos un nombre especial para un paseo que no permite volver a visitarse vértices.
- 12.4: Árboles
- Una clase especial de gráficas que surgen a menudo en la teoría de grafos, es la clase de árboles. Si un matemático sospecha que algo es cierto para todas las gráficas, una de las primeras familias de gráficas para las que probablemente intentará demostrarlo, es la familia de árboles porque su fuerte estructura los hace mucho más fáciles de trabajar que muchas otras familias de gráficas.
- 12.5: Resumen
- Esta página contiene el resumen de los temas tratados en el Capítulo 12.