In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Tutteova věta (cs)
- Satz von Tutte (de)
- Teorema di Tutte (it)
- タットの定理 (ja)
- Tutte theorem (en)
- Теорема Татта о паросочетаниях (ru)
- 塔特定理 (zh)
- Теорема Татта (uk)
|
| rdfs:comment
| - Tutteho věta v matematické teorii grafů charakterizuje grafy s perfektním párováním. Je pojmenována po Williamu Thomasovi Tutteovi. Jedná se o zobecnění Hallovy věty. (cs)
- Nella disciplina matematica della teoria dei grafi il teorema di Tutte, che prende nome da William Thomas Tutte, è una caratterizzazione dei grafi con accoppiamenti perfetti. È una generalizzazione del teorema dei matrimoni ed è un caso particolare della . (it)
- In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula. (en)
- 数学の分科、グラフ理論におけるタットの定理（タットのていり、英: Tutte theorem）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またの特殊な場合である。 (ja)
- Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа. Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф, , имеет не более связных компонент с нечётным числом вершин. Установлена Уильямом Таттом. (ru)
- Теоре́ма Та́тта про парування дає необхідну і достатню умову на існування досконалого парування у графі. Названа на честь Вільяма Томаса Татта. Ця теорема узагальнює теорему Холла про одруження для двочасткових графів і є окремим випадком формули Татта — Бержа. (uk)
- 在图论中，塔特定理（Tutte theorem）是： 图 有匹配，当且仅当 。 其中 、是图的奇数元件的数量（有奇数个頂點的连通元件）。 (zh)
- Der Satz von Tutte (nach William Thomas Tutte) ist ein mathematischer Satz aus der Graphentheorie. Er lautet: Ein Graph G=(V,E) hat genau dann ein perfektes Matching, wenn für jede Teilmenge S der Knotenmenge V die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von G-S höchstens gleich |S|, der Anzahl der Knoten in S, ist. Ein einfacherer Beweis als der von Tutte stammt von Tibor Gallai (1963). (de)
|
| differentFrom
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| date
| |
| reason
| - how exactly is it a generalization? (en)
|
| has abstract
| - Tutteho věta v matematické teorii grafů charakterizuje grafy s perfektním párováním. Je pojmenována po Williamu Thomasovi Tutteovi. Jedná se o zobecnění Hallovy věty. (cs)
- Der Satz von Tutte (nach William Thomas Tutte) ist ein mathematischer Satz aus der Graphentheorie. Er lautet: Ein Graph G=(V,E) hat genau dann ein perfektes Matching, wenn für jede Teilmenge S der Knotenmenge V die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von G-S höchstens gleich |S|, der Anzahl der Knoten in S, ist. 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 q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen G=(V,E), so lässt sich die zweite Bedingung kurz schreiben als |S| ≥ q(G-S) für alle Teilmengen S von V. Ein einfacherer Beweis als der von Tutte stammt von Tibor Gallai (1963). (de)
- Nella disciplina matematica della teoria dei grafi il teorema di Tutte, che prende nome da William Thomas Tutte, è una caratterizzazione dei grafi con accoppiamenti perfetti. È una generalizzazione del teorema dei matrimoni ed è un caso particolare della . (it)
- In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula. (en)
- 数学の分科、グラフ理論におけるタットの定理（タットのていり、英: Tutte theorem）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またの特殊な場合である。 (ja)
- Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа. Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф, , имеет не более связных компонент с нечётным числом вершин. Установлена Уильямом Таттом. (ru)
- Теоре́ма Та́тта про парування дає необхідну і достатню умову на існування досконалого парування у графі. Названа на честь Вільяма Томаса Татта. Ця теорема узагальнює теорему Холла про одруження для двочасткових графів і є окремим випадком формули Татта — Бержа. (uk)
- 在图论中，塔特定理（Tutte theorem）是： 图 有匹配，当且仅当 。 其中 、是图的奇数元件的数量（有奇数个頂點的连通元件）。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is rdfs:seeAlso
of | |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is known for
of | |
| is known for
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)