Aristas múltiples

En teoría de grafos, las aristas múltiples (también llamadas aristas paralelas o una multi-arista), son dos o más aristas que son incidentes (es decir, que conectan) a al menos dos vértices. Los grafos sin aristas múltiples son llamados grafos simples.

Cuando un grafo admite aristas múltiples, se llama multigrafo.

Dependiendo del contexto, un grafo puede definirse de manera que permita o no la presencia de aristas múltiples (del mismo modo que a veces se permite y a veces no la presencia de bucles):

• En un contexto en que se permiten la presencia de aristas múltiples y bucles, un grafo sin bucles es usualmente llamado multigrafo.^[1]
• En un contexto en que no se permiten aristas múltiples y bucles, un multigrafo o pseudografo es definido para referirse a un "grafo" que puede tener bucles y aristas múltiples.^[2]

Las aristas múltiples son útiles, por ejemplo, en la consideración de redes eléctricas, desde un punto de vista de teoría de grafos.^[3]

Un grafo planar permanece planar si es añadida una arista entre dos vértices ya unidos por una arista; por lo tanto, la agregación de aristas múltiples preserva la planaridad.^[4]

Notas

1. Ver por ejemplo Balakrishnan, p. 1, y Gross (2003), p. 4, Zwillinger, p. 220.
2. Ver por ejemplo Bollobas, p. 7, Diestel, p. 25, y Harary, p. 10.
3. Bollobas, pp. 39, 40.
4. Gross (1998), p. 308.

Referencias

• Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1.ª edición (1 de febrero de 1997). ISBN 0-07-005489-4.
• Bollobas, Bela; Modern Graph Theory, 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; Graph Theory and Its Applications, CRC Press (30 de diciembre de 1998). ISBN 0-8493-3982-0.
• Gross, Jonathon L, y Yellen, Jay; (eds); Handbook of Graph Theory. CRC (29 de diciembre de 2003). ISBN 1-58488-090-2.
• Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31a edición (27 de noviembre de 2002). ISBN 1-58488-291-3.

• Datos: Q6934937