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

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

ในทฤษฎีความซับซ้อนของการคำนวณ มีการกำหนด คลาสความซับซ้อนหลาย คลาส ที่เกี่ยวข้องกับกราฟโดยปริยาย ซึ่งกำหนดไว้ข้างต้นโดยกฎหรืออัลกอริทึมสำหรับการแสดงรายการเพื่อนบ้านของจุดยอด ตัวอย่างเช่นPPAคือคลาสของปัญหาที่กำหนดให้รับกราฟโดยปริยายแบบไม่มีทิศทาง (ซึ่งจุดยอดเป็นสตริงไบนารีn บิต โดยมีอัลกอริทึม เวลาพหุนามสำหรับการแสดงรายการเพื่อนบ้านของจุดยอดใดๆ) และจุดยอดที่มีดีกรีคี่ในกราฟเป็นอินพุต และต้องหาจุดยอดที่สองที่มีดีกรีคี่ ตามทฤษฎีบทการจับมือกันจุดยอดดังกล่าวมีอยู่จริง การหาจุดยอดนั้นเป็นปัญหาในNPแต่ปัญหาที่สามารถกำหนดได้ในลักษณะนี้อาจไม่จำเป็นต้องเป็นNP-completeเนื่องจากไม่ทราบว่า PPA = NP หรือไม่PPADเป็นคลาสที่คล้ายกันซึ่งกำหนดบนกราฟโดยปริยาย แบบมีทิศทาง ซึ่งได้รับความสนใจในทฤษฎีเกมเชิงอัลก อริทึม เนื่องจากมีปัญหาในการคำนวณสมดุลแนช^{[ 3 ]}ปัญหาของการทดสอบการเข้าถึงของจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่งในกราฟโดยปริยาย อาจใช้เพื่อกำหนดลักษณะของคลาสความซับซ้อนที่ไม่แน่นอนที่มีขอบเขตพื้นที่ รวมถึงNL (คลาสของปัญหาที่อาจกำหนดลักษณะโดยการเข้าถึงในกราฟทิศทางโดยปริยายซึ่งจุดยอดเป็น สตริงบิต O(log n )บิต), SL (คลาสที่คล้ายกันสำหรับกราฟที่ไม่มีทิศทาง) และPSPACE (คลาสของปัญหาที่อาจกำหนดลักษณะโดยการเข้าถึงในกราฟโดยปริยายที่มีสตริงบิตความยาวพหุนาม) ในบริบททางทฤษฎีความซับซ้อนนี้ จุดยอดของกราฟโดยปริยายอาจแทนสถานะของเครื่องจักรทัวริงที่ไม่แน่นอนและขอบอาจแทนการเปลี่ยนสถานะที่เป็นไปได้ แต่กราฟโดยปริยายอาจใช้เพื่อแสดงโครงสร้างเชิงการจัดเรียงประเภทอื่นๆ อีกมากมาย^{[ 4 ​​]} PLSซึ่งเป็นคลาสความซับซ้อนอีกคลาสหนึ่ง จับความซับซ้อนของการค้นหาจุดเหมาะสมที่สุดในท้องถิ่นในกราฟโดยปริยาย^{[ 5 ]}

แบบจำลองกราฟโดยปริยายยังถูกใช้เป็นรูปแบบของการเปรียบเทียบเพื่อพิสูจน์การแยกระหว่างคลาสความซับซ้อนที่แข็งแกร่งกว่าการแยกที่ทราบสำหรับแบบจำลองที่ไม่ใช่แบบเปรียบเทียบ ตัวอย่างเช่น Childs et al. ใช้การแสดงแทนย่านใกล้เคียงของกราฟโดยปริยายเพื่อกำหนดปัญหาการท่องกราฟที่สามารถแก้ไขได้ในเวลาพหุนามบนคอมพิวเตอร์ควอนตัมแต่ต้องใช้เวลาเลขชี้กำลังในการแก้ไขบนคอมพิวเตอร์แบบคลาสสิกใดๆ^{[ 6 ]}

