Ein Graph heißt planar, wenn er in einer Ebene gezeichnet werden kann, sodass sich keine Kanten kreuzen.

Beispiel: Der in Abb. gezeigte Graph ist ein planarer Graph.

was ist 10 von 60

Bereich eines Diagramms: Betrachten Sie einen planaren Graphen G=(V,E). Eine Region ist definiert als ein Bereich der Ebene, der durch Kanten begrenzt ist und nicht weiter unterteilt werden kann. Ein planarer Graph unterteilt die Pläne in einen oder mehrere Bereiche. Eine dieser Regionen wird unendlich sein.

Endliche Region: Wenn die Fläche der Region endlich ist, wird diese Region als endliche Region bezeichnet.

Unendliche Region: Wenn die Fläche der Region unendlich ist, wird diese Region als unendliche Region bezeichnet. Ein planarer Graph hat nur einen unendlichen Bereich.

Beispiel: Betrachten Sie den in Abb. gezeigten Graphen. Bestimmen Sie die Anzahl der Regionen, endliche Regionen und eine unendliche Region.

Lösung: In der obigen Grafik gibt es fünf Regionen, d. h. r₁,R₂,R₃,R₄,R₅.

Es gibt vier endliche Regionen im Diagramm, nämlich r₂,R₃,R₄,R₅.

Es gibt nur eine endliche Region, nämlich r₁

Eigenschaften planarer Graphen:

1. Wenn ein zusammenhängender planarer Graph G e Kanten und r Bereiche hat, dann ist r ≦ Es ist.
2. Wenn ein verbundener planarer Graph G e Kanten, v Eckpunkte und r Regionen hat, dann ist v-e+r=2.
3. Wenn ein verbundener planarer Graph G e Kanten und v Eckpunkte hat, dann ist 3v-e≧6.
4. Ein vollständiger Graph K_Nist genau dann ein Planar, wenn n<5.< li>
5. Ein vollständiger zweiteiliger Graph K_mnist genau dann planar, wenn m3.

Beispiel: Beweisen Sie den vollständigen Graphen K₄ist planar.

Lösung: Der vollständige Graph K₄enthält 4 Eckpunkte und 6 Kanten.

Wir wissen, dass für einen zusammenhängenden planaren Graphen 3v-e≧6 gilt. Daher gilt für K₄, wir haben 3x4-6=6, was die Eigenschaft (3) erfüllt.

jvm in Java

Also K₄ist ein planarer Graph. Somit bewiesen.

Nichtplanarer Graph:

Ein Graph heißt nicht planar, wenn er nicht in einer Ebene gezeichnet werden kann, sodass sich keine Kanten kreuzen.

Beispiel: Die in Abb. gezeigten Diagramme sind nicht planare Diagramme.

Diese Graphen können nicht in einer Ebene gezeichnet werden, sodass sich keine Kanten kreuzen, es handelt sich also um nichtplanare Graphen.

Eigenschaften nichtplanarer Graphen:

Ein Graph ist genau dann nichtplanar, wenn er einen zu K homöomorphen Teilgraphen enthält₅oder K_3.3

Du bist ein Splice

Beispiel 1: Zeigen Sie, dass K₅ist nicht planar.

Lösung: Der vollständige Graph K₅enthält 5 Eckpunkte und 10 Kanten.

Für einen zusammenhängenden planaren Graphen gilt nun 3v-e≧6.

Daher gilt für K₅, wir haben 3 x 5-10=5 (was Eigenschaft 3 nicht erfüllt, da es größer oder gleich 6 sein muss).

So, K₅ist ein nichtplanarer Graph.

Beispiel2: Zeigen Sie, dass die in Abb. gezeigten Graphen nichtplanar sind, indem Sie einen zu K homöomorphen Untergraphen finden₅oder K_3.3.

Lösung: Wenn wir die Kanten entfernen (V₁,IN₄),(IN₃,IN₄)und (V₅,IN₄) der Graph G₁,wird homöomorph zu K₅.Daher ist es nicht planar.

Wenn wir die Kante V entfernen_2,V7) der Graph G₂wird homöomorph zu K_3.3.Daher ist es nicht planar.

Diagrammfärbung:

Angenommen, G= (V,E) ist ein Graph ohne mehrere Kanten. Eine Scheitelpunktfärbung von G ist eine Zuweisung von Farben zu den Scheitelpunkten von G, sodass benachbarte Scheitelpunkte unterschiedliche Farben haben. Ein Graph G ist M-färbbar, wenn es eine Färbung von G gibt, die M-Farben verwendet.

Richtige Färbung: Eine Färbung ist richtig, wenn zwei benachbarte Eckpunkte u und v unterschiedliche Farben haben, andernfalls spricht man von falscher Färbung.

Beispiel: Betrachten Sie den folgenden Graphen und färben Sie C={r, w, b, y}. Färben Sie den Graphen richtig, indem Sie alle Farben oder weniger Farben verwenden.

Der in Abb. gezeigte Graph ist mindestens 3-färbbar, daher x(G)=3

Algorithmus für BFS

Lösung: Abb. zeigt die korrekte Farbgebung des Diagramms mit allen vier Farben.

Abb. zeigt die korrekte Farbgebung des Diagramms mit drei Farben.

Chromatische Zahl von G: Die Mindestanzahl an Farben, die erforderlich ist, um eine ordnungsgemäße Färbung eines Graphen G zu erzeugen, wird als chromatische Zahl von G bezeichnet und mit x(G) bezeichnet.

Beispiel: Die chromatische Zahl von K_Nist n.

Lösung: Eine Färbung von K_Nkann mit n Farben konstruiert werden, indem jedem Scheitelpunkt unterschiedliche Farben zugewiesen werden. Keinen zwei Scheitelpunkten können die gleichen Farben zugewiesen werden, da alle zwei Scheitelpunkte dieses Diagramms benachbart sind. Daher die chromatische Zahl von K_N=n.

Anwendungen der Graphfärbung

Zu den Anwendungen der Diagrammfärbung gehören:

• Registerzuordnung
• Kartenfärbung
• Bipartite Graphprüfung
• Mobilfunkfrequenzzuteilung
• Erstellen eines Stundenplans usw.

Geben Sie das Handshaking-Theorem an und beweisen Sie es.

Handshake-Theorem: Die Gradsumme aller Eckpunkte in einem Graphen G ist gleich der doppelten Anzahl von Kanten im Graphen.

Mathematisch lässt sich das so formulieren:

∑_v∈VGrad(v)=2e

Nachweisen: Sei G = (V, E) ein Graph mit V = {v₁,In₂, . . . . . . . . . .} sei die Menge der Eckpunkte und E = {e₁,Es ist₂. . . . . . . . . .} sei die Menge der Kanten. Wir wissen, dass jede Kante zwischen zwei Scheitelpunkten liegt, sodass sie jedem Scheitelpunkt den Grad eins verleiht. Daher trägt jede Kante zum Grad zwei für den Graphen bei. Die Summe der Grade aller Eckpunkte ist also gleich der doppelten Anzahl der Kanten in G.

Daher ist ∑_v∈VGrad(v)=2e

String-Datum konvertieren