Análisis de grafos con relaciones de orden superior

Arancha Illán Toledano^1*

¹Grado en Matemáticas, Universidad Rey Juan Carlos (Madrid, España)

^*Autor de correspondencia: a.illan.2018@alumnos.urjc.es

Resumen
En este artículo se presenta “Análisis de grafos con relaciones de orden superior” [1], un Trabajo Fin de Grado dirigido por los profesores Miguel Romance del Río y Eva Primo Tárraga en el Grado de Matemáticas. Este trabajo fue planteado de tal forma que, quien lo desee, pueda informarse acerca de la Teoría de Hipergrafos o bien realizar una continuación de la misma en forma de otro TFG. Al final del mismo, se muestran algunas de las posibles temáticas sobre las que puede versar. De la extensa teoría, se seleccionaron cuatro áreas a tratar, las cuales quedan reflejadas en las siguientes secciones:

◾ La Sección 1 tiene como objetivo principal introducir al lector a la Teoría de Hipergrafos. Se presentan las primeras definiciones (algunas como extensión de sus homólogas para grafos y otras propias de hipergrafos) y algunos de los resultados más interesantes.

◾ La Sección 2 se centra en aplicar la técnica de Coloreabilidad a los hipergrafos. Además, se introduce concepto de Hipergrafo Mixto para aplicar y conocer en detalle algunas propiedades de la Coloreabilidad.

◾ La Sección 3 trata de generalizar el concepto de grafo dirigido hacia el concepto de hipergrafo dirigido. Habla acerca de sus propiedades, destacando entre ellas las propiedades eulerianas.

◾ Por último, en la Sección 4, se presentan algunas de las numerosas aplicaciones que desempeñan los hipergrafos, algunas basadas en las propias características de los hipergrafos y, otras, en su concepto.

El contenido de estas secciones fue principalmente extraído de las referencias [2, 3].

Palabras clave
hipergrafo, coloreabilidad, hipergrafo dirigido, aplicaciones

Este trabajo se ha llevado a cabo bajo la supervisión de los Profesores E. Primo Tárraga y M. Romance del Río (Tutores del TFG, URJC).

Introducción

La Teoría de Grafos ha demostrado, a lo largo de su extensa trayectoria, la utilidad que puede llegar a brindar en numerosos campos de la ciencia, así como la aplicabilidad de sus objetos a la hora de resolver problemas en la vida real. No obstante, las relaciones binarias que bien caracterizan a los grafos no son, en diversas ocasiones, la forma más precisa de representar otros tantos escenarios, como se muestra en este artículo. Se entra, entonces, en la necesidad de expandir los límites, ir un poco más allá y preguntarse qué posibilidades se presentarían si se trabajase con relaciones de mayor cardinalidad. Entonces, progresivamente, los esfuerzos de diversos investigadores comenzaron a encauzarse hacia un campo de estudio más complejo, donde se trabajara con sistemas de conjuntos. No fue hasta el siglo XX (más concretamente, en los años 60) que surge, a manos del matemático Claude Berge, el concepto de Hipergrafo para referirse a estos sistemas de conjuntos y, con él, una prometedora teoría (extensión, en gran parte, de los resultados en Teoría de Grafos) que ha sido objeto de gran atracción para investigadores, la Teoría de Hipergrafos. [4].

1. El lenguaje de los Hipergrafos

Comencemos dando la definición básica del objeto de trabajo del TFG:

Definición 1.1 Sea X = {x₁, x₂, ..., x_n} un conjunto finito de vértices y E = {e₁, e₂, ..., e_m} una familia de subconjuntos de X, denominados hiperaristas. El par H = (X, E) se conoce como hipergrafo no dirigido.

A partir de este concepto podemos presesntar algunas de las principales características de los hipergrafos, que bien pueden ser homólogas a aquellas en grafos, como son el orden y el tamaño de un hipergrafo, el grado de un vértice (g(x)) o una hiperarista (g(e)), o el significado de hipergrafo simple e hipergrafo lineal; o bien exclusivas de la Teoría de Hipergrafos, como la que sigue:

