| Property |
Value |
| dbo:abstract
|
- A matematika, azon belül a kombinatorika és gráfelmélet területén a Dinitz-probléma (Dinitz-sejtés, Galvin-tétel) táblázatok részletes latin négyzetté kiterjesztésérÅ‘l szóló állÃtás, amit 1979-ben állÃtott fel, majd 1994-ben igazolt. A Dinitz-probléma szerint ha adott egy n × n-es négyzetes táblázat, m különbözÅ‘ szimbólum, ahol m ≥ n, a táblázat minden cellájába az m szimbólumból kiválasztott n elemű halmaz kerül, lehetséges úgy megválasztani a cellákba kerülÅ‘ szimbólumokat (úgy cÃmkézni velük a cellákat), hogy egyetlen sorban vagy oszlopban se ismétlÅ‘djenek a cÃmkék. Megfogalmazható gráfelméleti eredményként is, eszerint a teljes páros gráf lista-élkromatikus száma éppen . Tehát ha a teljes páros gráf minden éléhez egy-egy szÃnbÅ‘l álló halmazt rendelünk, lehetséges minden egyes élhez a hozzárendelt szÃnek közül egy-egyet úgy kiválasztani, hogy az azonos csúcsból kiinduló élek közül ne legyen azonos szÃnű. Galvin általánosabb állÃtást bizonyÃt, miszerint bármely páros multigráf lista-élkromatikus száma megegyezik az élkromatikus számával. Egy általánosabb lista-élszÃnezési sejtés szerint ugyanez nem csak a páros gráfokra, hanem tetszÅ‘leges hurokmentes multigráfra igaz. Egy még általánosabb sejtés szerint pedig a karommentes gráfok listakromatikus száma minden esetben megegyezik a kromatikus számukkal. A Galvin-tétel kapcsolódik továbbá . (hu)
- A matematika, azon belül a kombinatorika és gráfelmélet területén a Dinitz-probléma (Dinitz-sejtés, Galvin-tétel) táblázatok részletes latin négyzetté kiterjesztésérÅ‘l szóló állÃtás, amit 1979-ben állÃtott fel, majd 1994-ben igazolt. A Dinitz-probléma szerint ha adott egy n × n-es négyzetes táblázat, m különbözÅ‘ szimbólum, ahol m ≥ n, a táblázat minden cellájába az m szimbólumból kiválasztott n elemű halmaz kerül, lehetséges úgy megválasztani a cellákba kerülÅ‘ szimbólumokat (úgy cÃmkézni velük a cellákat), hogy egyetlen sorban vagy oszlopban se ismétlÅ‘djenek a cÃmkék. Megfogalmazható gráfelméleti eredményként is, eszerint a teljes páros gráf lista-élkromatikus száma éppen . Tehát ha a teljes páros gráf minden éléhez egy-egy szÃnbÅ‘l álló halmazt rendelünk, lehetséges minden egyes élhez a hozzárendelt szÃnek közül egy-egyet úgy kiválasztani, hogy az azonos csúcsból kiinduló élek közül ne legyen azonos szÃnű. Galvin általánosabb állÃtást bizonyÃt, miszerint bármely páros multigráf lista-élkromatikus száma megegyezik az élkromatikus számával. Egy általánosabb lista-élszÃnezési sejtés szerint ugyanez nem csak a páros gráfokra, hanem tetszÅ‘leges hurokmentes multigráfra igaz. Egy még általánosabb sejtés szerint pedig a karommentes gráfok listakromatikus száma minden esetben megegyezik a kromatikus számukkal. A Galvin-tétel kapcsolódik továbbá . (hu)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4315 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| prop-hu:accessdate
| |
| prop-hu:title
|
- Dinitz Problem (hu)
- Dinitz Problem (hu)
|
| prop-hu:urlname
|
- DinitzProblem (hu)
- DinitzProblem (hu)
|
| prop-hu:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- A matematika, azon belül a kombinatorika és gráfelmélet területén a Dinitz-probléma (Dinitz-sejtés, Galvin-tétel) táblázatok részletes latin négyzetté kiterjesztésérÅ‘l szóló állÃtás, amit 1979-ben állÃtott fel, majd 1994-ben igazolt. A Dinitz-probléma szerint ha adott egy n × n-es négyzetes táblázat, m különbözÅ‘ szimbólum, ahol m ≥ n, a táblázat minden cellájába az m szimbólumból kiválasztott n elemű halmaz kerül, lehetséges úgy megválasztani a cellákba kerülÅ‘ szimbólumokat (úgy cÃmkézni velük a cellákat), hogy egyetlen sorban vagy oszlopban se ismétlÅ‘djenek a cÃmkék. (hu)
- A matematika, azon belül a kombinatorika és gráfelmélet területén a Dinitz-probléma (Dinitz-sejtés, Galvin-tétel) táblázatok részletes latin négyzetté kiterjesztésérÅ‘l szóló állÃtás, amit 1979-ben állÃtott fel, majd 1994-ben igazolt. A Dinitz-probléma szerint ha adott egy n × n-es négyzetes táblázat, m különbözÅ‘ szimbólum, ahol m ≥ n, a táblázat minden cellájába az m szimbólumból kiválasztott n elemű halmaz kerül, lehetséges úgy megválasztani a cellákba kerülÅ‘ szimbólumokat (úgy cÃmkézni velük a cellákat), hogy egyetlen sorban vagy oszlopban se ismétlÅ‘djenek a cÃmkék. (hu)
|
| rdfs:label
|
- Dinitz-probléma (hu)
- Dinitz-probléma (hu)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is foaf:primaryTopic
of | |
