Ein Beispiel-Hypergraph, mit

und

.

]]

In der Mathematik ist ein Hypergraph eine Generalisation eines Graphen, wo ein Rand jede Zahl von Scheitelpunkten verbinden kann. Formell ist ein Hypergraph ein Paar, wo eine Reihe von Elementen, genannt Knoten oder Scheitelpunkte ist, und eine Reihe nichtleerer Teilmengen von genannten Hyperrändern oder Verbindungen ist. Deshalb, ist eine Teilmenge dessen, wo der Macht-Satz dessen ist.

Während Graph-Ränder Paare von Knoten sind, sind Hyperränder willkürliche Sätze von Knoten, und können deshalb eine beliebige Zahl von Knoten enthalten. Jedoch ist es häufig nützlich, Hypergraphen zu studieren, wo alle Hyperränder denselben cardinality haben: Ein K-Uniform-Hypergraph ist ein solcher Hypergraph, dass alle seine Hyperränder Größe k haben. (Mit anderen Worten ist es eine Sammlung von Sätzen der Größe k.), So ist ein 2-Uniformen-Hypergraph ein Graph, ist ein 3-Uniformen-Hypergraph eine Sammlung dessen verdreifacht sich und so weiter.

Ein Hypergraph wird auch ein Satz-System oder eine Familie von Sätzen genannt, die vom universalen Satz X gezogen sind. Hypergraphen können als Vorkommen-Strukturen und umgekehrt angesehen werden. Insbesondere es gibt einen Graphen von Levi entsprechend jedem Hypergraphen, und umgekehrt. In der rechenbetonten Geometrie kann ein Hypergraph einen Reihe-Raum genannt werden, und die Hyperränder werden Reihen genannt.

In der kooperativen Spieltheorie werden Hypergraphen einfache Spiele genannt (Spiele wählend); dieser Begriff wird angewandt, um Probleme in der sozialen auserlesenen Theorie zu beheben.

Spezielle Fälle von Hypergraphen schließen das Durcheinander ein, wo kein Rand als eine Teilmenge eines anderen Randes erscheint; und der Auszug simplicial Komplex, der alle Teilmengen jedes Randes enthält.

Die Sammlung von Hypergraphen ist eine Kategorie mit dem Hypergraph-Homomorphismus als morphisms.

Fachsprache

Weil Hypergraph-Verbindungen jeden cardinality haben können, gibt es vielfache, verschiedene Begriffe des Konzepts eines Subgraphen: subhypergraphs, teilweise Hypergraphen und Abteilungshypergraphen.

Lassen Sie, der Hypergraph zu sein, der aus Scheitelpunkten besteht

:

d. h. die Scheitelpunkte werden durch einen Index mit einem Inhaltsverzeichnis versehen, und der Rand-Satz ist

:

mit den durch einen Index mit einem Inhaltsverzeichnis versehenen Rändern.

Ein subhypergraph ist ein Hypergraph mit einigen entfernten Scheitelpunkten. Formell wird der subhypergraph, der durch eine Teilmenge dessen veranlasst ist, als definiert

:

e_i \cap Ein \neq \varnothing \rbrace \right) </Mathematik>

Der teilweise Hypergraph ist ein Hypergraph mit einigen entfernten Rändern. In Anbetracht einer Teilmenge des Index-Satzes ist der teilweise Hypergraph, der dadurch erzeugt ist, der Hypergraph

:

In Anbetracht einer Teilmenge ist der Abteilungshypergraph der teilweise Hypergraph

:

i\in I, e_i \subseteq Ein \rbrace \right) </Mathematik>

Der Doppel-davon ist ein Hypergraph, dessen Scheitelpunkte und Ränder ausgewechselt werden, so dass durch die Scheitelpunkte gegeben wird, und dessen Ränder durch wo gegeben werden

:

Wenn ein Begriff der Gleichheit, wie getan, unten richtig definiert wird, ist die Operation, den Doppel-von einem Hypergraphen zu nehmen, eine Involution, d. h.,

:

Ein verbundener Graph G mit demselben Scheitelpunkt ist untergegangen, wie ein verbundener Hypergraph H ein Gastgeber-Graph für H ist, wenn jeder Hyperrand von H einen verbundenen Subgraphen in G veranlasst. Für einen getrennten Hypergraphen H ist G ein Gastgeber-Graph, wenn es eine Bijektion zwischen den verbundenen Bestandteilen von G und H, solch gibt, dass jeder verbundene Bestandteil G G ein Gastgeber des entsprechenden H ist.

