Graphentheorie - Isomorphismus
Ein Graph kann in verschiedenen Formen mit der gleichen Anzahl von Eckpunkten, Kanten und auch der gleichen Kantenkonnektivität existieren. Solche Graphen werden isomorphe Graphen genannt. Beachten Sie, dass wir die Grafiken in diesem Kapitel hauptsächlich beschriften, um auf sie zu verweisen und sie voneinander zu erkennen.
Isomorphe Graphen
Zwei Graphen G 1 und G 2 sollen isomorph sein, wenn -
Ihre Anzahl von Komponenten (Eckpunkte und Kanten) ist gleich.
Ihre Edge-Konnektivität bleibt erhalten.
Note- Kurz gesagt, von den beiden isomorphen Graphen ist einer eine optimierte Version des anderen. Ein unbeschrifteter Graph kann auch als isomorpher Graph betrachtet werden.
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.Note
Wenn G 1 ≡ G 2 ist, dann -
| V (G 1 ) | = | V (G 2 ) |
| E (G 1 ) | = | E (G 2 ) |
Die Gradfolgen von G 1 und G 2 sind gleich.
Wenn die Eckpunkte {V 1 , V 2 , .. Vk} einen Zyklus der Länge K in G 1 bilden , sollten die Eckpunkte {f (V 1 ), f (V 2 ),… f (Vk)} einen Zyklus bilden der Länge K in G 2 .
Alle obigen Bedingungen sind notwendig, damit die Graphen G 1 und G 2 isomorph sind, aber nicht ausreichend, um zu beweisen, dass die Graphen isomorph sind.
(G 1 ≡ G 2 ) genau dann, wenn (G 1 - ≡ G 2 -) wobei G 1 und G 2 einfache Graphen sind.
(G 1 ≡ G 2 ) wenn die Adjazenzmatrizen von G 1 und G 2 gleich sind.
(G 1 ≡ G 2 ) genau dann, wenn die entsprechenden Teilgraphen von G 1 und G 2 (erhalten durch Löschen einiger Eckpunkte in G1 und ihrer Bilder in Graph G 2 ) isomorph sind.
Example
Welche der folgenden Grafiken sind isomorph?
In dem Graphen G 3 hat der Scheitelpunkt 'w' nur Grad 3, während alle anderen Graphenscheitelpunkte Grad 2 haben. Daher ist G3 nicht isomorph zu G 1 oder G 2 .
Wenn Sie Komplemente von G 1 und G 2 nehmen , haben Sie -
Hier (G 1 - ≡ G 2 -), daher (G 1 ≡ G 2 ).
Planare Graphen
Ein Graph 'G' wird als planar bezeichnet, wenn er auf einer Ebene oder einer Kugel gezeichnet werden kann, sodass sich an einem Nicht-Scheitelpunkt keine zwei Kanten kreuzen.
Example
Regionen
Jeder planare Graph unterteilt die Ebene in verbundene Bereiche, die als Regionen bezeichnet werden.
Example
Grad einer begrenzten Region r = deg(r) = Anzahl der Kanten, die die Bereiche r einschließen.
deg(1) = 3
deg(2) = 4
deg(3) = 4
deg(4) = 3
deg(5) = 8
Grad einer unbegrenzten Region r = deg(r) = Anzahl der Kanten, die die Bereiche r einschließen.
deg(R1) = 4
deg(R2) = 6In planaren Graphen gelten die folgenden Eigenschaften:
In einem planaren Graphen mit 'n' Eckpunkten ist die Gradsumme aller Eckpunkte -
Gemäß Sum of Degrees of Regions/ Theorem, in einem planaren Graphen mit 'n' Regionen ist die Summe der Grad der Regionen -
Basierend auf dem obigen Satz können Sie die folgenden Schlussfolgerungen ziehen:
In einem planaren Graphen
Wenn der Grad jeder Region K ist, dann ist die Summe der Grad der Regionen -
Wenn der Grad jeder Region mindestens K (≥ K) beträgt, dann
Wenn der Grad jeder Region höchstens K (≤ K) ist, dann
Note - Angenommen, alle Regionen haben den gleichen Grad.
Gemäß Euler’s Formulae auf planaren Graphen,
Wenn ein Graph 'G' ein verbundener Planar ist, dann
Wenn ein planares Diagramm mit 'K'-Komponenten vorliegt, dann
Wo, | V | ist die Anzahl der Eckpunkte | E | ist die Anzahl der Kanten und | R | ist die Anzahl der Regionen.
Kantenscheitelpunktungleichung
Wenn 'G' ein verbundener planarer Graph mit einem Grad jeder Region von mindestens 'K' ist, dann
| E | ≤ k / (k-2) {| v | - 2}
Sie wissen, | V | + | R | = | E | + 2
K. | R | ≤ 2 | E |
K (| E | - | V | + 2) ≤ 2 | E |
(K - 2) | E | ≤ K (| V | - 2)
| E | ≤ k / (k-2) {| v | - 2}
Wenn 'G' ein einfacher verbundener planarer Graph ist, dann
|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4Es gibt mindestens einen Scheitelpunkt V • ∈ G, so dass deg (V) ≤ 5 ist.
Wenn 'G' ein einfacher verbundener planarer Graph (mit mindestens 2 Kanten) und ohne Dreiecke ist, dann
|E| ≤ {2|V| – 4}Kuratowskis Satz
Ein Graph 'G' ist genau dann nicht planar, wenn 'G' einen Teilgraphen hat, der homöomorph zu K 5 oder K 3,3 ist .
Homomorphismus
Zwei Graphen G 1 und G 2 werden als homomorph bezeichnet, wenn jeder dieser Graphen aus demselben Graphen 'G' erhalten werden kann, indem einige Kanten von G durch mehr Eckpunkte geteilt werden. Schauen Sie sich das folgende Beispiel an -
Teilen Sie die Kante 'rs' in zwei Kanten, indem Sie einen Scheitelpunkt hinzufügen.
Die unten gezeigten Diagramme sind homomorph zum ersten Diagramm.
Wenn G 1 zu G 2 isomorph ist , dann ist G zu G2 homöomorph, aber das Gegenteil muss nicht wahr sein.
Jeder Graph mit 4 oder weniger Eckpunkten ist planar.
Jeder Graph mit 8 oder weniger Kanten ist planar.
Ein vollständiger Graph K n ist genau dann planar, wenn n ≤ 4 ist.
Der vollständige zweigliedrige Graph K m, n ist genau dann planar, wenn m ≤ 2 oder n ≤ 2 ist.
Ein einfacher nichtplanarer Graph mit einer minimalen Anzahl von Eckpunkten ist der vollständige Graph K 5 .
Der einfache nichtplanare Graph mit der minimalen Anzahl von Kanten ist K 3, 3 .
Polyedrischer Graph
Ein einfacher verbundener planarer Graph wird als polyedrischer Graph bezeichnet, wenn der Grad jedes Scheitelpunkts ≥ 3 ist, dh Grad (V) ≥ 3 ∀ V ∈ G.
3 | V | ≤ 2 | E |
3 | R | ≤ 2 | E |