Definición 1.2 Si g(x) = k ∀x ∈ X, k ∈ ℕ, entonces H es k–regular. Si g(e) = r ∀e ∈ E, r ≥ 0, entonces H es r–uniforme.

Cuando el número de vértices y el número de relaciones entre los vértices de un hipergrafo comienza a ser significativamente grande, los hipergrafos resultan visualmente complicados de entender. Es por ello conveniente introducir representaciones algebraicas de los hipergrafos que faciliten su comprensión. Existen, además, representaciones de un hipergrafo en forma de otro hipergrafo e, incluso, en forma de grafo.

Definimos, en primer lugar, la matriz de adyacencia, la matriz de incidencia y la representación bipartita de un hipergrafo (análogas a la matriz de adyacencia, la matriz de incidencia y la representación bipartita de un grafo) para después dar la demostración del siguiente resultado:

Proposición 1.1 En un hipergrafo H = (X, E), la suma de los grados de los vértices es igual a la suma de las cardinalidades de las hiperaristas, es decir

$\sum_{i = 1}^{n} g (x_{i}) = \sum_{j = 1}^{m} g (e_{j})$

Posteriormente, presentamos el concepto de dualidad de un hipergrafo:

Definición 1.3 Sea H = (X, E) un hipergrafo sin vértices aislados. Su hipergrafo dual, H^∗ = (X^∗ , E^∗), viene definido por:

◾ $X^{*} = {e_{1}^{*}, e_{2}^{*}, \dots, e_{m}^{*}} .$

◾ $E^{*} = {X_{1}^{*}, X_{2}^{*}, \dots, X_{n}^{*}}$ donde $X_{j}^{*} = {e_{i}^{*} : x_{j} ∊ e_{i}}, \forall j ∊ {1, 2, \dots, n}, \forall i ∊ {1, 2, \dots, m} .$

En la Figura 2 podemos observar a la izquierda un hipergrafo y a la derecha su hipergrafo dual correspondiente:

La dualidad de un hipergrafo es una característica singular que consiste, a grandes rasgos, en intercambiar los papeles de vértices por los de hiperaristas y viceversa. Dicho en otras palabras, observamos el mismo problema desde puntos de vista opuestos.

El uso de operaciones básicas como el borrado de vértices o hiperaristas es una técnica muy común para la obtención de nuevas subestructuras. Las primeras subestructuras consideradas son aquellas obtenidas mediante el borrado tanto de vértices como de hiperaristas y son homólogas a aquellas para grafos.

Definición 1.4 Se dice que H′ = (X′, E′) es un subhipergrafo inducido (por X’) de H si cumple X′ ⊆ X y E′ está formado por las hiperaristas de H que quedan completamente contenidas en X′. Dicho de otra forma:

E′ = {e_i ∩ X′ : e_i ∈ E y e_i es bucle o |e_i ∩ X′| ≥ 2}.

Definición 1.5 Se dice que H′ = (X′, E′) es un subhipergrafo parcial de H si cumple X′ = X y E′ ⊆ E.

Posteriormente, vemos algunas de las subestructuras que nacen de tomar subconjuntos del conjunto de vértices o del conjunto de hiperaristas. Suponemos que los hipergrafos originales no tienen vértices aislados:

Definición 1.6 Se denomina a S ⊆ X conjunto estable (resp. fuertemente estable) si e ⊈ S (resp. |S ∩ e| ≤ 1), ∀e ∈ E. La cardinalidad máxima de un conjunto estable (resp. fuertemente estable) es α(H) (resp. α̅ (H)), también denominado número de la estabilidad.

Definición 1.7 Un conjunto T ⊆ X es un transversal si T ∩e ≠ ∅, ∀e ∈ E. El número transversal, o la cardinalidad mínima de un transversal, se denota como τ(H).

Estos conceptos tienen potenciales aplicaciones en el área de optimización, como se muestra en la Sección 4.