Der ursprüngliche Graph eines Hypergraphen ist der Graph mit denselben Scheitelpunkten des Hypergraphen und die Ränder zwischen allen Paaren von in demselben Hyperrand enthaltenen Scheitelpunkten. Der ursprüngliche Graph ist manchmal auch bekannt als der Graph von Gaifman des Hypergraphen.

Zweiteiliges Graph-Modell

Ein Hypergraph H kann durch einen zweiteiligen Graphen BG wie folgt vertreten werden: Die Sätze X und E sind die Teilungen von BG, und (x, e) werden mit einem Rand verbunden, wenn, und nur wenn Scheitelpunkt x im Rand e in H enthalten wird. Umgekehrt vertritt jeder zweiteilige Graph mit festen Teilen und keinen unverbundenen Knoten im zweiten Teil einen Hypergraphen in der näher beschriebenen Art und Weise oben. Dieser zweiteilige Graph wird auch Vorkommen-Graphen genannt.

Isomorphismus und Gleichheit

Ein Hypergraph-Homomorphismus ist eine Karte vom Scheitelpunkt-Satz eines Hypergraphen zu einem anderen solchem, dass jeder Rand zu einem anderem Rand kartografisch darstellt.

Ein Hypergraph ist zu einem Hypergraphen isomorph, schriftlich, als ob dort eine Bijektion besteht

:

und eine Versetzung von solchen dass

:

Die Bijektion wird dann den Isomorphismus der Graphen genannt. Bemerken Sie das

: wenn und nur wenn.

Wenn die Ränder eines Hypergraphen ausführlich etikettiert werden, hat man den zusätzlichen Begriff des starken Isomorphismus. Man sagt, dass das dazu stark isomorph ist, wenn die Versetzung die Identität ist. Man schreibt dann. Bemerken Sie, dass alle stark isomorphen Graphen, aber nicht umgekehrt isomorph sind.

Wenn die Scheitelpunkte eines Hypergraphen ausführlich etikettiert werden, hat man die Begriffe der Gleichwertigkeit, und auch der Gleichheit. Man sagt, dass das dazu gleichwertig ist und schreibt, ob der Isomorphismus hat

:und:

Bemerken Sie das

: wenn und nur wenn

Wenn, außerdem, die Versetzung die Identität ist, sagt man, dass das gleich ist und schreibt. Bemerken Sie, dass, mit dieser Definition der Gleichheit, Graphen Selbstdoppel-sind:

:

Ein Hypergraph automorphism ist ein Isomorphismus von einem Scheitelpunkt-Satz in sich, der ein Wiederbeschriften von Scheitelpunkten ist. Der Satz von automorphisms eines Hypergraphen H (= (X, E)) ist eine Gruppe unter der Zusammensetzung, genannt die automorphism Gruppe des Hypergraphen und schriftlichen Aut (H).

Beispiele

Denken Sie den Hypergraphen mit Rändern

:

e_1 = \lbrace a, b \rbrace,

e_2 = \lbrace b, c \rbrace,

e_3 = \lbrace c, d \rbrace,

e_4 = \lbrace d, ein \rbrace,

e_5 = \lbrace b, d \rbrace,

e_6 = \lbrace a, c \rbrace

\rbrace </Mathematik>

und:

f_1 = \lbrace \alpha, \beta \rbrace,

f_2 = \lbrace \beta, \gamma \rbrace,

f_3 = \lbrace \gamma, \delta \rbrace,

f_4 = \lbrace \delta, \alpha \rbrace,

f_5 = \lbrace \alpha, \gamma \rbrace,

f_6 = \lbrace \beta, \delta \rbrace

\rbrace </Mathematik>

Dann klar und sind isomorph (mit, usw.), aber sie sind nicht stark isomorph. Also, zum Beispiel, in, entspricht Scheitelpunkt Ränder 1, 4 und 6, so dass,

:

Im Graphen, dort besteht kein Scheitelpunkt, der Ränder 1, 4 und 6 entspricht:

:

In diesem Beispiel, und sind gleichwertig, und die duals sind stark isomorph:.

Symmetrische Hypergraphen

Die Reihe eines Hypergraphen ist das Maximum cardinality von einigen der Ränder im Hypergraphen. Wenn alle Ränder denselben cardinality k haben, wie man sagt, ist der Hypergraph gleichförmig oder K-Uniform', oder wird einen K-Hypergraphen genannt'. Ein Graph ist gerade ein 2-Uniformen-Hypergraph.

