ในทฤษฎีกราฟกราฟช่วง (interval graph)คือกราฟแบบไม่มีทิศทางที่สร้างขึ้นจากเซตของช่วงบนเส้นจำนวนจริงโดยมีจุดยอดแทนแต่ละช่วง และมีเส้นเชื่อมระหว่างจุดยอดที่มีช่วงตัดกัน กราฟช่วงคือกราฟจุดตัดของช่วงเหล่านั้น

กราฟช่วง (Interval graphs) เป็นกราฟคอร์ดัล (chordal graphs)และกราฟสมบูรณ์ (perfect graphs ) สามารถระบุได้ในเวลาเชิงเส้นและสามารถหาการระบายสีกราฟ ที่เหมาะสมที่สุด หรือคลิกสูงสุด (maximum clique) ในกราฟเหล่านี้ได้ในเวลาเชิงเส้น กราฟช่วงประกอบด้วย กราฟช่วงแท้ (proper interval graphs) ทั้งหมด ซึ่งเป็นกราฟที่กำหนดในลักษณะเดียวกันจากเซตของช่วงหน่วย (unit intervals )

กราฟเหล่านี้ถูกนำมาใช้ในการสร้างแบบจำลองสายใยอาหารและศึกษา ปัญหา การจัดตารางเวลาที่ต้องเลือกชุดย่อยของงานที่จะดำเนินการในช่วงเวลาที่ไม่ทับซ้อนกัน การประยุกต์ใช้ในด้านอื่นๆ ได้แก่ การประกอบลำดับย่อยที่ต่อเนื่องกันใน การทำแผนที่ ดีเอ็นเอและการให้เหตุผลเชิงเวลา

กราฟช่วง (Interval graph) คือกราฟแบบไม่มีทิศทางGที่สร้างขึ้นจากกลุ่มของช่วงต่างๆ

${\displaystyle S_{i},\quad i=0,1,2,\dots }$

โดยการสร้างจุดยอดv _i หนึ่งจุด สำหรับแต่ละช่วงS _iและเชื่อมต่อจุดยอดv _iและv _j สองจุด ด้วยขอบเมื่อใดก็ตามที่เซตทั้งสองที่สอดคล้องกันมีส่วนที่ตัดกันที่ไม่ว่างเปล่า นั่นคือ เซตขอบของGคือ

${\displaystyle E(G)=\{(v_{i},v_{j})\mid S_{i}\cap S_{j}\neq \emptyset \}.}$

นี่คือกราฟแสดงจุดตัดของช่วงต่างๆ

กราฟประกอบด้วยจุดยอดอิสระสามจุด ซึ่งก่อให้เกิดกลุ่มจุดยอดคล้ายดาวเคราะห์น้อย (AT) หากสำหรับแต่ละสองจุด จะมีเส้นทางที่ประกอบด้วยจุดยอดสองจุดนั้น แต่ไม่มีจุดยอดที่สามอยู่ข้างเคียง กราฟจะเรียกว่าปราศจากกลุ่มจุดยอดคล้ายดาวเคราะห์ น้อย (AT-free ) หากไม่มีกลุ่มจุดยอดคล้ายดาวเคราะห์น้อย การกำหนดลักษณะเฉพาะของกราฟช่วงที่เก่าแก่ที่สุดดูเหมือนจะเป็นดังต่อไปนี้:

• กราฟจะเป็นกราฟช่วงก็ต่อเมื่อเป็นกราฟคอร์ดัลและปราศจาก AT ^{[ 1 ]}

ลักษณะอื่นๆ:

