Жолды бояу - Path coloring

Жылы графтар теориясы, жолды бояу әдетте екі мәселенің біріне жатады:

  • Түстер проблемасы а (көп) жиынтық туралы жолдар графикте , кез келген екі жолы болатындай етіп шегін бөлісетін түрлі түстер алады. Орнатыңыз және график енгізу кезінде беріледі. Бұл тұжырымдама барабар шыңдарды бояу The қақтығыс графигі жиынтығы , яғни шыңдары бар график және барлық жұп жолдарды қосатын жиектер қатысты жиектес емес .
  • Бояу мәселесі (жоғарыдағы анықтамаға сәйкес) кез келген таңдалған (көп) жиынтық ішіндегі жолдар , бастап жолдар шыңдарының жұп жиынтығы кейбір жиынтыққа немесе көпмөлшерге тең , а деп аталады сұраныстар жиынтығы. Орнатыңыз және график енгізу кезінде беріледі. Бұл мәселе графикалық маршруттау мәселелерінің жалпы классының ерекше жағдайы болып табылады, белгілі қоңырауларды жоспарлау.

Жоғарыда аталған екі мәселеде де, әдетте, бояуда қолданылатын түстердің санын азайту мақсаты қойылады. Жолды бояудың әртүрлі нұсқаларында, болуы мүмкін қарапайым график, диграф немесе мультиграф.

Әдебиеттер тізімі

  • [1] Жолдарды бояудың және қоңырауды жоспарлаудың күрделілігі Томас Эрлебах пен Клаус Янсендікі
  • [2] NP оңтайландыру мәселелерінің жиынтығы Вигго Канн (проблема: жолдың минималды бояуы)