ในบริบทของการแสดงกราฟที่มีประสิทธิภาพ JH Muller ได้กำหนดโครงสร้างท้องถิ่นหรือรูปแบบการติดป้ายความสัมพันธ์สำหรับกราฟGในตระกูล กราฟ Fที่กำหนดให้เป็นการกำหนด ตัวระบุ O (log n )บิตให้กับแต่ละจุดยอดของGพร้อมกับอัลกอริทึม (ซึ่งอาจขึ้นอยู่กับFแต่เป็นอิสระจากกราฟG แต่ละตัว ) ที่รับตัวระบุจุดยอดสองตัวเป็นอินพุตและพิจารณาว่าจุดยอดเหล่านั้นเป็นจุดปลายของขอบในG หรือไม่ กล่าวคือ การแสดงแบบโดยนัยประเภทนี้คล้ายคลึงกับเมทริกซ์ความสัมพันธ์กล่าวคือ การตรวจสอบว่าจุดยอดสองจุดอยู่ติดกันหรือไม่นั้นทำได้ง่าย แต่การค้นหาเพื่อนบ้านของจุดยอดใดๆ อาจเกี่ยวข้องกับการวนลูปผ่านจุดยอดทั้งหมดและทดสอบว่าจุดใดเป็นเพื่อนบ้าน^{[ 7 ]}

กลุ่มกราฟที่มีรูปแบบการติดป้ายกำกับความสัมพันธ์แบบประชิด ได้แก่:

กราฟดีกรีจำกัด

ถ้าทุกจุดยอดในGมีเพื่อนบ้านไม่เกินdจุด เราอาจกำหนดหมายเลขให้กับจุดยอดของGตั้งแต่ 1 ถึงnและให้ตัวระบุสำหรับจุดยอดเป็น ทูเปิล ( d + 1)ของหมายเลขของจุดยอดนั้นเองและหมายเลขของเพื่อนบ้าน จุดยอดสองจุดจะอยู่ติดกันเมื่อหมายเลขแรกในตัวระบุของจุดยอดทั้งสองปรากฏทีหลังในตัวระบุของจุดยอดอีกจุดหนึ่ง โดยทั่วไปแล้ว สามารถใช้แนวทางเดียวกันนี้เพื่อแสดงกราฟโดยปริยายที่มีขอบเขตของความเป็นต้นไม้หรือ ขอบเขตของ การเสื่อม สภาพ รวมถึงกราฟระนาบและกราฟในตระกูลกราฟปิดไมเนอร์ใด ๆ ^{[ 8 ] [ 9 ]}

กราฟจุดตัด

กราฟช่วงคือกราฟจุดตัดของเซตของส่วนของเส้นตรงในเส้นจำนวนจริงอาจมีการกำหนดรูปแบบการติดป้ายความประชิดโดยที่จุดที่เป็นจุดปลายของส่วนของเส้นตรงจะถูกกำหนดหมายเลขตั้งแต่ 1 ถึง 2n และแต่ละจุดยอดของกราฟจะถูกแทนด้วยหมายเลขของจุดปลายทั้งสองของช่วงที่สอดคล้องกัน ด้วยการแสดงแบบนี้ เราสามารถตรวจสอบได้ว่าจุดยอดสองจุดอยู่ติดกันหรือไม่โดยการเปรียบเทียบหมายเลขที่แทนจุดยอดเหล่านั้นและตรวจสอบว่าหมายเลขเหล่านี้กำหนดช่วงที่ทับซ้อนกัน วิธีการเดียวกันนี้ใช้ได้กับกราฟจุดตัดทางเรขาคณิตอื่นๆ รวมถึงกราฟของกล่องที่ มีขอบเขต และกราฟวงกลมและตระกูลย่อยของตระกูลเหล่านี้ เช่นกราฟระยะทางสืบทอดและโคกราฟ [ ^{8 ] [ 10 ] อย่างไรก็ตาม}การแสดงกราฟจุดตัดทางเรขาคณิตไม่ได้หมายความถึงการมีอยู่ของรูปแบบการติดป้ายความประชิดเสมอไป เนื่องจากอาจต้องใช้บิตมากกว่าจำนวนลอการิทึมเพื่อระบุวัตถุทางเรขาคณิตแต่ละชิ้น ตัวอย่างเช่น การแสดงกราฟเป็นกราฟดิสก์หน่วยอาจต้องใช้บิตจำนวนมากแบบเลขชี้กำลังสำหรับพิกัดของจุดศูนย์กลางดิสก์^{[ 11 ]}

