Hispanopedia Wiki
En teoría de grafos , las aristas múltiples (también llamadas aristas paralelas o multiaristas ) son, en un grafo no dirigido , dos o más aristas que inciden en los mismos dos vértices , o en un grafo dirigido , dos o más aristas con el mismo vértice de cola y el mismo vértice de cabeza. Un grafo simple no tiene aristas múltiples ni bucles .
Dependiendo del contexto, un gráfico puede definirse de modo que permita o no la presencia de múltiples aristas (a menudo junto con la autorización o no de bucles):
- Cuando los gráficos se definen de manera que permitan múltiples aristas y bucles, un gráfico sin bucles o múltiples aristas a menudo se distingue de otros gráficos llamándolo gráfico simple. [1]
- Cuando los gráficos se definen de manera tal que no se permiten múltiples aristas y bucles, un multigráfico o un pseudográfico se define a menudo como un "gráfico" que puede tener múltiples aristas. [2]
Los bordes múltiples son útiles, por ejemplo, en la consideración de redes eléctricas , desde un punto de vista teórico de grafos. [3] Además, constituyen la característica diferenciadora central de las redes multidimensionales .
Un gráfico plano sigue siendo plano si se agrega una arista entre dos vértices ya unidos por una arista; por lo tanto, agregar múltiples aristas preserva la planaridad. [4]
Un gráfico dipolar es un gráfico con dos vértices, en el que todos los bordes son paralelos entre sí.
Notas
- ^ Por ejemplo, véase Balakrishnan, pág. 1, y Gross (2003), pág. 4, Zwillinger, pág. 220.
- ^ Por ejemplo, véase Bollobás, p. 7; Diestel, pág. 28; Harary, pág. 10.
- ^ Bollobás, págs. 39–40.
- ^ Gross (1998), pág. 308.
Referencias
- Balakrishnan, VK; Graph Theory , McGraw-Hill; 1 edición (1 de febrero de 1997). ISBN 0-07-005489-4 .
- Bollobás, Béla; Teoría de grafos moderna , Springer; 1.ª edición (12 de agosto de 2002). ISBN 0-387-98488-7 .
- Diestel, Reinhard; Graph Theory , Springer; 2.ª edición (18 de febrero de 2000). ISBN 0-387-98976-5 .
- Gross, Jonathon L, y Yellen, Jay; Teoría de grafos y sus aplicaciones , CRC Press (30 de diciembre de 1998). ISBN 0-8493-3982-0 .
- Gross, Jonathon L, y Yellen, Jay; (eds); Manual de teoría de grafos . CRC (29 de diciembre de 2003). ISBN 1-58488-090-2 .
- Zwillinger, Daniel; Tablas y fórmulas matemáticas estándar del CRC , Chapman & Hall/CRC; 31.ª edición (27 de noviembre de 2002). ISBN 1-58488-291-3 .
