การระบายสีขอบช่วง

Q: ผลลัพธ์บางส่วน

ถ้า กราฟที่ไม่มีสามเหลี่ยม G=(V,E) มีการระบายสีแบบช่วง t แล้ว t ≤ |V|−1 Asratyan และ Kamalian พิสูจน์แล้วว่าถ้า G สามารถระบายสีแบบช่วงได้ χ'(G)=∆(G) [ 1 ] [ 3 ]

ในทฤษฎีกราฟการระบายสีขอบแบบช่วง (Interval Edge Coloring ) เป็นรูปแบบหนึ่งของการระบายสีขอบโดยที่ขอบแต่ละด้านจะถูกกำหนดป้ายกำกับด้วยจำนวนเต็มในช่วงที่กำหนด โดยจำนวนเต็มทุกตัวในช่วงนั้นจะถูกใช้โดยขอบอย่างน้อยหนึ่งด้าน และที่แต่ละจุดยอด ป้ายกำกับที่ปรากฏบนขอบที่เชื่อมต่อกับจุดยอดนั้นจะประกอบเป็นชุดตัวเลขที่แตกต่างกันต่อเนื่องกัน

ประวัติศาสตร์

แนวคิดของการระบายสีขอบต่อเนื่องได้รับการแนะนำด้วยศัพท์เฉพาะ ' การระบายสีขอบแบบช่วง'โดย Asratian และ Kamalian ในปี 1987 ในบทความของพวกเขาเรื่อง "การระบายสีขอบแบบช่วงของกราฟหลายเส้น" ^{[ 1 ]}นับตั้งแต่มีการแนะนำการระบายสีขอบแบบช่วงของกราฟ นักคณิตศาสตร์ได้ทำการตรวจสอบการมีอยู่ของกราฟที่สามารถระบายสีขอบแบบช่วงได้ เนื่องจากไม่ใช่ทุกกราฟที่จะอนุญาตให้ระบายสีขอบแบบช่วงได้ กลุ่มกราฟอย่างง่ายที่อนุญาตให้ระบายสีขอบแบบช่วงได้คือกราฟสมบูรณ์ที่มีอันดับคู่ และตัวอย่างค้านของกลุ่มกราฟดังกล่าวได้แก่กราฟสมบูรณ์ที่มีอันดับคี่ กราฟที่เล็กที่สุดที่ไม่สามารถระบายสีแบบช่วงได้คือกราฟคู่ที่มี 28 จุดยอดและดีกรีสูงสุด 21 ซึ่ง Sevast'janov ค้นพบว่าไม่สามารถระบายสีแบบช่วงได้ แม้ว่าการระบายสีแบบช่วงของกราฟที่มีดีกรีสูงสุดอยู่ระหว่างสี่ถึงสิบสองจะยังไม่เป็นที่ทราบแน่ชัด

Asratyan & Kamalyan (1987)พิสูจน์ว่าถ้ากราฟสามารถระบายสีแบบช่วงได้ จำนวนสีของขอบจะน้อยกว่าหรือเท่ากับลบหนึ่งจำนวนจุดยอด และยังสังเกตอีกว่าถ้า G เป็นกราฟปกติแบบ r แล้ว G จะมีการระบายสีแบบช่วงได้ก็ต่อเมื่อ G มีการระบายสีขอบแบบ r ที่เหมาะสม^{[ 1 ]}

การระบายสีขอบแบบช่วงได้รับการศึกษาในกราฟปกติกราฟสองส่วนทั้งที่เป็นกราฟปกติและไม่ปกติ กราฟระนาบ และส่วนขยายอื่นๆ ที่ริเริ่มขึ้นในการระบายสีขอบแบบช่วง

คำนิยาม

