En la teoría de grafos , los bordes múltiples (también llamados bordes paralelos o un borde múltiple ) son, en un gráfico no dirigido, dos o más bordes que inciden en los mismos dos vértices , o en un gráfico dirigido , dos o más bordes con ambos el mismo vértice de la cola y el mismo vértice de la cabeza. Un gráfico simple no tiene múltiples aristas ni bucles .
Dependiendo del contexto, un gráfico puede definirse para permitir o no permitir la presencia de múltiples bordes (a menudo en conjunto con permitir o rechazar bucles):
- Cuando los gráficos se definen para permitir múltiples aristas y bucles, un gráfico sin bucles o aristas múltiples a menudo se distingue de otros gráficos llamándolo gráfico simple. [1]
- Cuando los gráficos se definen para no permitir múltiples aristas y bucles, un multigrafo o un pseudógrafo se define a menudo para significar un "gráfico" que puede tener bucles y múltiples aristas. [2]
Los bordes múltiples son, por ejemplo, útiles en la consideración de redes eléctricas , desde un punto de vista teórico de gráficos. [3] Además, constituyen la característica central de diferenciación de las redes multidimensionales .
Un gráfico plano permanece plano si se agrega una arista entre dos vértices ya unidos por una arista; por lo tanto, agregar varios bordes conserva la planicidad. [4]
Un gráfico dipolo es un gráfico con dos vértices, en el que todos los bordes son paralelos entre sí.
Notas
Referencias
- Balakrishnan, VK; Teoría de grafos , 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; 1a edición (12 de agosto de 2002). ISBN 0-387-98488-7 .
- Diestel, Reinhard; Teoría de grafos , Springer; 2da 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 de CRC , Chapman & Hall / CRC; 31a edición (27 de noviembre de 2002). ISBN 1-58488-291-3 .