Multigrafo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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 los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multigrafo G es un par G:=(V, E) donde:

  • V es un conjunto de vértices o nodos
  • E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

Ejemplo. Los multigrafos podrían usarse, por ejemplo, para modelar las posibles conexiones de vuelo ofrecidas por una aerolínea. Para este caso tendríamos un grafo dirigido, donde cada nodo es una localidad y donde pares de aristas paralelas conectan estas localidades, según un vuelo es hacia o desde una localidad a la otra.

Algunos autores permiten que los multigrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo.[1]

Un multidigrafo es un grafo dirigido que está facultado para tener aristas múltiples, es decir, aristas con los mismos nodos iniciales y finales. Formalmente, un multidigrafo G es un par G:=(V,A) donde:

  • V es un conjunto de vértices o nodos
  • A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.

Un multidigrafo mixto G:=(V,E,A) puede definirse de la misma manera que un grafo mixto, es decir, con la capacidad de poseer al mismo tiempo aristas dirigidas (A) y no dirigidas (E).

Etiquetado[editar]

Los multigrafos y multidigrafos pueden etiquetarse de manera análoga a un grafo tradicional. Sin embargo, sólo existe consenso con respecto a la terminología para los multidigrafos.

Un multidigrafo etiquetado G es un grafo etiquetado con arcos etiquetados. Formalmente, es una 8-tupla G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A) donde:

  • V es un conjunto de nodos y A un multiconjunto de arcos.
  • \Sigma_V y \Sigma_A son alfabetos finitos para las etiquetas de nodos y arcos.
  • s\colon A\rightarrow\ V y t\colon A\rightarrow\ V son dos funciones que indican la fuente y objetivo de los nodos de un arco.
  • \ell_V\colon V\rightarrow\Sigma_V y \ell_A\colon A\rightarrow\Sigma_A son dos funciones que asocian cada nodo y arco con una etiqueta.

Notas[editar]

  1. Por ejemplo, ver, Bollobas, p. 7 y Diestel, p. 25.

Referencias[editar]

  • Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
  • Bollobas, Bela; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
  • Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
  • Gross, Jonathan L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
  • Gross, Jonathan L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
  • Harary, Frank; Graph Theory, Addison Wesley Publishing Company (January 1995). ISBN 0-201-41033-8.
  • Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.
  • Svante Janson, Donald E. Knuth, Tomasz Luczak, and Boris Pittel; The Birth of the Giant Component, Random Structures Algorithms 4 (1993), no. 3, 231-358.