Múltiples bordes

En teoría de grafos, los bordes incidentes/dirigidos entre los mismos vértices

Aristas múltiples que unen dos vértices.

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

1. Por ejemplo, véase Balakrishnan, pág. 1, y Gross (2003), pág. 4, Zwillinger, pág. 220.
2. Por ejemplo, véase Bollobás, p. 7; Diestel, pág. 28; Harary, pág. 10.
3. Bollobás, págs. 39–40.
4. 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 .