• Forschung
  • aktuelle Projekte
  • Archiv
  • Summengraphen
  • Gäste
  • Forschung

    Summenzahlen von Hypergraphen

    Im Zusammenhang mit der Speicherung von Graphen auf Computern werden seit Ende der Achtziger Jahre Strukturen von sogenannten Summengraphen bzw. Summenzahlen bestimmter Graphenklassen analysiert. Die Verallgemeinerung dieses Konzepts liefert folgende Definitionen: Ein Hypergraph $\mathcal H$ heißt genau dann Summenhypergraphen, wenn es eine endliche Menge $ S \subset \mathbb N^+$ und $\overline{d}$,$\underline{d}$ mit $\underline{d} \lt \overline{d}$ gibt, so dass $\mathcal H$ isomorph zum Hypergraphen $\mathcal H_{\underline{d},\overline{d}}(S) = (V,\mathcal E)$ ist, wobei $$\label{a} V := S \text{ und } \mathcal E := \left\{\left.e \subset S\right| \underline{d} \leq |e| \leq \overline{d} \wedge \sum_{v\in e} v \in S\right\} $$

    Für einen beliebigen Hypergraphen $\mathcal H$ ist die Summenzahl $\sigma = \sigma(\mathcal H)$ definiert als die minimale Anzahl isolierter Knoten $y_1,\ldots,y_{\sigma}\notin V$ so dass \mathcal H \cup \{y_1,\ldots,y_{\sigma}\}$ ein Summenhypergraph ist.

    Die Struktur des Summengraphen mit der Knotenmarkierung {1,2,…,11}
    Die Struktur des Summengraphen mit der Knotenmarkierung $\{1,2\ldots,11\}$

    Seit einigen Jahren gibt es Ansätze, verschiedene, ursprünglich für Graphen konstruierte Markierungen auf Hypergraphen zu betrachten. Das Hauptanliegen des Forschungsprojektes ist die Untersuchung von Summenzahlen für Klassen von Hypergraphen, die sich als Verallgemeinerungen bestimmter Graphen ergeben; exemplarisch seien hier vollständige d-uniforme Hypergraphen, Hyperbäume und Hyperkreise genannt. Eine in gewisser Hinsicht ,,inverse`` Fragestellung zu dem oben genannten Problem sind Strukturuntersuchungen d-uniformer Hypergraphen bei vorgegebener Knotenmarkierung $S$

    Eine Anwendung dieses Konzeptes für die Informatik ist offensichtlich: Sind für einen Hypergraphen $\mathcal H$ die Summenzahl und eine passende Knotenmarkierung $S$ $V ({\cal H}) \cup \{y_1,\ldots,y_\sigma\}$ bekannt, so ist die Erfassung im Computer effizient möglich, indem lediglich die Marken gespeichert werden, und die zugehörige Kantenmenge über die Beziehung \ref{a} erzeugt wird.

    Literatur

    Bearbeitet von
    PD Dr. Hanns-Martin Teichert
    In Zusammenarbeit mit
    Prof. Dr. Martin Sonntag (TU Bergakademie Freiberg)