กราฟเปรียบเทียบมิติที่ต่ำกว่า

กราฟเปรียบเทียบสำหรับเซตที่มีลำดับบางส่วนจะมีจุดยอดสำหรับองค์ประกอบเซตแต่ละอัน และมีขอบเชื่อมระหว่างองค์ประกอบเซตสองอันที่สัมพันธ์กันด้วยลำดับบางส่วนมิติของลำดับบางส่วนคือจำนวนขั้นต่ำของลำดับเชิงเส้นที่มีจุดตัดเป็นลำดับบางส่วนที่กำหนด หากลำดับบางส่วนมีมิติของลำดับที่จำกัด แผนการติดป้ายความประชิดสำหรับจุดยอดในกราฟเปรียบเทียบอาจถูกกำหนดโดยการติดป้ายจุดยอดแต่ละจุดด้วยตำแหน่งของจุดยอดในแต่ละลำดับเชิงเส้นที่กำหนด และพิจารณาว่าจุดยอดสองจุดอยู่ติดกันหากคู่ตัวเลขที่สอดคล้องกันในป้ายของจุดยอดแต่ละคู่มีความสัมพันธ์ของลำดับเหมือนกับคู่ตัวเลขอื่นๆ โดยเฉพาะอย่างยิ่ง วิธีนี้ช่วยให้สามารถใช้แผนการติดป้ายความประชิดสำหรับกราฟเปรียบเทียบแบบคอร์ดัล ซึ่งมาจากลำดับบางส่วนที่มีมิติไม่เกินสี่^{[ 12 ] [ 13 ]}

