Кіріспе
Графтарды түске бояу, онда граф элементтеріне түстер жиынтығы тағайындалады.
Фракциялық түске бояу – граф теориясының жас саласы, фракциялық граф теориясы деп аталады. Бұл – дәстүрлі графты түске бояудың жалпылауы. Дәстүрлі графты түске бояуда графтың әр төбесіне бір түс тағайындалады, ал жиектермен байланысқан көрші төбелерге әртүрлі түстер тағайындалуы керек. Ал фракциялық түске бояуда графтың әр төбесіне түстер жиынтығы тағайындалады. Көрші төбелерге қатысты талап күшінде қалады, яғни егер екі төбе жиекпен қосылса, олардың ортақ түсі болмауы керек. Фракциялық графты түске бояуды дәстүрлі графты түске бояудың сызықтық бағдарламалау арқылы жеңілдету ретінде қарастыруға болады. Шындығында, фракциялық түске бояу мәселелері дәстүрлі түске бояу мәселелеріне қарағанда сызықтық бағдарламалау әдісіне көбірек бейім.
Қолданбалар
Фракциялық графикті бояу қолданыстарының бірі – іс-шараларды жоспарлау. Бұл жағдайда G графигі – қақтығыс графигі: G-дегі u және v түйіндері арасындағы қабырға u және v бір уақытта белсенді бола алмайтынын көрсетеді. Басқаша айтқанда, бір уақытта белсенді түйіндер жиыны G графигінде тәуелсіз жиын болуы тиіс. G-дегі оптималды фракциялық графикті бояу – ең қысқа мүмкін кесте ұсынады, онда әрбір түйін жалпы сомада (кемінде) 1 уақыт бірлігі бойы белсенді болады, ал кез келген уақытта белсенді түйіндер жиыны тәуелсіз жиын болып табылады. Егер x жоғарыдағы сызықтық бағдарламаның шешімі болса, онда біз I барлық тәуелсіз жиындарды кездейсоқ ретпен қарап шығамыз. Әр I үшін I-дегі түйіндерді уақыт бірліктеріне белсенді етеміз; ал I-де жоқ әрбір түйін белсенді емес. Нақтырақ айтқанда, G-дің әрбір түйіні сымсыз байланыс желісіндегі радиохабар таратуын білдіруі мүмкін; G-дің қабырғалары радиохабар таратулар арасындағы кедергілерді көрсетеді. Әрбір радиохабар таратуы жалпы сомада 1 уақыт бірлігі бойы белсенді болуы керек; оптималды фракциялық графиктің бояуы қақтығыссыз ең аз ұзындығы кестесін (немесе, балама ретінде, ең көп жолақты кеңдігі кестесін) қамтамасыз етеді.
An optimal fractional graph coloring in G then provides a shortest possible schedule, such that each node is active for (at least) 1 time unit in total, and at any point in time the set of active nodes is an independent set. If we have a solution x to the above linear program, we simply traverse all independent sets I in an arbitrary order. For each I, we let the nodes in I be active for time units; meanwhile, each node not in I is inactive. In more concrete terms, each node of G might represent a radio transmission in a wireless communication network; the edges of G represent interference between radio transmissions. Each radio transmission needs to be active for 1 time unit in total; an optimal fractional graph coloring provides a minimum length schedule (or, equivalently, a maximum bandwidth schedule) that is conflict free.
Дәстүрлі графикті бояумен салыстыру
Егер әр түйіннің 1 уақыт бірлігі бойына үздіксіз жұмыс істеуі қажет болса (үнемі қосып-өшірмей), онда дәстүрлі граф түйіндерін түстеу оптималды кестемен қамтамасыз етеді: бірінші 1 түсті түйіндер 1 уақыт бірлігі бойына жұмыс істейді, содан кейін 2 түсті түйіндер 1 уақыт бірлігі бойына жұмыс істейді, және т.б. Қайтадан, кез келген уақытта жұмыс істейтін түйіндер жиыны тәуелсіз жиын болып табылады. Жалпы, бөлшекті графты түстеу, толық емес графты түстеуге қарағанда қысқа кесте береді; интегралдылық қабыс бар. Құрылғыларды (мысалы, радио хабар таратушыларды) бірнеше рет қосу және өшіру арқасында одан да қысқа кесте табу мүмкін.