ในทฤษฎีกราฟการระบายสีเส้นทางเป็นประเภทหนึ่งของการระบายสีกราฟโดยกำหนดสี (หรือความยาวคลื่น ) ให้กับชุดของเส้นทางในกราฟ โดยที่เส้นทางสองเส้นใดๆ ที่มีขอบ ร่วมกัน จะได้รับสีที่แตกต่างกัน โดยทั่วไปแล้ววัตถุประสงค์คือการลดจำนวนสีที่ใช้ การระบายสีเส้นทางได้รับแรงบันดาลใจจากปัญหาการจัดสรรแบนด์วิดท์แสงให้กับคำขอการสื่อสารในเครือข่ายออปติคอลทั้งหมดที่ใช้การมัลติเพล็กซ์แบบแบ่งความยาวคลื่น (WDM) ^{[ 1 ]}

การระบายสีเส้นทางอาจหมายถึง ปัญหา WAหรือปัญหา RWA ก็ได้

ในปัญหาการกำหนดความยาวคลื่น (หรือปัญหา WA ) อินพุตประกอบด้วยกราฟและ ชุด เส้นทาง(หลายชุด)ที่กำหนดไว้แล้วบนงานคือการกำหนดสีให้กับเส้นทางในโดยที่เส้นทางสองเส้นใดๆ ที่มีขอบร่วมกันในจะได้รับสีที่แตกต่างกัน^{[ 2 ]}${\displaystyle G}$${\displaystyle P}$${\displaystyle G}$${\displaystyle P}$${\displaystyle G}$

สูตรนี้เทียบเท่ากับการระบายสีจุดยอด ของ กราฟความขัดแย้งของซึ่งมีจุดยอดหนึ่งจุดสำหรับแต่ละเส้นทางในและมีขอบระหว่างจุดยอดสองจุดเมื่อใดก็ตามที่เส้นทางที่สอดคล้องกันมีขอบร่วมกันใน^{[ 1 ]}${\displaystyle P}$${\displaystyle P}$${\displaystyle G}$

ในปัญหาการกำหนดเส้นทางและการจัดสรรความยาวคลื่น (หรือปัญหาการกำหนดเส้นทางความยาวคลื่นหรือปัญหา RWA ) อินพุตประกอบด้วยกราฟและชุดคำขอโดยแต่ละคำขอเป็นคู่ของโหนดที่จะเชื่อมต่อกัน สำหรับแต่ละคำขอ อัลกอริทึมจะต้องเลือกเส้นทางที่เชื่อมต่อจุดปลายทั้งสองและกำหนดสีให้กับเส้นทางนั้น โดยเส้นทางที่ใช้ขอบร่วมกันจะได้รับสีที่แตกต่างกัน^{[ 2 ]}${\displaystyle G}$${\displaystyle R}$

ปัญหา RWA จึงถูกแยกย่อยออกเป็นสองปัญหาย่อย ได้แก่ปัญหาการกำหนดเส้นทางในการเลือกเส้นทางสำหรับแต่ละคำขอ และปัญหา WA ในการระบายสีเส้นทางที่ได้^{[ 1 ]}

โดยทั่วไปแล้ว ในกราฟที่มีเส้นทางหลายเส้นทางระหว่างคู่โหนด ปัญหาเหล่านี้จะเกิดปฏิสัมพันธ์กัน ทำให้ RWA มีความซับซ้อนมากกว่า WA เพียงอย่างเดียว

ใน เครือข่าย ต้นไม้เส้นทางที่เชื่อมต่อโหนดสองโหนดใดๆ จะมีเอกลักษณ์เฉพาะ ดังนั้น ปัญหาย่อยการกำหนดเส้นทางจึงกลายเป็นเรื่องง่าย และการกำหนดเส้นทางความยาวคลื่นในต้นไม้จะลดลงเหลือเพียงปัญหา WA ^{[ 1 ]}ด้วยเหตุนี้ การวิจัยเกี่ยวกับการระบายสีเส้นทางจึงมักมุ่งเน้นไปที่โทโพโลยีต้นไม้

ภาระของขอบถูกกำหนดให้เป็นจำนวนเส้นทางที่ผ่านขอบนั้น และภาระของชุดเส้นทางคือภาระสูงสุดของขอบทั้งหมด ภาระจะให้ขอบเขตล่างของจำนวนสีที่ต้องการ^{[ 1 ]}${\displaystyle L}$

