Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Zwei Matchings ergeben Kreise gerader Länge und Pfade
Autor
Universität/Hochschule J Zwei Matchings ergeben Kreise gerader Länge und Pfade
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Themenstart: 2021-09-22

Gegeben sei ein zusammenhängender Graph $G=(V,E)$. Ich soll zeigen, dass die Zusammenhangskomponenten von $T=(V,M_1 \cup M_2)$ Kreise gerader Länge und Pfade sind, wobei $M_1,M_2$ Matchings in $G$ sind. Mein Ansatz wäre es insgesamt 3 verschiedene Fälle zu betrachten: 1. Beide Matchings sind perfekt 2. Nur ein Matching ist perfekt 3. Kein Matching ist perfekt Ist das ein möglicher Ansatz, oder gibt es eine bessere und einfachere Variante es zu zeigen? Gruß


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7312
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2021-09-23

\quoteon(2021-09-22 18:31 - tetriscyphervalo im Themenstart) Gegeben sei ein zusammenhängender Graph $G=(V,E)$. Ich soll zeigen, dass die Zusammenhangskomponenten von $T=(V,M_1 \cup M_2)$ Kreise gerader Länge und Pfade sind, wobei $M_1,M_2$ Matchings in $G$ sind. Mein Ansatz wäre es insgesamt 3 verschiedene Fälle zu betrachten: 1. Beide Matchings sind perfekt 2. Nur ein Matching ist perfekt 3. Kein Matching ist perfekt Ist das ein möglicher Ansatz, oder gibt es eine bessere und einfachere Variante es zu zeigen? Gruß \quoteoff Hallo, diese Fallunterscheidung würde ich nicht machen.


   Profil
Paddington
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.10.2015
Mitteilungen: 3
  Beitrag No.2, eingetragen 2021-09-23

Hallo, die Aussage gilt auch für nicht zusammenhängende Graphen. Überlege dir, was du über den Grad der Knoten in \(T\) aussagen kannst.


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.3, vom Themenstarter, eingetragen 2021-09-23

\quoteon(2021-09-23 09:05 - StrgAltEntf in Beitrag No. 1) Hallo, diese Fallunterscheidung würde ich nicht machen. \quoteoff Was wäre eine mögliche alternative? \quoteon(2021-09-23 09:39 - Paddington in Beitrag No. 2) Hallo, die Aussage gilt auch für nicht zusammenhängende Graphen. Überlege dir, was du über den Grad der Knoten in \(T\) aussagen kannst. \quoteoff Der Grad der Knoten in T ist $\leq 2$, da in einem Matching ein Knoten nur zu einer Kante inzident sein kann, und da die Matchings nicht bedingt disjunkt sind, kann es auch vorkommen, dass ein Knoten nur Grad 1 hat, bzw. Grad 0, falls sie zu keiner Kante inzident sind. Wie kann ich hier fortfahren?


   Profil
Paddington
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.10.2015
Mitteilungen: 3
  Beitrag No.4, eingetragen 2021-09-23

Jede Zusammenhangskomponente ist also ein zusammenhängender Teilgraph, in dem jeder Knoten höchstens den Grad 2 hat. Hier sind genau 3 Fälle möglich: 1) Es handelt sich um einen isolierten Knoten und damit um einen Pfad der Länge 0. 2) Es gibt mindestens einen Knoten mit Grad 1. Überlege dir, dass dann genau 2 Knoten mit Grad 1 existieren. Folgere, dass es sich um einen Pfad handelt. 3) Alle Knoten haben den Grad 2, also handelt es sich um einen Kreis. Überlege dir, welche Kreiskanten zu \( M_1\) bzw. \(M_2\) gehören und folgere daraus, dass die Länge gerade sein muss.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7312
Wohnort: Milchstraße
  Beitrag No.5, eingetragen 2021-09-23

\quoteon(2021-09-23 12:37 - tetriscyphervalo in Beitrag No. 3) \quoteon(2021-09-23 09:05 - StrgAltEntf in Beitrag No. 1) Hallo, diese Fallunterscheidung würde ich nicht machen. \quoteoff Was wäre eine mögliche alternative? \quoteoff Die Fallunterscheidung nicht zu machen 😃 @Paddington: Willkommen auf dem Matheplaneten! (Übrigens hast du aus Versehen ungerade geschrieben.)


   Profil
Paddington
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.10.2015
Mitteilungen: 3
  Beitrag No.6, eingetragen 2021-09-23

@StrgAltEntf: Danke, ich habs korrigiert!


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.7, vom Themenstarter, eingetragen 2021-09-23

@StrgAltEnf: Na wenn du es sagst 👌 @Paddington: Danke für deine Hilfe


   Profil
tetriscyphervalo hat die Antworten auf ihre/seine Frage gesehen.
tetriscyphervalo hat selbst das Ok-Häkchen gesetzt.

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-2021 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]