Además de lo anterior, son destacables las definiciones de emparejamiento y emparejamiento máximo de un hipergrafo junto con las de recubrimiento y recubrimiento mínimo de un hipergrafo. Tras denotar el cardinal del emparejamiento máximo de un hipergrafo como ν(H) y el cardinal del recubrimiento mínimo de un hipergrafo como ρ(H), demostramos los siguientes resultados:

Proposición 1.2 Si H es un hipergrafo no dirigido, entonces ν(H) ≤ τ(H).

Proposición 1.3 Si H es un hipergrafo no dirigido, entonces ρ(H) = τ(H^∗).

A continuación mostramos algunas de las características más relevantes de los hipergrafos, como la Propiedad de König y la Propiedad de König Dual, así como el modelaje de hipergrafos como grafos. Destacamos la siguiente propiedad, de relevancia en la resolución de problemas de optimización:

Definición 1.8 Se dice que un hipergrafo H = (X, E = (e_j)j∈J) satisface la propiedad de Helly si se cumple la siguiente afirmación: para cada subfamilia de hiperaristas, si cada pareja de hiperaristas tienen intersección no vacía, entonces toda la subfamilia intersección no vacía.

Escrito de otra forma: sea A ⊂ J un subconjunto del conjunto de índices, si se cumple que

$(\forall B \subset A, | B | \leq 2) \underset{b ∊ B}{\cap} e_{b} \neq \emptyset entonces se tiene que \underset{a ∊ A}{\cap} e_{a} \neq \emptyset .$

Para saber si un hipergrafo satisface la propiedad de Helly, podemos hacer uso de la caracterización de Gilmore [5] que dice así:

Teorema 1.1 (GILMORE.) Sea H = (X, E) un hipergrafo. Se dice que H satisface la propiedad de Helly si y solo si para cualesquiera tres vértices x, y, z ∈ X la familia de hiperaristas que contengan al menos dos de estos vértices tiene intersección no vacía. Escrito de otra forma

$H es Helly ⟺ \forall C \subset X tal que | C | = 3 se tiene que \underset{| e_{j} \cap C | \geq 2}{\cap} e_{j} \neq \emptyset .$

Existen dos formas de modelar un hipergrafo como un grafo, tal y como vamos a continuación:

Definición 1.9 Sea H = (X, E) un hipergrafo. El grafo línea de H, es aquel grafo que se define como L(H) = (E′, A) tal que:

◾ E′ = E, es decir, el conjunto de vértices de V se corresponde con el conjunto de las hiperaristas de H.

◾ ${e_{i}^{'}, e_{j}^{'}} \in A ⟺ e_{i} \cap e_{j} \neq Ø$ , es decir, dos vértices son adyacentes en L(H) si, en H las hiperaristas respectivas intersecan.

Definición 1.10 Sea H = (X, E) un hipergrafo. El grafo de Gaifman de H, [H]₂, también llamado 2–sección de H, es aquel que comparte los mismos vértices que H y cuya familia de aristas viene dada por:

A = {a = {x_i, x_j} : x_i, x_j ∈ e, e ∈ E}.

Es decir, el grafo une todos los pares de vértices que se encuentren dentro de una misma hiperarista.

2. Coloreabilidad

Hacer particiones sobre un conjunto de objetos conforme a una serie de reglas es un proceso fundamental en matemáticas, del cual la coloreabilidad de hipergrafos (cuyos conceptos se expanden de la coloreabilidad de grafos) responde. En esta sección haremos un breve resumen de los conceptos y resultados que presenta el Capítulo 2 del TFG [1] donde, adicionalmente, se ha estudiado la coloreabilidad de un nuevo tipo de hipergrafo denominado Hipergrafo Mixto.

Comenzamos dando la definición de coloreabilidad para hipergrafos:

Definición 2.1 Sea H = (X, E) un hipergrafo sin bucles ni vértices aislados y {1, 2, . . . , k} un conjunto de k colores. Un k–coloreado de H es un etiquetado de sus vértices con colores de {1, 2, . . . , k} de tal forma que:

i) Cada vértice tiene asignado un único color.

ii) ∀e ∈ E, si |e| ≥ 2, e no es monocromático, es decir, tiene al menos dos vértices de distinto color.