• กราฟเป็นกราฟช่วงก็ต่อเมื่อคลิก สูงสุดของกราฟ สามารถเรียงลำดับได้โดยที่จุดยอดแต่ละจุดที่อยู่ในคลิกสองจุดนั้น จะต้องอยู่ในคลิกทั้งหมดระหว่างคลิกทั้งสองนั้นด้วย กล่าวคือ สำหรับทุก ๆจุดยอดที่มีก็ยังเป็นกรณีที่เมื่อใดก็ตามที่^{[ 2 ]}${\displaystyle M_{1},M_{2},\dots ,M_{k}}$${\displaystyle v\in M_{i}\cap M_{k}}$${\displaystyle i<k}$${\displaystyle v\in M_{j}}$${\displaystyle i<j<k}$
• กราฟจะเป็นกราฟช่วงก็ต่อเมื่อไม่มีกราฟวงจร เป็นกราฟย่อยที่เหนี่ยวนำและเป็นส่วนเติมเต็มของกราฟเปรียบเทียบ^{[ 3 ]}${\displaystyle C_{4}}$

มีการอธิบายลักษณะอื่นๆ ของกราฟช่วงเวลาและรูปแบบต่างๆ ไว้แล้ว^{[ 4 ]}

การพิจารณาว่ากราฟที่กำหนดเป็นกราฟช่วงหรือไม่ สามารถทำได้ในเวลาโดยการค้นหาลำดับของคลิกสูงสุดที่ต่อเนื่องกันโดยสัมพันธ์กับการรวมจุดยอด อัลกอริทึมที่รู้จักจำนวนมากสำหรับปัญหานี้ทำงานในลักษณะนี้ แม้ว่าจะสามารถระบุกราฟช่วงได้ในเวลาเชิงเส้นโดยไม่ต้องใช้คลิกก็ตาม^{[ 5 ]}${\displaystyle G=(V,E)}$${\displaystyle O(|V|+|E|)}$${\displaystyle G}$

อัลกอริทึมการจดจำเวลาเชิงเส้นดั้งเดิมของBooth & Lueker (1976)นั้นมีพื้นฐานมาจากโครงสร้างข้อมูลต้นไม้ PQ ที่ซับซ้อนของพวกเขา แต่ Habib et al. (2000)ได้แสดงวิธีการแก้ปัญหาที่ง่ายกว่าโดยใช้การค้นหาแบบกว้างตามลำดับตัวอักษรโดยอาศัยข้อเท็จจริงที่ว่ากราฟเป็นกราฟช่วงเวลาก็ต่อเมื่อเป็นกราฟคอร์ดัลและส่วนเติมเต็ม ของมัน เป็นกราฟเปรียบเทียบ^{[ 6 ]} แนวทางที่คล้ายกันโดยใช้อัลกอริทึม LexBFS แบบ 6 รอบได้รับการอธิบายไว้ในCorneil, Olariu & Stewart (2009 )

จากการกำหนดลักษณะของกราฟช่วงเวลาเป็นกราฟคอร์ดัลที่ปราศจาก AT ^{[ 1 ]}กราฟช่วงเวลาจึงเป็นกราฟคอร์ดัลที่แข็งแกร่งและดังนั้นจึง เป็น กราฟที่สมบูรณ์ แบบ ส่วนเติมเต็มของกราฟเหล่านี้อยู่ในกลุ่มของกราฟเปรียบเทียบ [ ^{3 ]}และความสัมพันธ์ของการเปรียบเทียบก็คือ^{ลำดับ}ช่วงเวลา นั่นเอง ^{[ 7 ]}

จากข้อเท็จจริงที่ว่ากราฟจะเป็นกราฟช่วงก็ต่อเมื่อเป็นกราฟคอร์ดัลและกราฟส่วนเติมเต็มเป็นกราฟเปรียบเทียบได้จึงสรุปได้ว่ากราฟและกราฟส่วนเติมเต็มต่างก็เป็นกราฟช่วงก็ต่อเมื่อกราฟนั้นเป็นทั้งกราฟแยกส่วนและกราฟเรียงสับเปลี่ยน

กราฟช่วงที่มีการแสดงช่วงโดยที่ทุกๆ สองช่วงจะไม่ทับซ้อนกันหรือซ้อนกันอยู่ เรียกว่ากราฟสมบูรณ์แบบโดยปริยาย (trivially perfect graphs )

