Zwei-Grafik - Wikipedia

In der Mathematik ist ein Two-Graph ein Satz von (ungeordneten) Tripeln, die aus einem endlichen Vertex-Set X ausgewählt wurden, so dass jedes (ungeordnete) Vierfach aus X enthält eine gerade Anzahl von Tripeln des Zweiergraphen. Ein regulärer Zwei-Graph hat die Eigenschaft, dass jedes Paar von Knoten in der gleichen Anzahl von Tripeln des Zwei-Graphen liegt. Zwei Graphen wurden aufgrund ihrer Verbindung mit gleichwinkligen Linien und bei regulären zwei Graphen stark regulären Graphen und auch endlichen Gruppen untersucht, da viele reguläre zwei Graphen interessante Automorphismengruppen aufweisen.

Ein Zwei-Graph ist kein Graph und sollte nicht mit anderen Objekten verwechselt werden, die in der Graphentheorie als 2-Graphs bezeichnet werden, wie z. B. 2-reguläre Graphen.

Beispiele [ edit ]

Auf der Menge der Eckpunkte {1, ..., 6} ist die folgende Sammlung ungeordneter Tripel eine Zwei-Grafik:

123 124 135 146 156 236 245 256 345 346

Diese zwei Graphen sind reguläre zwei Graphen, da jedes Paar unterschiedlicher Scheitelpunkte in genau zwei Tripeln erscheint.

Ausgehend von einem einfachen Graphen G = ( V E ) wurde die Menge der Tripel des Scheitelpunktsatzes V herangezogen Subgraph hat eine ungerade Anzahl von Kanten und bildet eine Zwei-Grafik auf dem Set V . Jeder Zweigraph kann auf diese Weise dargestellt werden. ^[1] Dieses Beispiel wird als Standardaufbau eines Zweigraphen aus einem einfachen Graphen bezeichnet.

Als komplexeres Beispiel sei T ein Baum mit Randsatz E . Die Menge aller Tripel von E die nicht in einem Pfad von T enthalten sind, bilden eine Zwei-Grafik am Set E . ^[2]

Umschaltung und Grafiken [ edit ]

Umschalten von {X, Y} in einer Grafik

Ein Zwei-Graph entspricht einer Schaltklasse von Graphen und auch einer (signierten) Schaltklasse von Vorzeichen komplette Graphen.

Beim Umschalten eines Satzes von Scheitelpunkten in einem (einfachen) Graphen bedeutet das Umkehren der Nachbarn jedes Scheitelpaares, einen im Satz und den anderen nicht im Satz: So wird der Kantensatz so geändert ein benachbartes Paar wird nicht benachbart und ein nicht benachbartes Paar wird benachbart. Die Kanten, deren Endpunkte beide in der Gruppe sind oder beide nicht in der Gruppe, werden nicht geändert. Diagramme sind Schaltäquivalent wenn eines durch Umschalten vom anderen erhalten werden kann. Eine Äquivalenzklasse von Graphen unter Schalten wird als Schaltklasse bezeichnet. Switching wurde von van Lint & Seidel (1966) eingeführt und von Seidel entwickelt. Es wurde Graph Switching oder Seidel Switching genannt, um es teilweise vom Schalten von signierten Graphen zu unterscheiden.

Bei der Standardkonstruktion eines Zwei-Graphen aus einem einfachen, oben angegebenen Graphen ergeben zwei Graphen den gleichen Zwei-Graphen, und zwar nur dann, wenn sie beim Schalten gleichwertig sind, das heißt, sie liegen in derselben Schaltklasse.