ให้Gเป็นกราฟช่วง แบบง่าย การระบายสีขอบของกราฟ G ด้วยสี 1, 2, ..., tเรียกว่า "การระบายสีช่วง t" ถ้าสำหรับแต่ละi ∈ {1, 2, ..., t } มีขอบอย่างน้อยหนึ่งขอบของGที่ถูกระบายสีด้วยiและสีของขอบที่เชื่อมต่อกับจุดยอดใด ๆ ของGนั้นแตกต่างกันและประกอบเป็นช่วงของจำนวนเต็ม^{[ 2 ]}หรืออีกนัยหนึ่ง การระบายสีขอบช่วงถูกกำหนดดังนี้: การระบายสีขอบของกราฟGด้วยสี 1 ... tเป็น ' การระบายสีช่วง t'ถ้าใช้สีทั้งหมด และสีของขอบที่เชื่อมต่อกับจุดยอดแต่ละจุดของGนั้นแตกต่างกันและประกอบเป็นช่วงของจำนวนเต็ม กราฟGเป็น "กราฟที่สามารถระบายสีช่วงได้" ถ้าGมีการระบายสีช่วง t สำหรับจำนวนเต็มบวกt บางตัว ให้Nเป็นเซตของกราฟที่สามารถระบายสีช่วงได้ทั้งหมด สำหรับกราฟG ∈ Nค่าต่ำสุดและค่าสูงสุดของtที่ทำให้Gมี การระบายสี ขอบ แบบช่วง t จะถูกแทนด้วยw ( G ) และW ( G ) ตามลำดับ การระบายสีขอบแบบช่วงของกราฟเรียกว่าการระบายสีขอบแบบช่วงที่ยุติธรรม หากชั้นสีสองชั้นใดๆ ของกราฟแตกต่างกันไม่เกินหนึ่ง

เซตของสีของขอบที่เชื่อมต่อกับจุดยอด (x) เรียกว่า สเปกตรัมของ ( x ) เรากล่าวว่าเซตย่อยRของจุดยอดของGมี คุณสมบัติ iถ้ามีการระบายสีขอบt ที่เหมาะสม ของGซึ่งเป็นช่วงเหนือ R

ผลลัพธ์บางส่วน

ถ้ากราฟที่ไม่มีสามเหลี่ยม G=(V,E) มีการระบายสีแบบช่วง t แล้ว t ≤ |V|−1 Asratyan และ Kamalian พิสูจน์แล้วว่าถ้า G สามารถระบายสีแบบช่วงได้ χ'(G)=∆(G) ^{[ 1 ]}^{[ 3 ]}

Petrosyan ศึกษาการระบายสีช่วงของกราฟสมบูรณ์และลูกบาศก์ n มิติ และแสดงให้เห็นว่าถ้า n ≤ t ≤ n(n+1)/2 แล้วลูกบาศก์ n มิติ Qn จะมีการระบายสีช่วง t ^{[ 2 ]} Axenovich พิสูจน์ว่าการแบ่งสามเหลี่ยมระนาบนอกทั้งหมดที่มีจุดยอดมากกว่าสามจุดและไม่มีสามเหลี่ยมคั่นสามารถระบายสีช่วงได้^{[ 4 ]} ถ้าGเป็นกราฟปกติ w(G)=∆(G) และ G มีการระบายสีช่วง t สำหรับทุก t, w(G) ≤ t ≤ W(G)

การระบายสีขอบช่วงของกราฟสมบูรณ์^{[ 2 ]}

กราฟสมบูรณ์สามารถระบายสีแบบช่วงได้ก็ต่อเมื่อจำนวนจุดยอดของกราฟเป็นจำนวนคู่
ถ้า n = _p 2 ^qโดยที่ p เป็นจำนวนคี่ q เป็นจำนวนบวก และ 2n−1 ≤ t ≤ 4n−2−p−q แล้วกราฟสมบูรณ์K _2nจะมีการระบายสีแบบช่วง t
ถ้า F เป็นเซตของขอบอย่างน้อย n เส้นที่เชื่อมต่อกับจุดยอด v จุดหนึ่งของกราฟสมบูรณ์K _2n+1แล้วK _2n+1 −Fจะมีการระบายสีแบบช่วง
ถ้า F เป็นการจับคู่สูงสุดของกราฟสมบูรณ์K _2n+1โดยที่ n≥2 แล้วK _2n+1 −Fจะไม่มีการระบายสีช่วง
ถ้าn ≤ t ≤ ${\frac {n(n+1)}{2}}$ แล้วลูกบาศก์ n มิติ Qn จะมีการระบายสีแบบช่วง t

