5.2: Multígrafos- Bucles y Múltiples Bordes

Última actualización
Guardar como PDF

Page ID: 118452

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \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}}\)

Considera una gráfica en la que los vértices representan ciudades y los bordes representan autopistas. Ciertos pares de ciudades están unidos por un borde mientras que otros pares no lo están. El gráfico puede o no estar conectado (aunque es probable que un gráfico desconectado resulte en viajeros descontentos). Sin embargo, ciertos aspectos de las redes de carreteras reales no son capturados por este modelo. Primero, entre dos ciudades cercanas, en realidad puede haber varias autopistas interconectadas, y viajar por una de ellas es fundamentalmente diferente de viajar por otra. Esto lleva al concepto de múltiples aristas, es decir, permitiendo más de un borde entre dos vértices adyacentes. También, podríamos tener una autopista que salga de una ciudad, pase por el campo cercano y regrese a la misma ciudad donde se originó. Esto lleva al concepto de un bucle, es decir, un borde con ambos puntos finales siendo el mismo vértice. Además, podemos permitir más de un bucle con el mismo punto final.

En consecuencia, los autores suelen llevar a cabo una discusión sobre un tema de teoría de grafos con una o dos oraciones como:

En este trabajo, todas las gráficas serán simples, es decir, no vamos a permitir bucles o múltiples aristas.
En este trabajo, las gráficas pueden tener bucles y múltiples aristas.

La terminología está lejos de ser estándar, pero en este texto, una gráfica siempre será una gráfica simple, es decir, sin bucles o múltiples aristas. Cuando queremos permitir bucles y múltiples aristas, usaremos el término multígrafo. Esto sugiere la pregunta de lo que llamaríamos una gráfica si se permite tener bucles pero no múltiples bordes, o si se permiten múltiples bordes pero no bucles. Si realmente necesitábamos hablar de tales gráficos, entonces el idioma inglés viene a nuestro rescate, ¡y simplemente declaramos la restricción explícitamente!