In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte-Berge formula.

PropertyValue
dbpprop:abstract
  • In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte-Berge formula.
  • Der Satz von Tutte ist ein mathematischer Satz aus der Graphentheorie. Er lautet: Ein Graph <math>G=(V,E)</math> hat genau dann ein perfektes Matching, wenn für jede Teilmenge S der Knotenmenge V ihre Mächtigkeit |S| größer ist als die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von G-S. G-S bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von S und ihre inzidenten Kanten aus G löscht. Bezeichnet man mit <math>q(G)</math> die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen <math>G=(V,E)</math>, so lässt sich die zweite Bedingung kurz schreiben als <math>|S|\geq q(G-S)</math> für alle Teilmengen S von V.
  • A Tutte-tétel arról szól, hogy mikor van egy nem feltétlenül páros gráfban teljes párosítás. Először Tutte bizonyította be 1947-ben, majd Gallai Tibor adott rá elemi bizonyítást. Teljes párosításra tétel még a Frobenius-tétel.
dbpprop:hasPhotoCollection
dbpprop:p
  • 84 (xsd:integer)
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte-Berge formula.
  • Der Satz von Tutte ist ein mathematischer Satz aus der Graphentheorie. Er lautet: Ein Graph <math>G=(V,E)</math> hat genau dann ein perfektes Matching, wenn für jede Teilmenge S der Knotenmenge V ihre Mächtigkeit |S| größer ist als die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von G-S. G-S bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von S und ihre inzidenten Kanten aus G löscht.
  • A Tutte-tétel arról szól, hogy mikor van egy nem feltétlenül páros gráfban teljes párosítás. Először Tutte bizonyította be 1947-ben, majd Gallai Tibor adott rá elemi bizonyítást. Teljes párosításra tétel még a Frobenius-tétel.
rdfs:label
  • Tutte theorem
  • Satz von Tutte
  • Tutte-tétel
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of