El coloreado, como puede intuirse, induce a una partición en k clases del conjunto de vértices X, S₁ , S₂, . . . , S_k , tal que cada S_icontiene a los vértices coloreados con el color i ∈ {1, 2, . . . , k}. Por lo tanto

$X = \cup_{i = 1}^{k} S_{i} donde S_{i} \cap S_{j} = \emptyset si i \neq j .$

El número cromático es el k mínimo necesario para poder hacer un k–coloreado sobre un hipergrafo H. Se denota como χ(H).

A continuación, presentamos los siguientes resultados que relacionan el número cromático con el número de la estabilidad y el número transversal, cuya demostración queda reflejada en el TFG:

Proposición 2.1 Sea H = (X, E) un hipergrafo con |X| = n y número de estabilidad α(H). Entonces se cumple la siguiente desigualdad: χ(H) · α(H) ≥ n.

Proposición 2.2 Sea H = (X, E) un hipergrafo con |X| = n, número de estabilidad α(H) y número transversal τ(H). Entonces se cumple la siguiente desigualdad: χ(H) ≤ n − α(H) + 1.

A lo largo de las siguientes páginas, mostramos distintos tipos de coloreados de los vértices de un hipergrafo: el k–coloreado fuerte, el k–coloreado equitativo, el k–coloreado correcto y el k–coloreado uniforme. Además, también existen formas de colorear las hiperaristas:

Definición 2.2 Sea H = (X, E). Un k–coloreado de hiperaristas de H es un coloreado de hiperaristas de H tal que se cumple:

i) cada hiperarista tiene asignado un único color.

ii) se usan k colores para colorear las hiperaristas.

iii) dos hiperaristas que intersecan tienen colores distintos.

3. Hipergrafos dirigidos

Al igual que hemos presentado el concepto de hipergrafo como generalización de grafo, daremos a conocer el concepto de hipergrafo dirigido como la generalización de grafo dirigido. Se trata de una rama de los hipergrafos con poco camino recorrido hasta la actualidad y varios campos de investigación abiertos, como la lingüística computacional o el trabajo con bases de datos relacionales, entre otros.

Definición 3.1 Sea X = {x₁, x₂, . . . , x_n} un conjunto finito de vértices y $\vec{E} = {\vec{e_{1}}, \vec{e_{2}}, \dots, \vec{e_{m}}}$ el conjunto de hiperaristas dirigidas, también denominadas hiperarcos. El par ordenado $\vec{H} = (X, \vec{E})$ es conocido como hipergrafo dirigido. A su vez, cada hiperarco es el par ordenado

$\vec{e_{i}} = (e_{i}^{-}, e_{i}^{+})$

donde $e_{i}^{-} y e_{i}^{+}$ son conocidas, respectivamente, como cabeza y cola de $\vec{e_{i}}$ . La cabeza y la cola cumplen que $e_{i}^{-}, e_{i}^{+} \subseteq X$ $y e_{i}^{-} \cap e_{i}^{+} = Ø con e_{i}^{-} \neq y e_{i}^{+} \neq Ø$ . Denotaremos al conjunto de vértices de $\vec{e_{i}}$ por $e_{i} = e_{i}^{-} ⋃ e_{i}^{+}$ .

Al igual que sucedía en la Sección 1, se pueden definir los conceptos de hipergrafo simple e hipergrafo lineal de forma similar.

De igual forma, se muestran las principales representaciones de los hipergrafos tanto como matrices como en forma de grafos. A continuación algunos ejemplos:

Definición 3.2 Un grafo dirigido FD de un hipergrafo dirigido $\overset{⟶}{H}$ es el grafo $F D (H) = (Y, \overset{⟶}{F})$ que cumple:

◾ $Y = X ⊔ \overset{⟶}{E}$ , donde $⊔$ denota la unión disjunta,

◾ $\overset{⟶}{F} = {(x, \overset{⟶}{e_{i}}) : x ⟶ e_{i}^{-}} \cup {(\overset{⟶}{e_{j}}, y) : y ⟶ e_{j}^{+}} .$

