Arestes múltiples

Erro al crear miniatura:

Quan un grafo admet arestes múltiples, es diu multigrafo.

En teoria de grafos, les arestes múltiples (també cridades arestes paraleles o una multi-aresta), són dos o més arestes que són incidents (és dir, que conecten) a a lo manco dos vèrtiços. Els grafos sense arestes múltiples són cridats grafos simples.

Depenent del context, un grafo pot definir-se de manera que permeta o no la presència d'arestes múltiples (de la mateixa manera que a voltes es permet i a voltes no la presència de bucles):

• En un context en que es permeten la presència d'arestes múltiples i bucles, un grafo sense bucles és usualment cridat multigrafo.
• En un context en que no es permeten arestes múltiples i bucles, un multigrafo o pseudografo és definit per a referir-se a un "grafo" que pot tindre bucles i arestes múltiples.

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

Un grafo planar permaneix planar si és afegida una aresta entre dos vèrtiços ya units per una aresta; per lo tant, l'agregació d'arestes múltiples preserva la planaridad.

Referències

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