การระบายสีขอบช่วงของกราฟสองส่วน

สำหรับ m, n ∈ N ใดๆ กราฟสองส่วนสมบูรณ์K _m,nสามารถระบายสีแบบช่วงได้ และ

(1) w ( K _m,n ) = m + n − gcd(m, n)

(2) W ( K _m,n ) = m + n − 1,

(3) ถ้า w ( K _m,n ) ≤ t ≤ W ( K _m,n ) แล้วK _m,nจะมีการระบายสีช่วง t

ถ้า G เป็นกราฟสองส่วน แล้ว χ′(G) = ∆(G)
ถ้า G ∈ N แล้ว G[ K _m,n ] ∈ N สำหรับ m, n ∈ N ใดๆ ยิ่งไปกว่านั้น สำหรับ m, n ∈ N ใดๆ เรามี

w (G[ K _m,n ]) ≤ (w(G) + 1)(m + n) − 1 และ W (G[ K _m,n ]) ≥ (W(G) + 1)(m + n) − 1

ถ้า G เป็นกราฟสองส่วนที่เชื่อมต่อกัน และ G ∈ N แล้ว W(G) ≤ diam(G) (∆(G) − 1) + 1

การระบายสีขอบช่วงของกราฟระนาบ^{[ 4 ]}

การระบายสีขอบช่วงของกราฟระนาบนอกได้รับการตรวจสอบโดย Giaro และ Kubale และพิสูจน์แล้วว่ากราฟสองส่วนระนาบนอกทั้งหมดสามารถระบายสีช่วงได้^{[ 5 ]}

ถ้าG = G ₁ eG ₂โดยที่G ₁และG ₂มีการระบายสีแบบช่วงซึ่งeมีป้ายกำกับภายนอก แล้วGก็มีการระบายสีแบบช่วงเช่น กัน

บทพิสูจน์:ให้c ₁เป็นการระบายสีช่วงของ 'G ₁ ' โดยที่e=xyได้รับป้ายกำกับที่เล็กที่สุดในบรรดาขอบที่เชื่อมต่อกับxและyกำหนดให้ c ₁ (e)=0 พิจารณาการระบายสีช่วงc ₁ของG ₁โดยที่eได้รับป้ายกำกับที่ใหญ่ที่สุดในบรรดาขอบที่เชื่อมต่อกับxและyสมมติว่าc ₂ (e)=iจากนั้นเราสร้างการระบายสีช่วงcของGเป็นc(e') = c ₁ (e') ถ้า(e') ∈E(G ₁ ) หรือ c (e') = c ₂ (e') - iถ้า (e') ∈ E(G ₁ )

ถ้าGเป็นกราฟระนาบนอกที่มีจำนวนจุดอย่างน้อย 4 จุด โดยไม่มีสามเหลี่ยมคั่นกลาง กราฟนั้นจะมีสีแบบช่วง (interval coloring)
ให้ G เป็นกราฟที่ได้จากการลบเส้นแบ่งบางเส้นภายใต้การระบายสีแบบช่วงของกราฟHแล้วGก็สามารถระบายสีแบบช่วงได้เช่นกัน
ให้Hเป็นการแบ่งรูปสามเหลี่ยมบนระนาบนอกโดยไม่มีรูปสามเหลี่ยมแยกออกจากกัน และให้H = H ₁ ,----- H _mเป็นการแบ่งส่วนที่มีขอบเชื่อมต่อe ₁ ,----, e _m-1ถ้าGได้มาจากHโดยการลบขอบเชื่อมต่อบางส่วนออก G จะมีการระบายสีแบบช่วง
สำหรับกราฟGที่ สามารถระบายสีช่วงบนระนาบได้ บน จุดยอด nจุดt(G) ≤(11/6) n

การระบายสีขอบช่วงของกราฟสองส่วนแบบไบเรกูลาร์ที่มีดีกรีจุดยอดน้อย

