Autor |
Bipartiter Graph |
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Themenstart: 2022-05-16
|
Hallo,
Wie kann man zeigen, dass jeder vollständig gelabelte bipartite Graph K_2,n genau n*2^(n-1) aufspannende Bäume besitzt?
Gruß
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.1, eingetragen 2022-05-16
|
Hallo,
überlege Dir, wie so ein Spannbaum aussehen muss:
- Von jedem Knoten muss mindestens eine Kante ausgehen.
- Was muss zusätzlich gelten, damit die Zusammenhangseigenschaft erfüllt ist?
|
Profil
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Beitrag No.2, vom Themenstarter, eingetragen 2022-05-16
|
Naja, der Teilgraph muss zudem auch noch zusammenhängend und kreisfrei sein. Aber ich weiß nicht, wie man da vorgehen soll. Also durch Lösungen lernt man ja auch dazu.
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.3, eingetragen 2022-05-16
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Kreisfreiheit und Zusammenhang gehören zur Definition eines Spannbaums. Es geht darum herauszufinden, was genau diese beiden Eigenschaften im Falle der sehr speziellen Graphen $K_{2,n}$ aussagen.
Gegeben sei ein Spannbaum $T$. Betrachte die Knoten in der Partitionsklasse mit $n$ Elementen. Was kannst Du über die Grade dieser Knoten in $T$ aussagen?\(\endgroup\)
|
Profil
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Beitrag No.4, vom Themenstarter, eingetragen 2022-05-16
|
Naja die Grade ist das Paar von Listen, das jeweils die Knotengrade der Partitionsklassen enthält. Somit hätte der bipartite Graph K_2,n die Gradfolge (2) und (n,n), wenn ich das richtig verstanden habe?
habe mich jetzt an wiki orientiert:
https://de.wikipedia.org/wiki/Bipartiter_Graph
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.5, eingetragen 2022-05-16
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Ich glaube, Du hast meinen Tipp falsch verstanden.
Im vollständig bipartiten Graphen $K_{2,n}$ gibt es zwei Typen von Knoten:
- Es gibt $2$ Knoten, die jeweils Grad $n$ haben.
- Es gibt $n$ Knoten, die jeweils Grad $2$ haben.
Meine Frage war aber nicht nach den Knotengraden im $K_{2,n}$ selbst, sondern nach den Knotengraden in einem Spannbaum von $K_{2,n}$.
Mache Dir eventuell erstmal eine Skizze mit einem Beispiel, sagen wir mit $n=5$. Wähle einen beliebigen Spannbaum von $K_{2,5}$ und erstelle eine Liste mit den Knotengraden in diesem Spannbaum (in der Form: Es gibt genau ... Knoten mit Grad ...). Wiederhole das mit einem anderen Spannbaum (wieder mit $n=5$) und dann ggf. auch noch mit anderen $n$. Fällt Dir etwas auf?\(\endgroup\)
|
Profil
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Beitrag No.6, vom Themenstarter, eingetragen 2022-05-16
|
Also bei K_2,3 habe ich zum Beispiel 3 Knoten mit Grad 2 und 2 Knoten mit Grad 1.
Bei K_2,4 habe ich 2 Knoten mit Grad 2, 3 Knoten mit Grad 1 und 1 Knoten mit Grad 3. Aber ist wahrscheinlich falsch
|
Profil
|
StrgAltEntf
Senior  Dabei seit: 19.01.2013 Mitteilungen: 7819
Wohnort: Milchstraße
 | Beitrag No.7, eingetragen 2022-05-16
|
Kleine Ergänzung:
Man kann das auch mit dem Matrix-Gerüst-Satz berechnen. Allgemein gilt: Der vollständige bipartite Graph \(K_{m,n}\) besitzt \(n^{m-1}\cdot m^{n-1}\) Gerüste.
Grüße
StrgAltEntf
[Die Antwort wurde nach Beitrag No.5 begonnen.]
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.8, eingetragen 2022-05-16
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
\quoteon(2022-05-16 18:44 - adghl in Beitrag No. 6)
Also bei K_2,3 habe ich zum Beispiel 3 Knoten mit Grad 2 und 2 Knoten mit Grad 1.
Bei K_2,4 habe ich 2 Knoten mit Grad 2, 3 Knoten mit Grad 1 und 1 Knoten mit Grad 3. Aber ist wahrscheinlich falsch
\quoteoff
Falsch ist es nicht. Die genauen Zahlen hängen aber von dem gewählten Spannbaum ab.
Wenn Du nur die Grade der Knoten in der Partitionsklasse mit $n$ Elementen betrachtest, fällt Dir dann etwas auf?\(\endgroup\)
|
Profil
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Beitrag No.9, vom Themenstarter, eingetragen 2022-05-16
|
Leider nicht. Kannst du mir nicht einfach die Lösung sagen. Eigeninitiative habe ich doch schon gezeigt 😄
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.10, eingetragen 2022-05-16
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Könnte ich, will ich aber nicht und ist auch nicht im Sinne des Matheplaneten.
Knoten in der Partionsklasse mit $n$ Elementen können nur mit den zwei Knoten in der anderen Partitionsklasse benachbart sein. Demnach hat in einem Spannbaum jeder Knoten in der Partitionsklasse mit $n$ Elementen einen Grad $\leq 2$.
Wie oft kommt der Grad $0$ vor? Wie oft $1$? Wie oft $2$?\(\endgroup\)
|
Profil
|
adghl
Junior  Dabei seit: 06.12.2020 Mitteilungen: 15
 | Beitrag No.11, vom Themenstarter, eingetragen 2022-05-16
|
Okay, das habe ich jetzt auch auf meinen Aufzeichnungen gesehen, dass der Knotengrad der Partitionsklassen von den Spannbäumen Grad 2 nicht überschreitet.
Aber was bringen mir die Informationen über die Knotengrade, wenn ich die Anzahl der Spannbäume herausfinden möchte
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3565
 | Beitrag No.12, eingetragen 2022-05-16
|
Mit meinem Tipp wirst Du die Spannbäume so charakterisieren können, dass sie einfach abzuzählen sind. Voraussetzung dafür ist natürlich, dass Du auf die Tipps auch tatsächlich eingehst.
|
Profil
|