| Property |
Value |
| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. Bár a de Bruijn–Erdős-tételnek számos különböző bizonyítása létezik, mindegyik a kiválasztási axiómára alapul. A tétel alkalmazásai közé tartozik a négyszíntétel és a Dilworth-tétel kiterjesztése véges gráfokról és részbenrendezett halmazokról végtelenre, továbbá a sík kromatikus számával foglalkozó Hadwiger–Nelson-probléma redukálása véges gráfokra vonatkozó problémára. A tétel általánosítható véges számú színről olyan színhalmazokra, melynek számossága kardinális szám (wd). (hu)
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. Bár a de Bruijn–Erdős-tételnek számos különböző bizonyítása létezik, mindegyik a kiválasztási axiómára alapul. A tétel alkalmazásai közé tartozik a négyszíntétel és a Dilworth-tétel kiterjesztése véges gráfokról és részbenrendezett halmazokról végtelenre, továbbá a sík kromatikus számával foglalkozó Hadwiger–Nelson-probléma redukálása véges gráfokra vonatkozó problémára. A tétel általánosítható véges számú színről olyan színhalmazokra, melynek számossága kardinális szám (wd). (hu)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 21161 (xsd:nonNegativeInteger)
- 21205 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
|
- 22265480 (xsd:integer)
- 25467823 (xsd:integer)
|
| prop-hu:author1Link
|
- Nicolaas Govert de Bruijn (hu)
- Nicolaas Govert de Bruijn (hu)
|
| prop-hu:author2Link
|
- Erdős Pál (hu)
- Erdős Pál (hu)
|
| prop-hu:date
|
- 20160310003706 (xsd:decimal)
|
| prop-hu:first
|
- Paul (hu)
- Nicolaas Govert (hu)
- Paul (hu)
- Nicolaas Govert (hu)
|
| prop-hu:last
|
- de Bruijn (hu)
- Erdős (hu)
- de Bruijn (hu)
- Erdős (hu)
|
| prop-hu:url
| |
| prop-hu:wikiPageUsesTemplate
| |
| prop-hu:year
| |
| dct:subject
| |
| rdfs:comment
|
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. (hu)
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. (hu)
|
| rdfs:label
|
- De Bruijn–Erdős-tétel (gráfelmélet) (hu)
- De Bruijn–Erdős-tétel (gráfelmélet) (hu)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