กราฟสองส่วน (bipartite graph) เรียกว่า กราฟ (a, b)-biregular ถ้าทุกจุดยอดในส่วนหนึ่งมีดีกรี a และทุกจุดยอดในอีกส่วนหนึ่งมีดีกรี b มีการตั้งข้อสันนิษฐานว่ากราฟดังกล่าวทั้งหมดสามารถระบายสีแบบช่วงได้ Hansen พิสูจน์แล้วว่ากราฟสองส่วน G ทุกกราฟที่มี ∆(G) ≤ 3 สามารถระบายสีแบบช่วงได้

การระบายสีขอบช่วง K ที่เป็นธรรม

การระบายสีขอบแบบ k ช่วงของกราฟ เรียกว่าเป็นการระบายสีขอบแบบ k ช่วงที่เท่าเทียมกัน ถ้าเซตขอบ E ของกราฟนั้นถูกแบ่งออกเป็น K เซตย่อย E ₁ ,E ₂ ,...,E _kโดยที่ E _iเป็นเซตอิสระ และเงื่อนไข -1 ≤ E _i ≤ E _j ≤ 1 เป็นจริงสำหรับทุก 1 ≤i ≤k,1 ≤j ≤k จำนวนเต็มที่เล็กที่สุด k ที่ทำให้ G มีการระบายสีขอบแบบ k ช่วงที่เท่าเทียมกัน เรียกว่าจำนวนสีที่เท่าเทียมกันของการระบายสีขอบแบบ k ช่วงของ G และใช้สัญลักษณ์แทน $\chi _{eie}(G)$

แอปพลิเคชัน

การระบายสีขอบช่วงเวลามีแอปพลิเคชันที่หลากหลายในสาขาวิทยาศาสตร์และการจัดตารางเวลา

หนึ่งในแอปพลิเคชันพื้นฐานของการระบายสีขอบตามช่วงเวลาคือการจัดตารางเรียนโดยไม่ให้คาบเรียนชนกัน ในแอปพลิเคชันนี้ ชั่วโมงเรียนจะกลายเป็นจุดยอด และทั้งสองชั่วโมงเรียนจะใช้ขอบร่วมกันหากช่วงเวลาเดียวกัน จำนวนสีที่ใช้ในการระบายสีขอบคือจำนวนห้องเรียนที่จำเป็นในการจัดการเรียนการสอนโดยไม่ให้คาบเรียนชนกัน วิธีนี้ใช้ในทุกกรณีที่ต้องการจัดกิจกรรมสองอย่างขึ้นไปโดยหลีกเลี่ยงการชนกัน
มีการประยุกต์ใช้งานในลักษณะเดียวกันในการจัดตารางเวลาการทำงานของโปรเซสเซอร์ เช่น การจัดตารางเวลาการถ่ายโอนไฟล์ในเครือข่ายแบบกระจาย หรือการจัดตารางเวลาการทดสอบวินิจฉัยในระบบคอมพิวเตอร์หลายเครื่อง รวมถึงการจัดตารางเวลางานในระบบโอเพ่นช็อป มีการพัฒนาอัลกอริธึมต่างๆ มากมายเพื่อจุดประสงค์นี้
การระบายสีขอบช่วงของกราฟสมบูรณ์ช่วยในการจัดตารางการแข่งขัน 2n ครั้ง โดยที่แต่ละทีมจะได้เล่นกันเอง
การศึกษาเรื่องการระบายสีขอบช่วงของกราฟระนาบและกราฟสองส่วนกำลังก่อให้เกิดการประยุกต์ใช้งานอื่นๆ อีกมากมาย

ข้อสันนิษฐาน

สำหรับ m,n∈N ใดๆ K1,m,n ∈ N ก็ต่อเมื่อ gcd(m+1, n+1) = 1
ถ้าGเป็นกราฟระนาบที่มี จุดยอด nจุด จำนวนสีสูงสุดที่ใช้ในการระบายสีช่วงของG จะมีค่าไม่เกิน (3/2) n
กราฟระนาบนอกที่ได้จากการแบ่งสามเหลี่ยมระนาบนอกโดยไม่มีสามเหลี่ยมคั่นกลางโดยการลบขอบภายใน สามารถระบายสีตามช่วงได้

ดูเพิ่มเติม

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]