Der Grad d (v) eines Scheitelpunkts v ist die Zahl von Rändern, die es enthalten. H ist k-regular', wenn jeder Scheitelpunkt Grad k hat.

Der Doppel-von einem gleichförmigen Hypergraphen ist regelmäßig und umgekehrt.

Zwei Scheitelpunkte x und y von H werden symmetrisch genannt, wenn dort ein solcher automorphism dass besteht. Wie man sagt, sind zwei Ränder und symmetrisch, wenn dort ein solcher automorphism dass besteht.

Wie man

sagt, ist ein Hypergraph mit dem Scheitelpunkt transitiv (oder mit dem Scheitelpunkt symmetrisch), wenn alle seine Scheitelpunkte symmetrisch sind. Ähnlich ist ein Hypergraph mit dem Rand transitiv, wenn alle Ränder symmetrisch sind. Wenn ein Hypergraph sowohl Rand - als auch mit dem Scheitelpunkt symmetrisch ist, dann ist der Hypergraph einfach transitiv.

Wegen der Hypergraph-Dualität ist die Studie des Randes-transitivity zur Studie des Scheitelpunkts-transitivity identisch.

Transversals

Ein transversal oder schlagender Satz eines Hypergraphen H = (X, E) sind ein Satz, der nichtleere Kreuzung mit jedem Rand hat. Ein transversal T wird minimal genannt, wenn keine richtige Teilmenge von T ein transversal ist. Der transversal Hypergraph von H ist der Hypergraph (X, F), wessen Rand untergegangen ist, besteht F aus dem ganzen minimalen transversals von H. Die Computerwissenschaft des transversal Hypergraphen hat Anwendungen im Maschinenlernen und den anderen Feldern der Informatik, weil Spieltheorie, das Indexieren von Datenbanken, Problem, Datenbergwerk und Optimierung GESESSEN hat.

Vorkommen-Matrix

Lassen Sie und. Jeder Hypergraph hat eine Vorkommen-Matrix wo

:

Das Umstellen der Vorkommen-Matrix definiert einen Hypergraphen genannt den Doppel-davon, wo eine M Element-Satz ist und ein N-Element-Satz von Teilmengen dessen ist. Für und wenn und nur wenn.

Das Hypergraph-Färben

Das Hypergraph-Färben wird wie folgt definiert. Lassen Sie, ein solcher Hypergraph dass zu sein. Dann ist ein richtiges Färben dessen, wenn, und nur wenn, für alle dort solch dass besteht.

Mit anderen Worten: Für jeden Rand im Graphen, der mindestens zwei Knoten als Endpunkte hat, sind die Knoten, die dieser Rand verbindet, nicht die ganze dieselbe Farbe.

Teilungen

Ein Teilungslehrsatz wegen E. Daubers stellt fest, dass, für einen mit dem Rand transitiven Hypergraphen, dort eine Teilung besteht

:

des solchen Scheitelpunkt-Satzes, dass der subhypergraph, der dadurch erzeugt ist, für jeden transitiv, und dass solch

ist:

wo die Reihe von H ist.

Als eine Folgeerscheinung ist ein mit dem Rand transitiver Hypergraph, der nicht mit dem Scheitelpunkt transitiv ist, bicolorable.

Das Graph-Verteilen (und insbesondere Hypergraph-Verteilen) haben viele Anwendungen auf das IC Design und die parallele Computerwissenschaft.

Lehrsätze

Viele Lehrsätze und Konzepte, die Graphen auch einschließen, halten für Hypergraphen. Der Lehrsatz von Ramsey und Liniengraph eines Hypergraphen sind typische Beispiele. Einige Methoden, um symmetries von Graphen zu studieren, strecken sich bis zu Hypergraphen aus.

Zwei prominente Lehrsätze sind Erd&#337;s-Ko-Rado Lehrsatz und der Kruskal-Katona Lehrsatz auf gleichförmigen Hypergraphen.

Hypergraph-Zeichnung

Obwohl Hypergraphen schwieriger sind, sich auf Papier zu stützen, als Graphen, haben mehrere Forscher Methoden für die Vergegenwärtigung von Hypergraphen studiert.

In einer möglicher Sehdarstellung für Hypergraphen, die dem Standardgraph-Zeichnungsstil ähnlich sind, in dem Kurven im Flugzeug verwendet werden, um Graph-Ränder zu zeichnen, werden Scheitelpunkte eines Hypergraphen als Punkte, Platten oder Kästen gezeichnet, und seine Hyperränder werden als Bäume gezeichnet, die die Scheitelpunkte als ihre Blätter haben. Wenn die Scheitelpunkte als Punkte vertreten werden, können die Hyperränder auch als glatte Kurven gezeigt werden, die Sätze von Punkten, oder als einfache geschlossene Kurven verbinden, die Sätze von Punkten einschließen.