การระบายสีเส้นทางสามารถศึกษาได้ทั้งในการตั้งค่าแบบไม่มีทิศทางและแบบมีทิศทาง (มีทิศทาง) ^{[ 2 ]}

• ในการระบายสีเส้นทางแบบไม่มีทิศทางกราฟจะเป็นกราฟแบบไม่มีทิศทาง และเส้นทางก็จะเป็นแบบไม่มีทิศทางเช่นกัน เส้นทางสองเส้นจะขัดแย้งกันหากมีขอบร่วมกัน${\displaystyle G}$
• ในการระบายสีเส้นทางแบบมีทิศทางกราฟจะเป็นกราฟสองทิศทาง (แต่ละขอบที่ไม่มีทิศทางจะถูกแทนที่ด้วยขอบที่มีทิศทางสองเส้นในทิศทางตรงกันข้าม) และเส้นทางจะเป็นเส้นทางที่มีทิศทาง เส้นทางที่มีทิศทางสองเส้นจะขัดแย้งกันก็ต่อเมื่อทั้งสองเส้นทางมีขอบที่มีทิศทางร่วมกันในทิศทางเดียวกันเท่านั้น

รูปแบบที่มีทิศทางจะจำลองเครือข่ายที่แต่ละลิงก์ใยแก้วนำแสงมีกำลังการผลิตแยกต่างหากสำหรับแต่ละทิศทางการส่งสัญญาณ

การระบายสีเส้นทางเป็นปัญหา NP-hard สำหรับทั้งเครือข่าย วงแหวนแบบไม่มีทิศทางและแบบมีทิศทางสำหรับต้นไม้: ^{[ 1 ] [ 2 ]}

• การระบายสีเส้นทางแบบไม่มีทิศทางในกราฟรูปดาวเทียบเท่ากับการระบายสีขอบของกราฟหลายเส้นและด้วยเหตุนี้จึงเป็นปัญหา NP-hard
• การระบายสีเส้นทางแบบมีทิศทางเป็นปัญหา NP-hard แม้แต่สำหรับต้นไม้สองทิศทางแบบไบนารี
• การระบายสีเส้นทางสามารถแก้ไขได้อย่างเหมาะสมที่สุดในเวลาพหุนามสำหรับต้นไม้ที่มีดีกรีจำกัด หรือเมื่อจำนวนเส้นทางที่สัมผัสโหนดใด ๆ มีค่าเท่ากับสำหรับบางค่า${\displaystyle O((\log n)^{1-\varepsilon })}$${\displaystyle \varepsilon >0}$

สำหรับต้นไม้แบบไม่มีทิศทาง อัลกอริทึมแบบโลภที่ใช้การระบายสีขอบของมัลติกราฟทำให้ได้อัตราส่วนการประมาณค่าที่ 3/2 ซึ่งถือว่าแม่นยำ^{[ 1 ]}นอกจากนี้ยังมีอัลกอริทึมที่มีอัตราส่วนการประมาณค่าสัมบูรณ์ 4/3 และอัตราส่วนการประมาณค่าเชิงอะซิมโทติก 1.1 อีกด้วย^{[ 2 ]}

สำหรับต้นไม้แบบสองทิศทาง อัลกอริทึมโลภแบบกำหนดได้จะบรรลุขอบเขตบนของสีสำหรับเส้นทางของการโหลดอัลกอริทึมแบบสุ่มจะปรับปรุงสิ่งนี้ให้เป็นสีสำหรับต้นไม้แบบสองทิศทางไบนารี^{[ 1 ]}${\displaystyle 5L/3}$${\displaystyle L}$${\displaystyle 7L/5+o(L)}$

การระบายสีเส้นทางมีความเกี่ยวข้องอย่างใกล้ชิดกับการจัดตารางการโทรซึ่งเป็นการขยายปัญหาโดยการนำข้อกำหนดแบนด์วิดท์และระยะเวลาการโทรเข้ามาใช้ เมื่อข้อกำหนดแบนด์วิดท์ ความจุขอบ และระยะเวลาการโทรทั้งหมดเท่ากับ 1 การจัดตารางการโทรจะลดลงเหลือปัญหา RWA โดยสีจะสอดคล้องกับช่วงเวลา^{[ 2 ]}

• หนังสือรวบรวมปัญหาการหาค่าเหมาะสมที่สุดแบบ NPโดย Viggo Kann (ปัญหา: การระบายสีเส้นทางขั้นต่ำ)

บทความเกี่ยวกับทฤษฎีกราฟนี้ ยัง ไม่สมบูรณ์คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป

• วี
• ที
• อี