Definición 3.3 Sea $\overset{⟶}{H} = (X, \overset{⟶}{E})$ un hipergrafo dirigido. El grafo de Gaifman de $\overset{⟶}{H}, [\overset{⟶}{H}]_{2} = (Y, \overset{⟶}{F})$ , viene dado por

◾ Y = X,

◾ $\overset{⟶}{F} = {(x, y) : x ∊ e^{-}, y ∊ e^{+}, \overset{⟶}{e} = (e^{-}, e^{+}) \cup \overset{⟶}{E}} .$

Además, también destacamos la dualidad de los hipergrafos dirigidos:

Definición 3.4 El hipergrafo dirigido dual de $\overset{⟶}{H} = (X, \overset{⟶}{E})$ viene definido por

$\overset{⟶}{H^{*}} = (\overset{⟶}{E}, ({\overset{⟶}{H}}^{-} (x), {\overset{⟶}{H}}^{+} (x)), \forall x ∊ X .$

donde

${\overset{⟶}{H}}^{-} (x) = {\overset{⟶}{e} ∊ \overset{⟶}{E} : x ∊ e^{-}} y {\overset{⟶}{H}}^{+} (x) = {\overset{⟶}{e} ∊ \overset{⟶}{E} : x ∊ e^{+}} .$

Tras conocer la noción de hipergrafo dirigido, estudiamos de qué manera se puede extender el concepto de grafo dirigido euleriano a este contexto. Para ello, en el TFG se dedican unas páginas a dar las ideas principales de la demostración del siguiente resultado:

Proposición 3.1 Sea $\overset{⟶}{H} = (X, \overset{⟶}{E})$ un hipergrafo dirigido y $L (\overset{⟶}{H})$ su grafo línea dirigido. Entonces $\overset{⟶}{H}$ es euleriano si y solo si $L (\overset{⟶}{H})$ es hamiltoniano.

Fueron previamente necesarias las definiciones de hiperciclo euleriano, grafo dirigido hamiltoniano y contracción del arco de un grafo.

4. Aplicaciones

Desde hace pocos años, la Teoría de Hipergrafos, al igual que las teorías más fructuosas de las matemáticas, ha demostrado ser de gran utilidad y tener numerosas aplicaciones, que varían desde las ciencias aplicadas hasta las actividades cotidianas. Algunas de las más destacadas son aquellas aplicadas para resolver problemas de optimización, modelizar distintos escenarios y hacer análisis sobre redes complejas. De igual forma, resultan también de provecho sus propiedades.

Los hipergrafos dirigidos también dotan de herramientas para la resolución de problemas, como pueden ser los problemas de flujo a coste mínimo, de aprendizaje automático, recuperación de imágenes, etc. No obstante, debido a su dificultad, en esta sección veremos exclusivamente algunos ejemplos de casos de hipergrafos no dirigidos.

A continuación mostraremos dos de los ejemplos dispuestos en el trabajo, el primero del área de optimización y el segundo de análisis de redes, donde la modelización con hipergrafos juega un papel fundamental.

4.1 Contratación de supervisores.

En la empresa X buscan contratar supervisores para controlar sus distintas áreas de trabajo: dirección (a₁), recursos humanos (a₂), producción (a₃), ventas (a₄), finanzas (a₅), marketing (a₆), informática (a₇) y formación (a₈). A los puestos se presentan los siguientes solicitantes (s_i), cada una con experiencias en:

s₁: formación e informática

s₂: producción e informática

s₃: recursos humanos

s₄: dirección

s₅: producción, ventas y finanzas

s₆: producción y ventas

s₇: finanzas

s₈: marketing,

s₉ : dirección y recursos humanos

s₁₀ : informática

s₁₁ : ventas y marketing

s₁₂ : dirección y formación

s₁₃ : recursos humanos e informática

Idealmente, se quiere contratar al mínimo de supervisores posibles de tal manera que tengan cubiertas el máximo número de áreas de la empresa cada uno, conforme a las aptitudes que poseen.

El hipergrafo que modela este escenario cuenta con un vértice por cada solicitante y una hiperarista por cada área de la empresa. Su representación queda reflejada en la Figura 5.

Para obtener la solución deseada, hemos de encontrar el conjunto mínimo transversal que, recordemos, era el conjunto más pequeño cuyos elementos (vértices) intersecaban con todas las hiperaristas. En analogía con este caso, estaríamos buscando al mínimo grupo de personas (vértices) cuyas aptitudes sirvan para cubrir todas las áreas (hiperaristas).

Al ser un ejemplo con pocos vértices y pocas hiperaristas, podemos ver sin dificultad que un ejemplo de mínimo transversal es:

s₈ (cubriendo a₆), s₅ (cubriendo a₅, a₄, a₃), s₁ (cubriendo a₈, a₇) y s₉ (cubriendo a₂, a₁).

4.2 Número de Ërdos y Número de Bacon.

Paul Erdös fue un conocido matemático cuyas participaciones destacaron en los campos de la teoría combinatoria, la teoría de grafos y la teoría de números entre muchos otros. Entre sus numerosas aportaciones, se encuentra el concepto que tratamos en este apartado, el Número de Erdös [6]. Este término describe la “distancia de colaboración” que existe entre cualquier autor de un artículo matemático y Paul Erdös, medida en función de las co-autorías, esto es:

◾ Paul Erdös tiene Número de Erdös 0,

◾ un autor que publique un artículo matemático en co-autoría con Paul Erdös tiene Número de Erdös 1,

◾ un autor que publique un artículo matemático con un autor que ha colaborado directamente con Paul Erdös tiene Número de Erdös 2,

◾ etc.

El hipergrafo que modela este caso está formado por los vértices representando los autores y las hiperaristas representando a los artículos publicados, de tal forma que cada artículo conforma al conjunto de autores que participaron en él. El Número de Erdös de un autor consistiría en calcular la distancia entre el vértice. Tradicionalmente, la herramienta utilizada era el grafo, más concretamente, el grafo de Gaifman del hipergrafo que acabamos de describir.

En el contexto cinematográfico existe el término análogo al Número de Erdös, denominado el Número de Bacon [7], creado también por matemáticos, que describe la “distancia” entre actores de películas con Kevin Bacon, actor de cine, teatro y televisión estadounidense.

El hipergrafo que describe esta situación es aquel cuyos vértices representan a los actores y cuyas hiperaristas representan a las películas, de manera que cada película conforma al conjunto de actores que actúan en ella. Nuevamente, se suele usar la representación del grafo de Gaifman.

4.3 Otras aplicaciones.

Como bien se mencionó al inicio de la sección, las aplicaciones de los hipergrafos son cada vez más numerosas y notorias. Aunque en estas páginas hemos puesto varios ejemplos en práctica, a continuación enumeramos algunos casos interesantes donde el uso de hipergrafos toma gran relevancia, si bien el número de aplicaciones crece cada día:

◾ Procesamiento de imágenes y cancelación de ruido en imágenes. Para más información, consultar referencias [8] y [2] Capítulo 7.

◾ Optimización del rendimiento de las redes de tráfico de datos en 5G. Consultar referencia [9].

◾ Clustering en Minería de Datos. Consultar referencia [10].

Conclusiones y Trabajo futuro

Conclusiones

Los hipergrafos están demostrando que, aunque aún quede mucho por estudiar, pueden resultar en una potente herramienta matemática aplicable a diversos campos de la ciencia.

Hemos conseguido, leyendo estas páginas, conocer algunas de las nociones más importantes, pudiendo darnos cuenta de varias ventajas que los hipergrafos poseen: (1) la dualidad, característica que nos permite cambiar los papeles de vértices por hiperaristas y viceversa, dotando de un enfoque invertido que puede simplificar mucho la compresión de un problema y que podemos encontrar tanto para hipergrafos dirigidos como para no dirigidos, (2) partir de los conocimientos de la Teoría de Grafos (estructura, coloreabilidad, dirección, etc.) para reflejarlos en los hipergrafos a la hora de extraer y estudiar propiedades y ser capaz de poder transformar de grafo a hipergrafo y de hipergrafo a grafo en caso de necesidad.

Aplicamos los conceptos de partición y coloración a los hipergrafos, destacando los distintos tipos de coloreado que pueden aparecer en un hipergrafo y sus potenciales aplicaciones (una de las cuales ejemplificamos en la Sección 4). Además, los hipergrafos mixtos nos han permitido conocer gracias a su peculiar estructura nuevas definiciones y resultados.

No pasa desapercibido el complicado comportamiento que presenta esta nueva herramienta en el ámbito teórico. Por ejemplo, mientras que determinar la existencia de un camino euleriano en grafos se limita al estudio del grado de sus vértices, realizar la misma tarea en hipergrafos es bastante más laborioso, como hemos podido comprobar tanto para el caso de hipergrafo dirigido como para no dirigido. No obstante, este comportamiento no es una característica negativa, pues genera mucho tema de estudio en cuanto a tipos nuevos de hipergrafos, características y aplicaciones.

Trabajo futuro

A lo largo de la realización del Trabajo Fin de Grado me surgieron las siguientes dos necesidades que no pude satisfacer: una mayor extensión del documento para poder abarcar más Teoría de Hipergrafos y más capacidad de computación para poder crear ejemplos de mayores dimensiones o estudiar las propiedades de un hipergrafo dado. Es por ello que presento como posibles trabajos futuros los siguientes:

◾ El primero de ellos, enfocado a ampliar la teoría de este TFG. Algunas ideas son:

i) Métricas en hipergrafos.