กราฟจะมีค่า boxicityไม่เกินหนึ่งก็ต่อเมื่อเป็นกราฟช่วงเท่านั้น ค่า boxicity ของกราฟใดๆ ก็ตามคือจำนวนกราฟช่วงขั้นต่ำบนเซตของจุดยอดเดียวกัน ซึ่งผลรวมของเซตของขอบของกราฟช่วงเหล่านั้นคือ ${\displaystyle G}$${\displaystyle G}$

กราฟจุดตัดของส่วนโค้งของวงกลมก่อให้เกิดกราฟส่วนโค้งวงกลมซึ่งเป็นกลุ่มกราฟที่รวมถึงกราฟช่วง กราฟสี่เหลี่ยมคางหมูซึ่งเป็นจุดตัดของสี่เหลี่ยมคางหมูที่มีด้านขนานทั้งหมดอยู่บนเส้นขนานสองเส้นเดียวกัน ก็เป็นการขยายความของกราฟช่วงเช่นกัน

กราฟช่วง ที่เชื่อมต่อกันโดยไม่มีสามเหลี่ยมคือต้นไม้หนอนผีเสื้อ^{[ 8 ]}

กราฟช่วงเวลาที่เหมาะสมคือกราฟช่วงเวลาที่มีการแสดงช่วงเวลาซึ่งไม่มีช่วงเวลา ใด บรรจุช่วงเวลาอื่นได้ อย่างเหมาะสม กราฟช่วงเวลาหน่วยคือกราฟช่วงเวลาที่มีการแสดงช่วงเวลาซึ่งแต่ละช่วงเวลามีความยาวหนึ่งหน่วย การแสดงช่วงเวลาหน่วยที่ไม่มีช่วงเวลาซ้ำกันจำเป็นต้องเป็นการแสดงช่วงเวลาที่เหมาะสม ไม่ใช่ทุกการแสดงช่วงเวลาที่เหมาะสมจะเป็นการแสดงช่วงเวลาหน่วย แต่กราฟช่วงเวลาที่เหมาะสมทุกกราฟเป็นกราฟช่วงเวลาหน่วย และในทางกลับกัน^{[ 9 ]}กราฟช่วงเวลาที่เหมาะสมทุกกราฟเป็นกราฟที่ไม่มีกรงเล็บในทางกลับกัน กราฟช่วงเวลาที่เหมาะสมก็คือกราฟช่วงเวลาที่ไม่มีกรงเล็บ อย่างไรก็ตาม มีกราฟที่ไม่มีกรงเล็บที่ไม่ใช่กราฟช่วงเวลาอยู่^{[ 10 ]}

กราฟช่วงเวลาเรียกว่า-proper ถ้ามีการแสดงแทนซึ่งไม่มีช่วงเวลาใดบรรจุมากกว่าช่วงเวลาอื่น แนวคิดนี้ขยายแนวคิดของกราฟช่วงเวลาที่เหมาะสม โดยที่กราฟช่วงเวลา 0-proper เป็นกราฟช่วงเวลาที่เหมาะสม^{[ 11 ]} กราฟช่วงเวลาเรียกว่า-improper ถ้ามีการแสดงแทนซึ่งไม่มีช่วงเวลาใดบรรจุมากกว่าช่วงเวลาอื่น แนวคิดนี้ขยายแนวคิดของกราฟช่วงเวลาที่เหมาะสม โดยที่กราฟช่วงเวลา 0-improper เป็นกราฟช่วงเวลาที่เหมาะสม^{[ 12 ]} กราฟช่วงเวลาเรียกว่า-nested ถ้าไม่มีสายโซ่ของช่วงเวลาที่มีความยาวซ้อนกัน นี่เป็นการวางนัยทั่วไปของกราฟช่วงเวลาที่เหมาะสม เนื่องจากกราฟช่วงเวลา 1-nested เป็นกราฟช่วงเวลาที่เหมาะสมอย่างแท้จริง^{[ 13 ]}${\displaystyle q}$${\displaystyle q}$${\displaystyle p}$${\displaystyle p}$${\displaystyle k}$${\displaystyle k+1}$