ไม่ใช่ว่าตระกูลกราฟทั้งหมดจะมีโครงสร้างเฉพาะที่ สำหรับบางตระกูล การโต้แย้งการนับอย่างง่ายพิสูจน์ได้ว่าไม่มีแผนการติดป้ายความสัมพันธ์: สามารถใช้บิต O ( n log n )เพื่อแสดงกราฟทั้งหมดได้ ดังนั้นการแสดงประเภทนี้จึงมีอยู่ได้ก็ต่อเมื่อจำนวน กราฟ nจุดยอดในตระกูลF ที่กำหนด มีค่าไม่เกิน2 ^{O ( n log n )}ตระกูลกราฟที่มีจำนวนกราฟมากกว่านี้ เช่นกราฟสองส่วนหรือกราฟที่ไม่มีสามเหลี่ยมจะไม่มีแผนการติดป้ายความสัมพันธ์^{[ 8 ] [ 10 ]}อย่างไรก็ตาม แม้แต่ตระกูลกราฟที่มีจำนวนกราฟในตระกูลน้อยก็อาจไม่มีแผนการติดป้ายความสัมพันธ์ ตัวอย่างเช่น ตระกูลกราฟที่มีขอบน้อยกว่าจุดยอดจะมี กราฟ 2 ^{O ( n log n )} nจุดยอด แต่ไม่มีรูปแบบการติดป้ายความสัมพันธ์ เนื่องจากสามารถแปลงกราฟใดๆ ที่กำหนดให้เป็นกราฟขนาดใหญ่ขึ้นในตระกูลนี้ได้โดยการเพิ่มจุดยอดที่แยกเดี่ยวใหม่สำหรับแต่ละขอบ โดยไม่เปลี่ยนแปลงความสามารถในการติดป้าย^{[ 7 ] [ 10 ]} Kannan และคณะได้ตั้งคำถามว่าการมีลักษณะเฉพาะของกราฟย่อยที่ต้องห้ามและการมีกราฟอย่างมากที่สุด 2 ^{O ( n log n )} nจุดยอดนั้นเพียงพอที่จะรับประกันการมีอยู่ของรูปแบบการติดป้ายความสัมพันธ์หรือไม่ คำถามนี้ซึ่ง Spinrad ได้กล่าวซ้ำอีกครั้งว่าเป็นข้อสันนิษฐาน งานล่าสุดได้หักล้างข้อสันนิษฐานนี้โดยการจัดหาตระกูลกราฟที่มีลักษณะเฉพาะของกราฟย่อยที่ต้องห้ามและอัตราการเติบโตที่ช้าพอ แต่ไม่มีรูปแบบการติดป้ายความสัมพันธ์^{[ 14 ]} ในบรรดาตระกูลของกราฟที่ตรงตามเงื่อนไขของการคาดการณ์และซึ่งไม่มีแผนการติดป้ายประชิดที่รู้จัก ได้แก่ ตระกูลของกราฟดิสก์และกราฟจุดตัดของส่วนของเส้นตรง

หากตระกูลกราฟFมีรูปแบบการติดป้ายความสัมพันธ์ กราฟ nจุดยอดในFอาจถูกแทนด้วยกราฟย่อยเหนี่ยวนำของกราฟสากลเหนี่ยว นำทั่วไป ที่มีขนาดพหุนาม ซึ่งเป็นกราฟที่ประกอบด้วยตัวระบุจุดยอดที่เป็นไปได้ทั้งหมด ในทางกลับกัน หากสามารถสร้างกราฟสากลเหนี่ยวนำประเภทนี้ได้ เอกลักษณ์ของจุดยอดอาจถูกใช้เป็นป้ายกำกับในรูปแบบการติดป้ายความสัมพันธ์^{[ 8 ]}สำหรับการประยุกต์ใช้การแสดงกราฟโดยปริยายนี้ สิ่งสำคัญคือป้ายกำกับต้องใช้บิตให้น้อยที่สุดเท่าที่จะเป็นไปได้ เนื่องจากจำนวนบิตในป้ายกำกับจะแปลงโดยตรงเป็นจำนวนจุดยอดในกราฟสากลเหนี่ยวนำ Alstrup และ Rauhe แสดงให้เห็นว่าต้นไม้ใดๆ ก็มีรูปแบบการติดป้ายประชิดที่มีlog ₂ n + O ( log * n )บิตต่อป้าย ซึ่งจากนั้นจะสรุปได้ว่ากราฟใดๆ ที่มีarboricity kก็จะมีรูปแบบที่มีk log ₂ n + O ( log * n )บิตต่อป้าย และกราฟสากลที่มีn ^k 2 ^{O ( log * n )}จุดยอด โดยเฉพาะอย่างยิ่ง กราฟระนาบจะมี arboricity ไม่เกินสาม ดังนั้นจึงมีกราฟสากลที่มีจำนวนจุดยอดเกือบเป็นลูกบาศก์^{[ 15 ]} ขอบเขตนี้ได้รับการปรับปรุงโดย Gavoille และ Labourel ซึ่งแสดงให้เห็นว่ากราฟระนาบและตระกูลกราฟปิดไมเนอร์มีรูปแบบการติดป้ายที่มี2 log ₂ n + O (log log n ) บิตต่อป้าย และกราฟที่มีtreewidth จำกัด จะมีรูปแบบการติดป้ายที่มีlog ₂ n + O (log log n )บิตต่อป้าย^{[ 16 ]} ขอบเขตสำหรับกราฟระนาบได้รับการปรับปรุงอีกครั้งโดย Bonamy, Gavoille และ Piliczuk ซึ่งแสดงให้เห็นว่ากราฟระนาบมีรูปแบบการติดป้ายที่มี(4/3+o(1))log ₂ n บิตต่อป้าย^{[ 17 ]} ในที่สุด Dujmović และคณะแสดงให้เห็นว่ากราฟระนาบมีรูปแบบการติดป้ายที่มี(1+o(1))log ₂ n บิตต่อป้าย ทำให้ได้กราฟสากลที่มีn ^1+o(1)จุดยอด^{[ 18 ]}

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

