| dbo:abstract
|
- Der schwache Perfekte-Graphen-Satz (oder auch nur Perfekte-Graphen-Satz und Satz von Lovász) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von László Lovász bewiesen. „Ein Graph G ist genau dann perfekt, wenn sein komplementärer Graph Gc perfekt ist.“ Im Folgenden bezeichne für einen Graphen G seine Eckenmenge, einen von induzierter Teilgraphen, die chromatische Zahl, die Cliquenzahl, die Stabilitätszahl und die Zusammenhangszahl. Die folgenden Bedingungen sind dann (formal) äquivalent: 1.
* für alle (G perfekt). 2.
* für alle (Gc perfekt). 3.
* für alle . (de)
- In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. (en)
- Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами. (ru)
- 在图论中，完美图定理（由洛瓦兹·拉兹洛证明László Lovász （, ））断言：一个无向图是的当且仅当其補圖也是完美的。这个结论一度是提出的猜想。它有时也被称为弱完美图定理，以和作区分。强完美图定理通过来刻画完美图。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12870 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
|
- László Lovász (en)
- Claude Berge (en)
|
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1961 (xsd:integer)
- 1963 (xsd:integer)
- 1972 (xsd:integer)
|
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. (en)
- Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами. (ru)
- 在图论中，完美图定理（由洛瓦兹·拉兹洛证明László Lovász （, ））断言：一个无向图是的当且仅当其補圖也是完美的。这个结论一度是提出的猜想。它有时也被称为弱完美图定理，以和作区分。强完美图定理通过来刻画完美图。 (zh)
- Der schwache Perfekte-Graphen-Satz (oder auch nur Perfekte-Graphen-Satz und Satz von Lovász) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von László Lovász bewiesen. „Ein Graph G ist genau dann perfekt, wenn sein komplementärer Graph Gc perfekt ist.“ Im Folgenden bezeichne für einen Graphen G seine Eckenmenge, einen von induzierter Teilgraphen, die chromatische Zahl, die Cliquenzahl, die Stabilitätszahl und die Zusammenhangszahl. Die folgenden Bedingungen sind dann (formal) äquivalent: (de)
|
| rdfs:label
|
- Schwacher Perfekte-Graphen-Satz (de)
- Perfect graph theorem (en)
- Теорема о совершенных графах (ru)
- 完美图定理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
