| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a gráfok színezése a speciális esete: bizonyos megszorítások mentén „színeket” (vagy számokat) rendelünk hozzá egy gráf valamilyen alkotóelemeihez. A leggyakoribb formájában a gráf csúcsaihoz történik a hozzárendelés, ez csúcsszínezés vagy egyszerűen színezés. Ha a gráf éleihez rendelünk színeket, az a gráf élszínezése, ha pedig a csúcsok és az élek is színezésre kerülnek, totális színezésről beszélhetünk. Síkbarajzolható gráf tartományszínezésénél pedig a lerajzolás tartományaihoz rendelünk színeket. A gráfszínezéseknél jó színezésnek azt tekintjük, ha a szomszédos elemek (csúcsszínezésnél az egymással összekötött csúcsok, élszínezésnél az egy csúcsból kiinduló élek, tartományszínezésnél a közös határral rendelkező területek) különböző színűek. Színezés alatt külön jelző nélkül is általában jó színezés értendő. A gráfok színezése területének kiindulópontjában a csúcsszínezés áll, és a többi színezési probléma is visszavezethető csúcsszínezésre: például egy gráf élszínezése megegyezik élgráfjának, totális színezése totális gráfjának, síkgráf tartományszínezése pedig duálisának csúcsszínezésével. Mégis, a nem-csúcsszínezési problémákat gyakran eredeti változatukban vizsgálják – ennek oka a perspektíva, egyes problémák, mint az élszínezés, egyszerűen jobban átláthatók, jobban kezelhetők eredeti formájukban. A színek hozzárendelésének hagyománya a térképek országainak színezéséből ered, ahol a tartományokat szó szerint kiszínezték. Ezt általánosították a síkba gráf tartományainak színezésére. A dualitás miatt ebből csúcsok színezése lett, amit aztán minden gráfra általánosítottak. A matematikai és számítógépes megvalósításokban jellemzően az első néhány pozitív vagy nemnegatív számot használják „színekként”. Bármilyen véges halmaz alkalmas lehet „színhalmaznak” – a színezési probléma természete csak a színek számosságán múlik, nem a minőségükön. A gráfszínezés területén számos gyakorlati alkalmazással, még több elméleti kihívással lehet találkozni. A klasszikusnak mondható problémák mellett különböző korlátok állíthatók fel a szóba jövő gráfra, a szín hozzárendelésének módjára vagy a színre magára. Jelenleg is igen aktívan kutatott terület. (hu)
- A matematika, azon belül a gráfelmélet területén a gráfok színezése a speciális esete: bizonyos megszorítások mentén „színeket” (vagy számokat) rendelünk hozzá egy gráf valamilyen alkotóelemeihez. A leggyakoribb formájában a gráf csúcsaihoz történik a hozzárendelés, ez csúcsszínezés vagy egyszerűen színezés. Ha a gráf éleihez rendelünk színeket, az a gráf élszínezése, ha pedig a csúcsok és az élek is színezésre kerülnek, totális színezésről beszélhetünk. Síkbarajzolható gráf tartományszínezésénél pedig a lerajzolás tartományaihoz rendelünk színeket. A gráfszínezéseknél jó színezésnek azt tekintjük, ha a szomszédos elemek (csúcsszínezésnél az egymással összekötött csúcsok, élszínezésnél az egy csúcsból kiinduló élek, tartományszínezésnél a közös határral rendelkező területek) különböző színűek. Színezés alatt külön jelző nélkül is általában jó színezés értendő. A gráfok színezése területének kiindulópontjában a csúcsszínezés áll, és a többi színezési probléma is visszavezethető csúcsszínezésre: például egy gráf élszínezése megegyezik élgráfjának, totális színezése totális gráfjának, síkgráf tartományszínezése pedig duálisának csúcsszínezésével. Mégis, a nem-csúcsszínezési problémákat gyakran eredeti változatukban vizsgálják – ennek oka a perspektíva, egyes problémák, mint az élszínezés, egyszerűen jobban átláthatók, jobban kezelhetők eredeti formájukban. A színek hozzárendelésének hagyománya a térképek országainak színezéséből ered, ahol a tartományokat szó szerint kiszínezték. Ezt általánosították a síkba gráf tartományainak színezésére. A dualitás miatt ebből csúcsok színezése lett, amit aztán minden gráfra általánosítottak. A matematikai és számítógépes megvalósításokban jellemzően az első néhány pozitív vagy nemnegatív számot használják „színekként”. Bármilyen véges halmaz alkalmas lehet „színhalmaznak” – a színezési probléma természete csak a színek számosságán múlik, nem a minőségükön. A gráfszínezés területén számos gyakorlati alkalmazással, még több elméleti kihívással lehet találkozni. A klasszikusnak mondható problémák mellett különböző korlátok állíthatók fel a szóba jövő gráfra, a szín hozzárendelésének módjára vagy a színre magára. Jelenleg is igen aktívan kutatott terület. (hu)
|