ทฤษฎีทางคณิตศาสตร์ของกราฟช่วงเวลาได้รับการพัฒนาโดยนักวิจัยใน แผนกคณิตศาสตร์ของ RAND Corporation โดยมุ่งเน้นการประยุกต์ใช้ ซึ่งรวมถึงนักวิจัยรุ่นใหม่ เช่นPeter C. Fishburnและนักศึกษาอย่างAlan C. TuckerและJoel E. Cohenรวมถึงผู้นำ เช่นDelbert FulkersonและVictor Klee ( ผู้มาเยือนเป็นประจำ) ^{[ 14 ]} Cohen ได้ประยุกต์ใช้กราฟช่วงเวลากับแบบจำลองทางคณิตศาสตร์ของชีววิทยาประชากรโดยเฉพาะอย่างยิ่งใยอาหาร^{[ 15 ]}

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

การระบายสีกราฟที่เหมาะสมที่สุดของกราฟช่วงเวลาแสดงถึงการจัดสรรทรัพยากรที่ครอบคลุมคำขอทั้งหมดโดยใช้ทรัพยากรให้น้อยที่สุดเท่าที่จะเป็นไปได้ ซึ่งสามารถค้นหาได้ในเวลาพหุนามโดย อัลกอริทึม การระบายสีแบบโลภที่ระบายสีช่วงเวลาตามลำดับที่เรียงตามจุดปลายด้านซ้าย^{[ 17 ]}

การประยุกต์ใช้อื่นๆ ได้แก่ พันธุศาสตร์ชีวสารสนเทศและวิทยาศาสตร์คอมพิวเตอร์ การค้นหาชุดช่วงเวลาที่แสดงถึงกราฟช่วงเวลาสามารถใช้เป็นวิธีการประกอบลำดับย่อยที่ต่อเนื่องกันในการทำแผนที่DNA ได้เช่นกัน ^{[ 18 ]}กราฟช่วงเวลายังมีบทบาทสำคัญในการให้เหตุผลเชิงเวลาอีกด้วย^{[ 19 ]}

ถ้าเป็นกราฟใดๆการเติมเต็มช่วงของ คือกราฟช่วงบนเซตจุดยอดเดียวกันที่มีเป็นกราฟย่อย เวอร์ชันพารามิเตอร์ของการเติมเต็มช่วง (หาซูเปอร์กราฟช่วงที่มี ขอบเพิ่มเติม kเส้น) สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่และยิ่งไปกว่านั้น สามารถแก้ไขได้ในเวลาแบบ subexponential ที่มีพารามิเตอร์^{[ 20 ] [ 21 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

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

จำนวนกราฟช่วงที่เชื่อมต่อกันบนจุดยอดที่ไม่มีป้ายกำกับ สำหรับคือ: ^{[ 23 ]}${\displaystyle n}$${\displaystyle n=1,2,3,\dots }$

1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302, ... (ลำดับA005976ในOEIS )

หากไม่มีสมมติฐานเรื่องการเชื่อมต่อ ตัวเลขก็จะมากขึ้น จำนวนกราฟช่วงเวลาบนจุดยอดที่ไม่มีป้ายกำกับ ซึ่งไม่จำเป็นต้องเชื่อมต่อกัน คือ: ^{[ 24 ]}${\displaystyle n}$

1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446, ... (ลำดับA005975ในOEIS )

ตัวเลขเหล่านี้แสดงให้เห็นการเติบโตที่เร็วกว่าแบบเลขชี้กำลัง : จำนวนกราฟช่วงบนจุดยอดที่ไม่มีป้ายกำกับมีอย่างน้อย[ ^{25 ] เนื่องจาก}อัตราการเติบโตที่รวดเร็วนี้ กราฟช่วงจึงไม่มีความกว้างคู่ที่ จำกัด ^{[ 26 ]}${\displaystyle 3n}$${\displaystyle n!/3^{3n}}$

• "กราฟช่วง"ระบบสารสนเทศเกี่ยวกับคลาสกราฟและส่วนประกอบต่างๆ
• ไวส์สไตน์, เอริค ดับเบิลยู. , "กราฟช่วง" , MathWorld