Arestes múltiples

Quan un graf admet arestes múltiples, es diu multigraf

En matemàtiques, i més concretament en teoria de grafs, les arestes múltiples (també anomenades arestes paral·leles o una multiaresta) són dues o més arestes que són incidents (és a dir, que connecten) a almenys dos vèrtexs. Els grafs sense arestes múltiples són anomenats grafs simples.

Depenent del context, un graf es pot definir de manera que permeti o no la presència d'arestes múltiples (de la mateixa manera que de vegades es permet i de vegades no la presència de bucles):

• En un context en què es permeten la presència d'arestes múltiples i bucles, un graf sense bucles és usualment anomenat multigraf.
• En un context en què no es permeten arestes múltiples i bucles, un multigraf o pseudograf és definit per referir-se a un «graf» que pot tenir bucles i arestes múltiples.

Les arestes múltiples són útils, per exemple, en la consideració de xarxes elèctriques, des d'un punt de vista de teoria de grafs.

Un graf pla roman pla si és afegida una aresta entre dos vèrtexs ja units per una aresta; per tant, l'agregació d'arestes múltiples preserva la planaritat.

Bibliografia

• Balakrishnan, V. K.. Graph Theory (en anglès). 1. McGraw-Hill, 1r de febrer de 1997. ISBN 0-07-005489-4. 
• Bollobas, Bela. Modern Graph Theory (en anglès). 1. Springer, 12 d'agost de 2002. ISBN 0-387-98488-7. 
• Diestel, Reinhard. Graph Theory (en anglès). 2. Springer, 18 de febrer de 2000. ISBN 0-387-98976-5. 
• Gross, Jonathon L.; Yellen, Jay. Graph Theory and Its Applications (en anglès). CRC Press, 30 de desembre de 1998. ISBN 0-8493-3982-0. 
• Gross, Jonathon L.; Yellen, Jay. Handbook of Graph Theory (en anglès). CRC Press, 29 de desembre de 2003. ISBN 1-58488-090-2. 
• Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae (en anglès). 31. Chapman & Hall/CRC, 27 de novembre de 2002. ISBN 1-58488-291-3. 

Vegeu també

• Multigraf