Sei two zwei Graphen am Set X . Definieren Sie für jedes Element x von X einen Graphen mit einem Scheitelpunkt X mit nebeneinander liegenden Scheitelpunkten y und wenn und nur dann, wenn { x y z } in Γ ist. In diesem Diagramm wird x ein isolierter Scheitelpunkt sein. Diese Konstruktion ist reversibel. Bei einem einfachen Graphen G schließen Sie ein neues Element x an die Menge der Eckpunkte von G an und definieren die beiden Graphen, deren Tripel alle { sind ] x y z } wobei y und z benachbarte Eckpunkte in G sind. Diese zwei Graphen werden die -Erweiterung von G um x in der designtheoretischen Sprache genannt. ^[3] In einer gegebenen Schaltungsklasse von Graphen einer regulären zwei- graph, sei Γ _x der eindeutige Graph mit x als isoliertem Scheitelpunkt (dies ist immer vorhanden, nehmen Sie einfach einen beliebigen Graphen in der Klasse und wechseln Sie die offene Nachbarschaft von x ) ohne Scheitelpunkt x . Das heißt, der Zwei-Graph ist die Erweiterung von Γ _x um x . Im ersten Beispiel eines regulären Zwei-Graphen ist Γ _x ein 5-Zyklus für eine beliebige Wahl von x . ^[4]

To a graph G Dort entspricht ein vorzeichenbehafteter vollständiger Graph Σ auf demselben Scheitelpunktsatz, dessen Kanten negativ sind, wenn er in G ist, und positiv, wenn nicht in G . Umgekehrt ist G der Untergraph von Σ, der aus allen Ecken und allen negativen Kanten besteht. Der Zwei-Graph von G kann auch als die Menge von Dreifachpunkten von Scheitelpunkten definiert werden, die ein negatives Dreieck (ein Dreieck mit einer ungeraden Anzahl von negativen Kanten) in Σ unterstützen. Zwei vorzeichenbehaftete vollständige Diagramme ergeben genau dann das gleiche Diagramm, wenn sie beim Umschalten gleichwertig sind.

Das Umschalten von G und von Σ hängen zusammen: Das Umschalten derselben Scheitelpunkte in beiden ergibt einen Graphen H und den dazugehörigen unterzeichneten vollständigen Graphen.

Adjazenzmatrix [ edit ]

Die Adjazenzmatrix eines Zweigraphen ist die Adjazenzmatrix des entsprechenden signierten vollständigen Graphen; es ist also symmetrisch, ist auf der Diagonale Null und hat Eingaben ± 1 von der Diagonale. Wenn G der Graph ist, der dem vorzeichenbehafteten vollständigen Graph Σ entspricht, wird diese Matrix als (0, -1, 1) -Adjazenzmatrix oder als Seidel-Adjazenzmatrix von G bezeichnet . Die Seidel-Matrix hat null Einträge in der Hauptdiagonale, -1 Einträge für benachbarte Scheitelpunkte und +1 Einträge für nicht benachbarte Scheitelpunkte.

Wenn Graphen G und H in derselben Schaltklasse liegen, sind die Multisets der Eigenwerte der beiden Seidel-Adjazenzmatrizen von G und H stimmt überein, da die Matrizen ähnlich sind. ^[5]

Ein Zwei-Graph auf einem Satz V ist regelmäßig, wenn und nur wenn seine Adjazenzmatrix nur zwei verschiedene Merkmale aufweist Eigenwerte ρ ₁ > 0> ρ ₂ sagen, wobei ρ ₁ ρ ₂ = 1 - | V ^[6]

Gleichschenklige Linien [ edit ]

Jeder Zwei-Graph entspricht einem Satz von Linien in einem euklidischen Raum, der sich in einem bestimmten Winkel befindet. Die aus zwei Graphen auf n Knoten konstruierte Linie wird wie folgt erhalten. Sei -ρ der kleinste Eigenwert der Seidel-Adjazenzmatrix, A der zwei Graphen, und nehmen an, dass er eine Multiplizität aufweist n d d. Dann ist die Matrix ρ I + A positiv semi-definite von Rang d und kann somit als Gram-Matrix der inneren Produkte von dargestellt werden n Vektoren im euklidischen d -Raum. Da diese Vektoren dieselbe Norm haben (nämlich ${ displaystyle { sqrt { rho}}$) und gegenseitige innere Produkte ± 1 jedes Paar der n -Linien, die von ihnen umspannt werden, treffen sich im gleichen Winkel φ, wobei cos φ = 1 / ρ ist. Umgekehrt kann jeder Satz von nicht orthogonalen gleichwinkligen Linien in einem euklidischen Raum zu einem Zwei-Graphen führen (siehe äquiangulare Linien für die Konstruktion). ^[7]

Mit der oben genannten Notation maximale Kardinalität n erfüllt n ≤ d ( ² - 1) / ( ² - - ] d ) und die Grenze wird genau dann erreicht, wenn der Zwei-Graph regelmäßig ist.

