Aristas múltiples

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

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.

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; 1ra edición (1 de febrero, 1997). ISBN 0-07-005489-4.
  • Bollobas, Bela; Modern Graph Theory, Springer; 1ra edición (12 de agosto, 2002). ISBN 0-387-98488-7.
  • Diestel, Reinhard; Graph Theory, Springer; 2da edición (18 de febrero, 2000). ISBN 0-387-98976-5.
  • Gross, Jonathon L, y Yellen, Jay; Graph Theory and Its Applications, CRC Press (30 de diciembre, 1998). ISBN 0-8493-3982-0.
  • Gross, Jonathon L, y Yellen, Jay; (eds); Handbook of Graph Theory. CRC (29 de diciembre, 2003). ISBN 1-58488-090-2.
  • Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31a edición (27 de noviembre, 2002). ISBN 1-58488-291-3.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Multigrafo — Un multigrafo con múltiples aristas (en rojo) y tres bucles (en azul). No todos los autores permiten multigrafos con bucles. Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan …   Wikipedia Español

  • Grafo dual — El grafo G es dual del G , y viceversa. En teoría de grafos, un grafo dual G de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas. Contenido …   Wikipedia Español

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Bifaz — Saltar a navegación, búsqueda Primer bifaz publicado en la historia de la Arqueolog …   Wikipedia Español

  • Luis Aguilar Monsalve — Saltar a navegación, búsqueda Luis Aguilar Monsalve (1938) es un escritor ecuatoriano que radica en Indiana y es profesor asociado en la universidad Hanover College. Su incursión en la literatura empieza cuando estudiaba en Colegio La Salle,… …   Wikipedia Español

  • Tetraedro — regular Familia: Sólidos platónicos Imágen del sólido Caras 4 …   Wikipedia Español

  • Árbol de expansión — Un árbol de expansión (aristas azules gruesas) de un grafo de rejilla. En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas)… …   Wikipedia Español

  • Poaceae —   Poáceas …   Wikipedia Español

  • Poliedro dual — Saltar a navegación, búsqueda El octaedro y el cubo son poliedros duales. Poliedro dual o conjugado, en geometría, es el poliedro cuyos vértices se corresponden con el centro de las cara del otro poliedro dado. El poliedro dual del dual es… …   Wikipedia Español

  • Oxoanión — Un oxoanión es una especie química cuya fórmula genérica es AxOyz− (donde A representa un elemento químico, generalmente un no metal, y O representa un átomo de oxígeno). Los oxoaniones se forman con una gran diversidad de elementos químicos.[1]… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”