In einem anderen Stil der Hypergraph-Vergegenwärtigung, dem Unterteilungsmodell der Hypergraph-Zeichnung, wird das Flugzeug in Gebiete unterteilt, von denen jedes einen einzelnen Scheitelpunkt des Hypergraphen vertritt. Die Hyperränder des Hypergraphen werden durch aneinander grenzende Teilmengen dieser Gebiete vertreten, die durch das Färben, durch die Zeichnung von Umrissen um sie oder beide angezeigt werden können. Eine Ordnung-n Venn-Diagramm kann zum Beispiel als eine Unterteilungszeichnung eines Hypergraphen mit n Hyperrändern (die Kurven angesehen werden, die das Diagramm definieren) und 2 &minus; 1 Scheitelpunkte (vertreten durch die Gebiete, in die diese Kurven das Flugzeug unterteilen). Im Vergleich mit der polynomisch-maligen Anerkennung von planaren Graphen ist es NP-complete, um zu bestimmen, ob ein Hypergraph eine planare Unterteilungszeichnung hat, aber die Existenz einer Zeichnung dieses Typs kann effizient geprüft werden, wenn das Angrenzen-Muster der Gebiete beschränkt wird, ein Pfad, Zyklus oder Baum zu sein.

Generalisationen

Eine mögliche Generalisation eines Hypergraphen soll Rändern erlauben, auf andere Ränder hinzuweisen. Es gibt zwei Schwankungen dieser Generalisation. In einem bestehen die Ränder nicht nur einer Reihe von Scheitelpunkten, aber können auch Teilmengen von Scheitelpunkten ad infinitum enthalten. Satz-Mitgliedschaft stellt dann eine Einrichtung zur Verfügung, aber die Einrichtung ist weder eine teilweise Ordnung noch eine Vorordnung, da es nicht transitiv ist. Der Graph entsprechend dem Graphen von Levi dieser Generalisation ist ein geleiteter acyclic Graph., Denken Sie zum Beispiel, den verallgemeinerten Hypergraphen, dessen Scheitelpunkt-Satz ist, und dessen Ränder sind und. Dann, obwohl und, es das nicht wahr ist. Jedoch veranlasst der transitive Verschluss der Satz-Mitgliedschaft für solche Hypergraphen wirklich eine teilweise Ordnung, und "macht" den Hypergraphen in einen teilweise bestellten Satz "glatt".

Abwechselnd kann Rändern erlaubt werden, auf andere Ränder, (ohne Rücksicht auf die Voraussetzung dass die Ränder hinzuweisen, wie geleitet, acyclic Graphen bestellt werden). Das erlaubt Graphen mit Rand-Schleifen, die Scheitelpunkte überhaupt nicht zu enthalten brauchen. Denken Sie zum Beispiel den verallgemeinerten Hypergraphen, der aus zwei Rändern und, und Nullscheitelpunkte, so dass besteht und. Da diese Schleife ungeheuer rekursiv ist, verletzen Sätze, die die Ränder sind, das Axiom des Fundaments. Insbesondere es gibt keinen transitiven Verschluss der Satz-Mitgliedschaft für solche Hypergraphen. Obwohl solche Strukturen sonderbar zuerst scheinen können, können sie sogleich verstanden werden, indem sie bemerken, dass die gleichwertige Generalisation ihres Graphen von Levi nicht mehr zweiteilig ist, aber eher gerade ein allgemeiner geleiteter Graph ist.

Die verallgemeinerte Vorkommen-Matrix für solche Hypergraphen, ist definitionsgemäß, eine Quadratmatrix von einer Reihe, die der Gesamtzahl von Scheitelpunkten plus Ränder gleich ist. So, für das obengenannte Beispiel, ist die Vorkommen-Matrix einfach

:

Siehe auch

• P System
• Faktor-Graph
• Greedoid
• Vorkommen-Struktur
• Matroid

Referenzen

• Claude Berge, Dijen Strahl-Chaudhuri, "Hypergraph-Seminar, Ohio Staatliche Universität 1972", Vortrag-Zeichen in der Mathematik 411 Springer-Verlag
• Vitaly I. Voloshin. "Einführung, um Theorie Grafisch darzustellen und Grafisch hyperdarzustellen". Nova Science Publishers, Inc., 2009.