11: Conceptos básicos de la teoría de grafos
- Page ID
- 114397
\( \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}}\)
- 11.1: Antecedentes
- En combinatoria, lo que llamamos una gráfica no tiene nada que ver con los ejes x e 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, etc. 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.
- 11.2: Definiciones básicas, terminología y notación
- Ahora que tenemos una comprensión intuitiva de lo que es una gráfica, es el momento de hacer una definición formal.
- 11.3: Eliminación, gráficos completos y el lema de apretón de manos
- Comenzaremos esta sección introduciendo una operación básica que puede cambiar una gráfica (o un multígrafo, con o sin bucles) en una gráfica más pequeña: la eliminación. Entonces, definiremos una familia muy importante de gráficas, llamadas gráficas completas. Por último, presentaremos el lema de apretón de manos de Euler.
- 11.4: Isomorfismos gráficos
- Hay un problema con la forma en que hemos definido a Kn. Se supone que una gráfica consiste en dos conjuntos, V y E. A menos que los elementos de los conjuntos estén etiquetados, no podemos distinguir entre ellos. ¿Cuál de estas gráficas es K2? Ambos no pueden ser K2 ya que no son la misma gráfica — ¿o sí? La respuesta está en el concepto de isomorfismos.
- 11.5: Resumen
- Esta página contiene el resumen de los temas tratados en el Capítulo 11.