Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Bipartiter Graph
Autor
Universität/Hochschule Bipartiter Graph
adghl
Junior Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7827
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3568
  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
adghl hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]