Hypergraph y su representación | Matemáticas discretas

Introducción:
un hipergráfico es un gráfico en el que los hiperbordes (bordes generalizados) pueden conectarse a un subconjunto de vértices/Nodes en lugar de dos vértices/Nodes.
Los bordes (también conocidos como hiperbordes) de una hipergrafía son conjuntos arbitrarios de vértices no vacíos. Un k-hipérgrafo tiene todos esos hiperbordes que conectan exactamente k vértices; un gráfico normal es, por lo tanto, un hipergráfico de 2 (ya que un borde conecta 2 vértices).

Representación de hipergrafía:
una hipergrafía no dirigida H se define como un par H = (V,E), donde V es un conjunto de elementos conocidos como Nodes o vértices, y E es un conjunto de subconjuntos no vacíos de V, conocidos como hiperaristas o bordes (en una hipergrafía no dirigida).
Aquí, E es un subconjunto de P(X), donde P(X) es el conjunto potencia de X.
Cada hiperarista se puede representar como una curva cerrada que contiene sus miembros para crear hipergrafías. 
Ejemplo –

H(V) = { A, B, C, D, E}
H(E) = {e1, e2, e3 } = { {A, D}, {D, E}, {A, B, C} }

Orden y tamaño de la hipergrafía:
el orden de la hipergrafía = el tamaño del conjunto de vértices y
el tamaño de la hipergrafía = el tamaño del conjunto de aristas.

Order(H) = |H(V)|
Size(H)= |H(E)|

La hipergrafía anterior tiene –
Orden(H) = |H(V)| = 5
Tamaño(H)= |H(E)| = 3

Hipergrafía a gráfica bipartita:
debido a que siempre es posible (aunque no siempre conveniente) expresar una hipergrafía mediante una gráfica bipartita, las hipergrafías rara vez se utilizan. El conjunto de vértices en un gráfico bipartito se puede dividir en dos subconjuntos, P y Q, con cada borde conectando un vértice en P con un vértice en Q.
Simplemente representamos los vértices de H como vértices en Q y los hiperbordes de H como vértices en P, e inserte una arista (p, q) siempre que s sea miembro de la hiperarista t en H.
 

Una hipergrafía se representa de dos maneras. Cinco vértices a la izquierda están conectados por tres hiperbordes. A la derecha, los mismos cinco vértices se unen a nuevos vértices (tres) que representan las hiperaristas por aristas ordinarias.

Propiedades de la hipergrafía:
una hipergrafía puede tener una serie de propiedades diferentes, que incluyen:

• Hipergrafía vacía : 
  no hay bordes en la hipergrafía vacía. Como puede ver, la figura de abajo no tiene aristas sino 5 vértices nombrados: AB, C, D, E
   

• d – Regular – 
  Cada vértice tiene un grado de d, lo que implica que está contenido precisamente en d hiperaristas.
  Ejemplo: A continuación, la hipergrafía es 2-regular porque todos los vértices (A, B y C) tienen el mismo grado: 2

• 2-colorable : 
  sus vértices se pueden dividir en dos clases, P y Q, de modo que cada hiperarista con una cardinalidad de al menos 2 tenga al menos un vértice de cada clase.
• No simple : 
  tiene bucles (hiperaristas con un solo vértice) o aristas repetidas (dos o más aristas con el mismo conjunto de vértices)
  Ejemplo: 
  en el gráfico a continuación, podemos ver 2 bucles: e1 y e2e, por lo que es un no – Hipergrafía simple.

• Simple: 
  no hay bucles ni bordes repetidos en este diseño.
• k -uniforme : 
  cada hiperarista se compone exactamente de k vértices.
  Ejemplo: 
  en el siguiente hipergráfico podemos ver que cada hiperarista (e1, e2, e3, e4) consta de 2 vértices, por lo tanto, es un hipergráfico de 2 uniformes.

• k -partite – 
  Cada hiperarista comprende exactamente un vértice de cada tipo, y los vértices se dividen en k partes.
  Ejemplo: 
  en el hipergráfico a continuación, digamos, los vértices se dividen en 3 partes: m (A, D), (B, E) y (D, F) . Tenga en cuenta que cada hiperborde contiene solo un vértice de cada partición.