Wie lautet die maximale Anzahl perfekter Machtings in einem vollständigen paaren Graphen ?

1 Antwort

Sei {U,V} die Partition des Graphen in seiner zwei unabhängigen Komponenten (ich habe den genauen Begriff vergessen, aber du weißt hoffentlich, was ich meine). Seien m := |U| und n := |V|.

Lemma. in einem vollständigen bipartiten Graphen G mit Partition {U,V} sind die Matching 1 zu 1 durch die injektiven partiellen Funktionen ƒ : A ⟶ B mit A ⊆ U und B ⊆ V. 

Folgerung. in einem vollständigen bipartiten Graphen G mit Partition {U,V} sind die Matching 1 zu 1 durch die maximalen (bzgl. Funktionerweiterungen) injektiven partiellen Funktionen ƒ : A ⟶ B mit A ⊆ U und B ⊆ V. Falls G endlich (sodass U, V endlich sind) und |U| ≤ |V|, so gilt dies nur dann, wenn A=U.

Mithilfe dieser Charakterisierung können wir aufzählen:

Fall 1. |U| ≤ |V|. Dann v(G) = # Inj. Funktionen ƒ : U ⟶ V. Dies ist gleich n! / (n–m)!.

Fall 2. |V| ≤ |U|. Durch Symmetrie v(G) = # Inj. Funktionen ƒ : V ⟶ U. Dies ist gleich m! / (m–n)!

In allen Fällen gilt v(G) = Max{m,n}! / |m–n|!

Warum hat jeder planare, dreiecksfreie Graph einen Knoten mit Grad 3 oder weniger?

Also ich merke schon, dass dies der Fall ist. Aber was ist da die Erklärung für?

...zur Frage

Graphentheorie:vollständige Induktion?

Hallo! Ich habe paar Probleme bei einer Aufgabe! Ich glaube ich habe die Grundidee verstanden..aber dennoch kann ich mit der Aufgabe nicht so recht umgehen. Sie lautet:

Sei G n der Graph, dessen Knoten die Permutationen der Menge {1, . . . , n} sind, wobei zwei Knoten genau dann adjazent sind, wenn die zwei entsprechenden Permutationen durch den Austausch zweier benachbarter Elemente ineinander überführt werden können. Zeigen Sie mit vollständiger Induktion, dass G n zusammen- hängend ist.

also meine verständnisidee wäre...sei zb 123 die permutation,dann müssen sich die benachbarten 2 zahlen umdrehen. also zb 213 oder 321... diese ,,gedrehten permutationen) sind sozusagen die knoten und zw denen entstehen kannten,wo es zutrifft. die induktion bezieht sich dann auf die länge der permutation... und der schwerpunkt liegt dann wohl beim ,,tauschen" der zahlen.

ich hoffe ich habe es richtig verstanden. nur weiß ich nicht,wie ich die aufgabe lösen soll.

danke im vorraus! gf20109

...zur Frage

Wie zeichnet man die Linien eines Hexagons nach ohne eine Linie 2-mal zu benutzen?

Also man darf nur jede Linie einmal benutzen. Nicht doppelt drüber malen.

Wie geht das?

Ich hab schon gefühlte 100 Mal im Kreis gemalt aber immer bleiben 2 Strecken frei.

Über Google hab ich dazu nichts gefunden.

Habt ihr eine Lösung?

Lg, PCtiger :)

...zur Frage

Was ist ein Splitgraph?

Kann mir da jemand ein Beispiel machen?

Die Definition, aus der ich nicht wirklich schlau werde, ist folgende:

Ein ungerichteter Graph G = (V,E) heißt Splitgraph, falls es eine Knotenmenge U ⊆ V gibt, sodass G[U] ein vollständiger Graph und G[V\U] ein leerer Graph ist.

Ich interpretiere das so, dass V=U sein muss, damit G[V\U] leer ist, aber das macht ja gar keinen Sinn. Wo ist da der Fehler?

...zur Frage

Für welche Graphen ist die planara Einbettung eindeutig?

Ist die Antwort darauf, dass bei eindeutigen Einbettung die Facezyklen gleich bleiben? Ich konnte darauf leider keine zufriedenstellende Antwort finden.

...zur Frage

Was ist der unterschied zwischen inneren Knoten und Blättern (Graphentheorie)

...zur Frage

Was möchtest Du wissen?