Stark regelmäßige Grafiken [ edit ]

Die beiden Diagramme auf X die aus allen möglichen Tripeln von X und keinen Tripeln von bestehen X sind reguläre Zwei-Graphen und werden als Trivial -Diagramme betrachtet.

Für nicht triviale Zwei-Diagramme auf dem Set X ist das Zwei-Diagramm genau dann und wenn für einige x im X Diagramm normal Γ _x ist ein stark regelmäßiger Graph mit k = 2μ (der Grad eines Scheitelpunktes ist doppelt so groß wie die Anzahl der Scheitelpunkte neben jedem nicht benachbarten Schachtelpaar). Wenn diese Bedingung für ein x in X gilt, gilt dies für alle Elemente von X ^[8]

Daraus folgt, dass ein nicht trivialer regulärer Zwei-Graph eine gerade Anzahl von Punkten hat.

Wenn G ein regulärer Graph ist, dessen Erweiterung um zwei Graphen Γ mit n Punkten ist, dann ist a ein regelmäßiger Zwei-Graph, wenn und nur G ist ein stark regelmäßiger Graph mit Eigenwerten k r und s wobei n = 2 ( k - r ) oder n = 2 ( k - s ). ^[9]

1. ^ Colburn & Dinitz 2007, p. 876, Bemerkung 13.2
2. ^ Cameron, PJ (1994), "Zwei Graphen und Bäume", Diskrete Mathematik 127 : 63–74, doi: 10.1016 / 0012-365x (92) 00468-7 zitiert in Colburn & Dinitz 2007, p. 876, Construction 13.12
3. ^ Cameron & van Lint 1991, S. 58-59
4. ^ Cameron & van Lint 1991, S. 273. 62
5. ^ Cameron & van Lint 1991, p. 61
6. ^ Colburn & Dinitz 2007, p. 878 # 13.24
7. ^ van Lint & Seidel 1966
8. ^ Cameron & van Lint 1991, p. 62 Satz 4.11
9. ^ Cameron & van Lint 1991, p. 62 Satz 4.12

Verweise [ edit ]

• Brouwer, A. E., Cohen, A. M. und Neumaier, A. (1989), Distance-Regular Graphs. Springer-Verlag, Berlin. Abschnitte 1.5, 3.8, 7.6 C.
• Cameron, P. J .; van Lint, J.H. (1991), Entwürfe, Grafiken, Codes und ihre Verbindungen Student Texts 22 der Londoner Mathematical Society, Cambridge University Press, ISBN 978-0-521-42385-4
• Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Handbuch der kombinatorischen Entwürfe (2. Ausgabe), Boca Raton: Chapman & Hall / CRC, S. 875–882, ISBN 1-58488-506-8 [19659074GodsilChris:RoyleGordon(2001) Algebraische Graphentheorie. Diplomarbeiten in der Mathematik, Vol. 207. Springer-Verlag, New York. Chapter 11.
• Seidel, J. J. (1976), Eine Übersicht über zwei Graphen. In: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rome, 1973), Vol. I, S. 481–511. Atti dei Convegni Lincei, Nr. 17. Accademia Nazionale dei Lincei, Rom
• Taylor, D. E. (1977), Regular 2-Graphs. Verfahren der London Mathematical Society (3), vol. 35, S. 257–274.
• van Lint, J. H .; Seidel, J. J. (1966), "Gleichseitige Punktsätze in elliptischer Geometrie", Indagationes Mathematicae Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28 : 335–348