WikiDer > Hypergraph

Ein Beispiel für einen Hypergraphen mit 7 Knoten v₁...v₇ und vier Seiten: e₁...e₄. ${displaystyle X={v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}}}$ und ${displaystyle E={e_{1},e_{2},e_{3},e_{4}}=}$${Displaystil {{v_{1},v_{2},v_{3}},}$${displaystyle {v_{2},v_{3}},}$${Anzeigestil {v_{3},v_{5},v_{6}},}$${displaystyle {v_{4}}}}$.

EIN Hypergraph ist eine verallgemeinerte Form von a Anzahl. In einem "normalen" Graphen verbindet eine Seite zwei Knoten; aber in einem Hypergraphen kann a Hyperseite enthalten eine beliebige Anzahl von Knoten, die von 1 bis zur Anzahl der Knoten im Diagramm reichen.

Ein Hypergraph kann als a Sammlung von Teilmengen einer gegebenen Grundausstattung. Formal ist ein Hypergraph definiert als das Paar H = (X, E), wobei X die Menge der Knoten und E die Menge der (Hyper-)Seiten ist; Jede Hyperseite ist eine nichtleere Teilmenge von X.

Die in der Graphentheorie auftretenden Probleme werden auch in Hypergraphen untersucht, wie z Färbung, Spitzenbedeckung und Knopfabdeckung, Links, die Aufteilung eines Graphen in Klicks, finden a Hamilton-Pfad oder Hamilton-Schaltung und so weiter.

Einheitliche Hypergraphen

Der Hypergraph der Fano-Ebene

In der Praxis untersucht man oft Hypergraphen, bei denen alle Hyperseiten gleich sind Kardinalität haben; diese werden gleichförmige Hypergraphen genannt. EIN k-einheitlicher Hypergraph hat Hyperseiten mit nur Kardinalität k; mit anderen Worten, die Menge E besteht aus Mengen mit k Elemente. Ein 2-gleichförmiger Hypergraph ist also ein "regulärer" Graph; ein 3-gleichförmiger Hypergraph ist eine Menge von Tripletts usw.

Der Hypergraph des Fan-Flugzeug ist ein Beispiel für einen 3-gleichförmigen Hypergraphen. Der Graph hat sieben Knoten (nummeriert von 0 bis 6) und sieben Hyperseiten: {5,1,6}, {5,2,3}, {6,4,3}, {1,0,3}, {2, 0,6}, {5.0.4} und {1.2.4}.