Diferencia entre revisiones de «Hipergrafo»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 1:
[[Archivo:Hypergraph-wikipedia.svg|thumb|Ejemplo de hipergrafo de vértices ''v''<sub>1</sub>, ''v''<sub>2</sub>, ''v''<sub>3</sub>, ''v''<sub>4</sub>, ''v''<sub>5</sub>, ''v''<sub>6</sub> y ''v''<sub>7</sub>, con hiperaristas ''e''<sub>1</sub>, ''e''<sub>2</sub>, ''e''<sub>3</sub> y ''e''<sub>4</sub>. Es propio, tiene dominio parcial, su cardinalidad es 4 y su tamaño 28.]]
En [[matemáticas]] y [[ciencias de la computación]], un '''hipergrafo''' es una generalización de un [[grafo]], cuyas [[arista (teoría de grafos)|aristas]] aquí se llaman [[hiperarista]]s, y pueden relacionar a cualquier cantidad de [[vértice (teoría de grafos)|vértices]], en lugar de solo un máximo de dos como en el caso de los grafos. Así, un grafo es una clase particular de hipergrafos, en que cada hiperarista tiene a lo más dos vértices.<ref name=WF13.c4/>
== Definición formal ==
Línea 15:
* Un hipergrafo es '''propio''', si no es vacío ni contiene la hiperarista vacía.
* Un hipergrafo tiene '''dominio total''' si la unión de las hiperaristas es igual al conjunto ''A''; de lo contrario, se dice que tiene '''dominio parcial'''.
=== Dualidad de hipergrafos ===
Dado un hipergrafo <math>H=(A,E)</math>, se puede definir su '''hipergrafo dual''' <math>H^*=(E,A)</math> invirtiendo los roles de los vértices y las hiperaristas.<ref name=WF13.c4/>
== Aplicaciones ==
| |||