คุณสมบัติของกราฟคือคำถามที่ว่ากราฟนั้นเป็นของตระกูลกราฟที่กำหนดหรือไม่ คำตอบต้องไม่เปลี่ยนแปลงภายใต้การเปลี่ยนชื่อจุดยอดใดๆ ในบริบทนี้ คำถามที่ต้องพิจารณาคือต้องทดสอบจุดยอดกี่คู่สำหรับการอยู่ติดกัน ในกรณีที่เลวร้ายที่สุด ก่อนที่จะสามารถระบุได้ว่าคุณสมบัติที่สนใจนั้นเป็นจริงหรือเท็จสำหรับกราฟโดยปริยายที่กำหนด Rivest และ Vuillemin พิสูจน์แล้วว่าอัลกอริทึมเชิงกำหนดใดๆ สำหรับคุณสมบัติของกราฟที่ไม่ใช่แบบธรรมดาจะต้องทดสอบจำนวนคู่ของจุดยอดที่เป็นกำลังสอง^{[ 19 ]}ข้อสันนิษฐานของ Aanderaa–Karp–Rosenberg ฉบับเต็มคืออัลกอริทึมเชิงกำหนดใดๆ สำหรับคุณสมบัติของกราฟแบบโมโนโทนิก (ซึ่งยังคงเป็นจริงหากมีการเพิ่มขอบเพิ่มเติมลงในกราฟที่มีคุณสมบัตินั้น) ในบางกรณีจะต้องทดสอบจุดยอดทุกคู่ที่เป็นไปได้ มีการพิสูจน์แล้วว่าข้อสันนิษฐานดังกล่าวเป็นจริงในหลายกรณี เช่น เป็นที่ทราบกันว่าเป็นจริงสำหรับกราฟที่มีจำนวนจุดยอดเป็นจำนวนเฉพาะ^{[ 20 ]}แต่ข้อสันนิษฐานทั้งหมดยังคงเปิดอยู่ นอกจากนี้ยังมีการศึกษารูปแบบต่างๆ ของปัญหาสำหรับอัลกอริธึมแบบสุ่มและอัลกอริธึมควอนตัมด้วย

เบนเดอร์และรอนได้แสดงให้เห็นว่า ในแบบจำลองเดียวกันที่ใช้สำหรับสมมติฐานการหลบเลี่ยงนั้น เป็นไปได้ที่จะแยกแยะกราฟแบบมีทิศทางที่ไม่มีวงจรออกจากกราฟที่อยู่ห่างไกลจากความเป็นกราฟที่ไม่มีวงจรได้ในเวลาคงที่เท่านั้น ในทางตรงกันข้าม เวลาที่รวดเร็วเช่นนี้เป็นไปไม่ได้ในแบบจำลองกราฟโดยนัยที่อิงตามเพื่อนบ้าน^{[ 21 ]}

• กลุ่มกล่องดำ : แบบจำลองโดยนัยสำหรับ อัลกอริธึมเชิง ทฤษฎีกลุ่ม
• Matroid oracleโมเดลโดยนัยสำหรับอัลกอริธึมMatroid