| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy gráf élszínezése során színeket rendelnek hozzá a gráf éleihez. Általában jó élszínezésekkel foglalkoznak, melyek során az ugyanabból a csúcsból kiinduló élek mindig különböző színűek. Például a jobb oldali ábrán látható élszínezés három színt (piros, kék, zöld) használ. Az élszínezés a gráfok lehetséges színezéseinek csak egyetlen típusa. Az élszínezési probléma azt vizsgálja, hogy jól színezhetők-e adott gráf élei legfeljebb k különböző színnel, adott k-ra, illetve a lehető legkevesebb szín felhasználásával. Az adott gráf éleihez szükséges minimális színek számát a gráf élkromatikus számának vagy kromatikus indexének nevezik. Az illusztráción látható gráf élei kiszínezhetők három színnel, de kettővel nem, ezért a gráf élkromatikus száma három. A Vizing-tétel értelmében az egyszerű gráf élszínezéséhez szükséges színek száma vagy a maximális fokszáma, Δ vagy Δ+1. Egyes gráfok esetében, mint a páros gráfok vagy magas fokszámú síkbarajzolható gráfok, a kromatikus index mindig Δ, multigráfok esetén pedig akár 3Δ/2 is lehet. Léteznek polinom idejű algoritmusok páros gráfok optimális színezésének, illetve nem páros egyszerű gráfok legfeljebb Δ+1-színezésének előállítására; az optimális élszínezés általános esetben azonban feladat és a legjobb ismert algoritmusok is exponenciális idejűek. Az élszínezési problémának számos olyan változatát tanulmányozták, ahol a színek hozzárendelésekor a szomszédosság elkerülése mellett egyéb feltételeknek is teljesülniük kell. Az élszínezések gyakorlati szerepet kapnak az ütemezési problémákban és az optikai hálózatok frekvenciakiosztásában. (hu)
- A matematika, azon belül a gráfelmélet területén egy gráf élszínezése során színeket rendelnek hozzá a gráf éleihez. Általában jó élszínezésekkel foglalkoznak, melyek során az ugyanabból a csúcsból kiinduló élek mindig különböző színűek. Például a jobb oldali ábrán látható élszínezés három színt (piros, kék, zöld) használ. Az élszínezés a gráfok lehetséges színezéseinek csak egyetlen típusa. Az élszínezési probléma azt vizsgálja, hogy jól színezhetők-e adott gráf élei legfeljebb k különböző színnel, adott k-ra, illetve a lehető legkevesebb szín felhasználásával. Az adott gráf éleihez szükséges minimális színek számát a gráf élkromatikus számának vagy kromatikus indexének nevezik. Az illusztráción látható gráf élei kiszínezhetők három színnel, de kettővel nem, ezért a gráf élkromatikus száma három. A Vizing-tétel értelmében az egyszerű gráf élszínezéséhez szükséges színek száma vagy a maximális fokszáma, Δ vagy Δ+1. Egyes gráfok esetében, mint a páros gráfok vagy magas fokszámú síkbarajzolható gráfok, a kromatikus index mindig Δ, multigráfok esetén pedig akár 3Δ/2 is lehet. Léteznek polinom idejű algoritmusok páros gráfok optimális színezésének, illetve nem páros egyszerű gráfok legfeljebb Δ+1-színezésének előállítására; az optimális élszínezés általános esetben azonban feladat és a legjobb ismert algoritmusok is exponenciális idejűek. Az élszínezési problémának számos olyan változatát tanulmányozták, ahol a színek hozzárendelésekor a szomszédosság elkerülése mellett egyéb feltételeknek is teljesülniük kell. Az élszínezések gyakorlati szerepet kapnak az ütemezési problémákban és az optikai hálózatok frekvenciakiosztásában. (hu)
|
