อ่าน 3 นาที
การขยายตัวแบบมีขอบเขต
ในทฤษฎีกราฟตระกูลของกราฟจะเรียกว่ามีขอบเขตการขยายที่จำกัด หาก ไมเนอร์ตื้นทั้งหมดของตระกูลนั้นเป็นกราฟเบาบางตระกูลกราฟเบาบางตามธรรมชาติหลายตระกูลมีขอบเขตการขยายที่จำกัด...
การขยายตัวแบบมีขอบเขต
ในทฤษฎีกราฟตระกูลของกราฟจะเรียกว่ามีขอบเขตการขยายที่จำกัด หาก ไมเนอร์ตื้นทั้งหมดของตระกูลนั้นเป็นกราฟเบาบางตระกูลกราฟเบาบางตามธรรมชาติหลายตระกูลมีขอบเขตการขยายที่จำกัด คุณสมบัติที่เกี่ยวข้องอย่างใกล้ชิดแต่แข็งแกร่งกว่า คือ การขยายพหุนามซึ่งเทียบเท่ากับการมีอยู่ของทฤษฎีบทตัวแยก สำหรับตระกูลเหล่านี้ ตระกูลที่มีคุณสมบัติเหล่านี้มี อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาต่างๆ รวมถึงปัญหาไอโซมอร์ฟิซึมของกราฟย่อยและการตรวจสอบแบบจำลองสำหรับทฤษฎีอันดับแรกของกราฟ
คำจำกัดความและลักษณะเทียบเท่า
ไมเนอร์ แบบตื้น tของกราฟGถูกกำหนดให้เป็นกราฟที่สร้างขึ้นจากGโดยการยุบกลุ่มของกราฟย่อยที่ไม่มีจุดยอดร่วมกันซึ่งมีรัศมีtและลบจุดยอดที่เหลือของGตระกูลของกราฟมีการขยายที่จำกัดหากมีฟังก์ชันf อยู่ เช่นนั้น ในทุก ไมเนอร์แบบตื้น tของกราฟในตระกูล อัตราส่วนของขอบต่อจุดยอดจะมีค่าไม่เกินf ( t ) [ 1 ]
นิยามที่เทียบเท่ากันของคลาสของการขยายขอบเขตคือไมเนอร์ตื้นทั้งหมดมีจำนวนสีที่ถูกจำกัดด้วยฟังก์ชันของt [ 1 ]หรือตระกูลที่กำหนดมีค่าพารามิเตอร์ทางโทโพโลยี ที่ถูกจำกัด พารามิเตอร์ดังกล่าวเป็น ค่า คงที่ของกราฟ ที่เป็นโมโนโทนภายใต้การ เลือกกราฟย่อย โดยที่ค่าพารามิเตอร์สามารถเปลี่ยนแปลงได้เฉพาะในลักษณะที่ควบคุมได้เมื่อกราฟถูกแบ่งย่อย และค่าพารามิเตอร์ที่ถูกจำกัดหมายความว่ากราฟมีการเสื่อมสภาพที่ ถูกจำกัด [ 2 ]
การขยายพหุนามและทฤษฎีบทตัวคั่น
แนวคิดที่แข็งแกร่งกว่าคือการขยายพหุนามหมายความว่าฟังก์ชันfที่ใช้ในการจำกัดความหนาแน่นของขอบของไมเนอร์ตื้นเป็นพหุนามหากตระกูลกราฟสืบทอดเป็นไปตามทฤษฎีบทตัวแยกซึ่งระบุว่า กราฟ nจุดยอดใดๆ ในตระกูลสามารถแยกออกเป็นชิ้นส่วนที่มีจุดยอดไม่เกินn /2 จุดยอดโดยการลบ จุดยอด O ( nc ) สำหรับค่าคงที่c < 1 บางค่า ตระกูล นั้น จะต้องมีการขยายพหุนาม ในทางกลับกัน กราฟที่มีการขยายพหุนามจะมีทฤษฎีบทตัวแยกแบบย่อยเชิงเส้น[ 3 ]
คลาสของกราฟที่มีการขยายแบบจำกัด
เนื่องจากความเชื่อมโยงระหว่างตัวแยกและการขยายกราฟตระกูลปิดไมเนอร์ทุกตระกูลรวมถึงตระกูลกราฟระนาบจึงมีการขยายพหุนาม เช่นเดียวกับกราฟระนาบ 1 มิติและโดยทั่วไปแล้วกราฟที่สามารถฝังลงบนพื้นผิวที่มีจีนัสจำกัดและมีจำนวนจุดตัดต่อขอบจำกัด รวมถึงกราฟสตริงที่ปราศจากไบคลิก เนื่องจากกราฟเหล่านี้ทั้งหมดเป็นไปตามทฤษฎีบทตัวแยกที่คล้ายคลึงกันกับกราฟระนาบ[ 4 ] [ 5 ] [ 6 ] [ 7 ] ใน ปริภูมิยุคลิดมิติสูงกราฟจุดตัดของระบบลูกบอลที่มีคุณสมบัติว่าจุดใดๆ ในปริภูมิถูกปกคลุมด้วยลูกบอลจำนวนจำกัด ก็เป็นไปตามทฤษฎีบทตัวแยก[ 8 ]ที่บ่งบอกถึงการขยายพหุนาม เช่นกัน
แม้ว่ากราฟที่มีความหนาของหนังสือ จำกัด จะไม่มีตัวคั่นย่อยเชิงเส้น[ 9 ]แต่ก็มีการขยายที่จำกัดเช่นกัน[ 10 ]กราฟอื่นๆ ที่มีการขยายที่จำกัด ได้แก่ กราฟที่มีดีกรีจำกัด[ 11 ]กราฟสุ่มที่มีดีกรีเฉลี่ยจำกัดในแบบจำลอง Erdős–Rényi [ 12 ]และกราฟที่มีจำนวนคิวจำกัด[ 2 ] [ 13 ]
แอปพลิเคชันเชิงอัลกอริทึม
ตัวอย่างของปัญหาไอโซมอร์ฟิซึมของกราฟย่อยซึ่งมีเป้าหมายคือการค้นหากราฟเป้าหมายที่มีขนาดจำกัด ในฐานะกราฟย่อยของกราฟขนาดใหญ่ที่มีขนาดไม่จำกัด สามารถแก้ไขได้ในเวลาเชิงเส้นเมื่อกราฟขนาดใหญ่อยู่ในตระกูลของกราฟที่มีการขยายแบบจำกัด เช่นเดียวกันนี้ก็เป็นจริงสำหรับการค้นหาคลิกที่มีขนาดคงที่ การค้นหาเซตครอบงำที่มีขนาดคงที่ หรือโดยทั่วไปแล้วการทดสอบคุณสมบัติที่สามารถแสดงได้ด้วยสูตรที่มีขนาดจำกัดในตรรกะลำดับที่หนึ่งของกราฟ[ 14 ] [ 15 ]
สำหรับกราฟของการขยายพหุนาม จะมีแผนการประมาณค่าในเวลาพหุนามสำหรับปัญหาการครอบคลุมเซตปัญหาเซตอิสระสูงสุดปัญหาเซตครอบงำและปัญหาการเพิ่มประสิทธิภาพกราฟอื่นๆ ที่เกี่ยวข้องอีกหลายประการ[ 16 ]
เอกสารอ้างอิง
- ^ a b Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "5.5 Classes with Bounded Expansion", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, pp. 104– 107, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ a b Nešetřil, Jaroslav ; Ossona de Mendez, Patrice ; Wood, David R. (2012), "Characterisations and examples of graph classes with bounded expansion", European Journal of Combinatorics , 33 (3): 350– 373, arXiv : 0902.3265 , doi : 10.1016/j.ejc.2011.09.008 , MR 2864421 , S2CID 2633083 .
- ^ Dvořák, Zdeněk; Norin, Sergey (2016), "ตัวแยกย่อยเชิงเส้นอย่างเข้มข้นและการขยายพหุนาม", SIAM Journal on Discrete Mathematics , 30 (2): 1095– 1101, arXiv : 1504.04821 , doi : 10.1137/15M1017569 , MR 3504982 , S2CID 27395359
- ↑ Nešetřil & Ossona de Mendez (2012) , 14.2 Crossing Number, หน้า 319–321.
- ^ Grigoriev, Alexander; Bodlaender, Hans L. (2007), "อัลกอริทึมสำหรับกราฟที่ฝังได้โดยมีจุดตัดน้อยต่อขอบ" , Algorithmica , 49 (1): 1– 11, doi : 10.1007/s00453-007-0010-x , hdl : 1874/17980 , MR 2344391 , S2CID 8174422 .
- ^ Dujmović, Vida ; Eppstein, David ; Wood, David R. (2015), "Genus, treewidth, and local crossing number", Proc. 23rd Int. Symp. Graph Drawing (GD 2015) , arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D.
- ^ Fox, Jacob ; Pach, János (2009), "ทฤษฎีบทตัวแยกสำหรับกราฟสตริงและการประยุกต์ใช้" (PDF) , Combinatorics, Probability and Computing , 19 (3): 371, doi : 10.1017/s0963548309990459 , S2CID 5705145 .
- ^ Miller, Gary L. ; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "ตัวคั่นสำหรับการจัดเรียงทรงกลมและกราฟเพื่อนบ้านที่ใกล้ที่สุด", Journal of the ACM , 44 (1): 1– 29, doi : 10.1145/256292.256294 , MR 1438463 .
- ↑ดุยโมวิช, วิดา; ซิดิโรปูลอส, อนาสตาซิออส; Wood, David R. (2015), 3-Monotone Expanders , arXiv : 1501.05020 , Bibcode : 2015arXiv150105020D
- ↑ Nešetřil & Ossona de Mendez (2012) , 14.5 Stack Number, หน้า 327–328
- ↑ Nešetřil & Ossona de Mendez (2012) , หน้า. 307.
- ↑ Nešetřil & Ossona de Mendez (2012) , 14.1 Random Graphs (Erdős–Rényi Model), หน้า 314–319.
- ↑ Nešetřil & Ossona de Mendez (2012) , หน้า 321–327.
- ↑ Nešetřil & Ossona de Mendez (2012) , 18.3 The Subgraph Isomorphism Problem and Boolean Queries, หน้า 400–401
- ^ Dvořák, Zdeněk ; Kráľ, Daniel ; Thomas, Robin (2010), "การตัดสินคุณสมบัติลำดับแรกสำหรับกราฟแบบเบาบาง", Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) , IEEE Computer Soc., Los Alamitos, CA, pp. 133– 142, MR 3024787 .
- ^ Har-Peled, Sariel ; Quanrud, Kent (2015), "Approximation algorithms for polynomial-expansion and low-density graphs" , Algorithms - ESA 2015 , Lecture Notes in Computer Science, vol. 9294, Springer-Verlag, pp. 717– 728, arXiv : 1501.00721 , doi : 10.1007/978-3-662-48350-3_60 , ISBN 978-3-662-48349-7.
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ การขยายตัวแบบมีขอบเขต
ในทฤษฎีกราฟตระกูลของกราฟจะเรียกว่ามีขอบเขตการขยายที่จำกัด หาก ไมเนอร์ตื้นทั้งหมดของตระกูลนั้นเป็นกราฟเบาบางตระกูลกราฟเบาบางตามธรรมชาติหลายตระกูลมีขอบเขตการขยายที่จำกัด...
คำจำกัดความและลักษณะเทียบเท่า
ไมเนอร์ แบบตื้น tของกราฟGถูกกำหนดให้เป็นกราฟที่สร้างขึ้นจากGโดยการยุบกลุ่มของกราฟย่อยที่ไม่มีจุดยอดร่วมกันซึ่งมีรัศมีtและลบจุดยอดที่เหลือของGตระกูลของกราฟมีการขยายที่จำกัดหากมีฟังก์ชันf อยู่ เช่นนั้น ในทุก ไมเนอร์แบบตื้น tของกราฟในตระกูล...
การขยายพหุนามและทฤษฎีบทตัวคั่น
แนวคิดที่แข็งแกร่งกว่าคือการขยายพหุนามหมายความว่าฟังก์ชันfที่ใช้ในการจำกัดความหนาแน่นของขอบของไมเนอร์ตื้นเป็นพหุนามหากตระกูลกราฟสืบทอดเป็นไปตามทฤษฎีบทตัวแยกซึ่งระบุว่า กราฟ nจุดยอดใดๆ ในตระกูลสามารถแยกออกเป็นชิ้นส่วนที่มีจุดยอดไม่เกินn /2 จุดยอดโดยการลบ...
คลาสของกราฟที่มีการขยายแบบจำกัด
เนื่องจากความเชื่อมโยงระหว่างตัวแยกและการขยายกราฟตระกูลปิดไมเนอร์ทุกตระกูลรวมถึงตระกูลกราฟระนาบจึงมีการขยายพหุนาม เช่นเดียวกับกราฟระนาบ 1 มิติและโดยทั่วไปแล้วกราฟที่สามารถฝังลงบนพื้นผิวที่มีจีนัสจำกัดและมีจำนวนจุดตัดต่อขอบจำกัด รวมถึงกราฟสตริงที่ปราศจากไบคลิก...