Edición de «Multigrafo»

[[Archivo:Multiple edges.png|miniaturadeimagen|Multigrafo con dos vértices y dos aristas.]]
[[Archivo:Multi-pseudograph.svg|thumb|right|Un multigrafo con [[aristas múltiples]] (en rojo) y tres [[Bucle (teoría de grafos)|bucles]] (en azul). No todos los autores permiten multigrafos con bucles.]]
En [[teoría de grafos]], un '''multigrafo''' o '''grafo multivariado''' es una generalización de un [[grafo]] que permite [[aristas múltiples]], o equivalentemente, más de un conjunto de aristas. De esta forma, dos nodos pueden estar conectados por más de una arista.<ref name=WF13.c4>{{harvsp|Wasserman|Faust|2013|loc=«Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.}}</ref> Algunos autores permiten que los multigrafos tengan [[bucle (teoría de grafos)|bucles]], es decir, que una arista conecte a un nodo consigo mismo.{{Harvnp|Bollobas|2002|p=7}}{{Harvnp|Diestel|2000|p=25}} Un '''pseudografo''' se puede definir como un sinónimo de multigrafo, aunque en ocasiones también se utiliza para distinguir a los multigrafos en general, de aquellos que permiten bucles.<ref>{{cita web |autor=Pogliani, L. |año=2000 |título=From molecular connectivity indices to semiempirical connectivity terms: Recent trends in graph theoretical descriptors |publicación=Chemical Reviews |volumen=100 |número=10 |páginas=3827-3858 |doi=10.1021/cr0004456}}</ref> Si se consideran [[grafo dirigido|aristas dirigidas]], al multigrafo también se le conoce como '''multigrafo dirigido''' o '''multidigrafo'''. También se puede hablar de '''grafo complejo''' en oposición a un [[grafo|grafo simple]] (esto es, un grafo sin bucles ni aristas múltiples), como un grafo que posee bucles y/o al menos un par de vértices con más de una arista.<ref name=WF13.c4/>

== Definición formal ==
Formalmente, un '''multigrafo''' <math>G</math> es un [[par ordenado]] <math>G=(V,E)</math> donde:
*<math>V</math> es un [[conjunto]] de [[vértice (teoría de grafos)|vértices]] o nodos;
*<math>E</math> es un [[multiconjunto]] ([[conjunto finito|finito]]) de [[arista (teoría de grafos)|aristas]] o líneas, o alternativamente, una [[familia de conjuntos]] de aristas.<ref name=WF13.c4/>

Un '''multidigrafo''' se define de manera análoga, pero con <math>E</math> considerando [[grafo dirigido|aristas dirigidas]]. Si <math>E</math> admite aristas dirigidas y [[grafo no dirigido|no dirigidas]], entonces se habla de '''multidigrafo mixto'''.

== Etiquetado ==

Los multigrafos y multidigrafos pueden [[Grafo etiquetado|etiquetarse]] de manera análoga a un grafo tradicional. Sin embargo, solo 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]] <math>G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A)</math> donde:

* V es un conjunto de nodos y A un multiconjunto de arcos.
* <math>\Sigma_V</math> y <math>\Sigma_A</math> son alfabetos finitos para las etiquetas de nodos y arcos.
* <math>s\colon A\rightarrow\ V</math> y <math>t\colon A\rightarrow\ V</math> son dos [[Función matemática|funciones]] que indican la ''fuente'' y ''objetivo'' de los nodos de un arco.
* <math>\ell_V\colon V\rightarrow\Sigma_V</math> y <math>\ell_A\colon A\rightarrow\Sigma_A</math> son dos [[función matemática|funciones]] que asocian cada nodo y arco con una etiqueta.

== Aplicaciones ==
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.

== Véase también ==

* [[Grafo]]
* [[Teoría de grafos]]
* [[Red]]

== Notas==
{{listaref}}

==Referencias==
* {{cita libro |apellido=Bollobas |nombre=B. |año=2002 |título=Modern Graph Theory |editorial=Springer |edición=I |isbn=0-387-98488-7}}
* {{cita libro |apellido=Diestel |nombre=R. |año=2000 |título=Graph Theory |editorial=Springer |edición=II |isbn=0-387-98976-5}}
* {{cita libro |apellido1=Wasserman |nombre1=Stanley |apellido2=Faust |nombre2=Katherine |título=Análisis de redes sociales: Métodos y aplicaciones |editorial=Centro de Investigaciones Sociológicas |ubicación=Madrid |año=2013 |año-original=1994 |oclc=871814053 |isbn=978-84-7476-631-8}}
[[Categoría:Extensiones y generalizaciones de grafos]]