ii) Morfismos en hipergrafos.

iii) Estudio de hipergrafos particulares como el Espacio Lineal, el Hipergrafo de Fano y el Sistema de Steiner.

iv) Tipos de hipergrafos distintos: hipergrafo intervalo, normal, equilibrado, árbol y plano.

v) Extensión de las propiedades hamiltonianas de los hipergrafos.

◾ El segundo de ellos, enfocado a la programación. Algunas ideas son:

i) Importación de datos (por ejemplo desde la referencia [11]) para generar el hipergrafo.

ii) Dado un hipergrafo, programar una aplicación que devuelva las características deseadas del mismo. Ejemplos de pseudo-código pueden encontrarse en la referencia [2], páginas 32 y 55.

Agradecimientos

Brevemente, quisiera agradecer a mis directores del TFG, Miguel Romance del Río y Eva Primo Tárraga, por haberme guiado durante la realización del trabajo y, además, por haberme brindado la oportunidad de poder participar con este artículo en la revista Forum Docentis.

Referencias

¹ A. Illán, “Análisis de grafos con relaciones de orden superior.”, Grado en Matemáticas, Universidad Rey Juan Carlos (Madrid, España), Octubre 2022.

² A. Bretto, Hypergraph theory. An introduction. (Springer, 2013).

³ V. I. Voloshin, Introduction to graph and hypergraph theory. (Nova Science Publishers, 2009).

⁴ M. Grötschel y L. Lovász, Handbook of Combinatorics Volume 1 (Elsevier, 1995).

⁵ C. Berge y P. Duchet, “A generalization of Gilmore’s theorem. Recent advances in graph theory.”, 49–55 (1975).

⁶ C. Goffman, “And what is your Erdös number?”, American Math (1969).

⁷ N. Larrea, “El Número de Bacon.”, Fancine UC3M (Noviembre 2016).

⁸ A. Bretto y L. Gillibert, “Hypergraph-based image representation. In International Workshop on Graph-Based Representations in Pattern Recognition”, 1–11 (2005).

⁹ H. Zhang, L. Song, Y. Li y G. Y. Li, “Hypergraph theory: Applications in 5G heterogeneous ultra-dense networks.”, IEEE Communications Magazine 55, 70–76 (2017).

¹⁰ E. Han, G. Karypis, V. Kumar y B. Mobasher, “Clustering based on association rule hypergraphs.”, (1997).

¹¹ A. Benson, Austin R. Benson datasets.