การบรรจุในไฮเปอร์กราฟ

ในทางคณิตศาสตร์การบรรจุ (packing) ในไฮเปอร์กราฟคือการแบ่งเซตของขอบของไฮเปอร์กราฟออกเป็นเซตย่อยที่ไม่ซ้ำกันจำนวนหนึ่ง โดยที่ไม่มีขอบคู่ใดในแต่ละเซตย่อยใช้จุดยอดร่วมกัน มีอัลกอริทึมที่มีชื่อเสียงสองแบบที่ใช้ในการบรรจุให้ได้ผลลัพธ์ที่ดีที่สุดใน เชิงอะซิมโทติกในไฮเปอร์กราฟแบบ k -uniform อัลกอริทึมหนึ่งคืออัลกอริทึมแบบสุ่ม โลภ (random greedy algorithm)ซึ่งเสนอโดยJoel Spencerเขาใช้กระบวนการแตกแขนงเพื่อพิสูจน์ขอบเขตที่เหมาะสมที่สุดภายใต้เงื่อนไขบางประการ อีกอัลกอริทึมหนึ่งเรียกว่า Rödl nibble ซึ่งเสนอโดยVojtěch Rödlและคณะ พวกเขาแสดงให้เห็นว่าการบรรจุที่ทำได้โดย Rödl nibble นั้นใกล้เคียงกับการบรรจุที่ได้จากอัลกอริทึมแบบสุ่มโลภในบางแง่
ประวัติศาสตร์
ปัญหาการหาจำนวนของเซตย่อยดังกล่าวในไฮเปอร์กราฟแบบ k -uniform นั้น มีที่มาจากการคาดการณ์ของPaul ErdősและHaim Hananiในปี 1963 Vojtěch Rödlได้พิสูจน์การคาดการณ์ของพวกเขาในเชิงอะซิมโทติกภายใต้เงื่อนไขบางประการในปี 1985 Pippenger และJoel Spencerได้ขยายผลลัพธ์ของ Rödl โดยใช้อัลกอริทึมแบบโลภ แบบสุ่ม ในปี 1989
คำจำกัดความและศัพท์เฉพาะ
ในคำจำกัดความต่อไปนี้ไฮเปอร์กราฟจะถูกแทนด้วยH = ( V , E ) Hเรียกว่าไฮเปอร์กราฟk- ยูนิฟอร์ม ถ้าขอบทุกขอบในEประกอบด้วย จุดยอด kจุด พอดี
H คือ เซต ย่อยของขอบใน H ที่ไม่มีขอบที่แตกต่างกันสองคู่ใดที่มีจุดยอดร่วมกัน
คือ(,ไฮเปอร์กราฟที่ดีถ้ามีอยู่จริงโดยที่สำหรับทั้งหมดและและเงื่อนไขต่อไปนี้ทั้งสองข้อต้องเป็นจริง
ปริญญาของจุดยอดคือจำนวนขอบที่บรรจุและปริญญาร่วมประกอบด้วยจุดยอดสองจุดที่แตกต่างกันและคือจำนวนขอบที่ประกอบด้วยจุดยอดทั้งสองจุด
ทฤษฎีบท
มีการบรรจุเชิงอะซิมโทติกPที่มีขนาดอย่างน้อยสำหรับ-ไฮเปอร์กราฟแบบเอกรูปภายใต้เงื่อนไขสองประการต่อไปนี้
- จุดยอดทั้งหมดมีดีกรีเท่ากับซึ่งมีแนวโน้มเข้าสู่ค่าอนันต์
- สำหรับทุกคู่ของจุดยอด จะมีเพียงส่วนที่ใช้ร่วมกันเท่านั้นขอบร่วม
ที่ไหนคือจำนวนจุดยอดทั้งหมด ผลลัพธ์นี้แสดงให้เห็นโดย Pippenger และต่อมาได้รับการพิสูจน์โดย Joel Spencer เพื่อแก้ปัญหาการบรรจุไฮเปอร์กราฟเชิงอะซิมโทติก Joel Spencer ได้เสนออัลกอริทึมโลภแบบสุ่ม ในอัลกอริทึมนี้ กระบวนการแตกแขนงถูกใช้เป็นพื้นฐาน และแสดงให้เห็นว่าเกือบจะบรรลุการบรรจุที่เหมาะสมที่สุดในเชิงอะซิมโทติกภายใต้เงื่อนไขข้างต้นเสมอ
อัลกอริทึมการบรรจุแบบเชิงอะซิมโทติก
มีอัลกอริทึมที่มีชื่อเสียงสองแบบสำหรับการจัดเรียงไฮเปอร์กราฟ k-uniform ในเชิงอะซิมโทติก ได้แก่ อัลกอริทึมโลภแบบสุ่มผ่านกระบวนการแตกแขนง และนิบเบิลของ Rödl
อัลกอริทึมโลภแบบสุ่มผ่านกระบวนการแตกแขนง
ทุกขอบได้รับการกำหนด "เวลาเกิด" ที่แท้จริงที่แตกต่างกันอย่างเป็นอิสระและสม่ำเสมอขอบจะถูกเลือกทีละขอบตามลำดับเวลาเกิด ขอบได้รับการยอมรับและรวมอยู่ในหากมันไม่ทับซ้อนกับขอบที่ยอมรับไว้ก่อนหน้านี้ เห็นได้ชัดว่าเซตย่อยนั้นเป็นบรรจุภัณฑ์ และสามารถแสดงให้เห็นได้ว่าขนาดของมันคือเกือบจะแน่นอนเพื่อแสดงให้เห็นเช่นนั้น ให้หยุดกระบวนการเพิ่มขอบใหม่ ณ เวลาสำหรับค่าใดๆ ก็ตาม, เลือกโดยที่สำหรับใดๆ-ไฮเปอร์กราฟที่ดีที่ไหนแสดงถึงความน่าจะเป็นของจุดยอดการอยู่รอด (จุดยอดจะอยู่รอดหากไม่อยู่ในขอบใด ๆ ใน) จนถึงเวลาเห็นได้ชัดว่า ในสถานการณ์เช่นนี้ จำนวนที่คาดหวังของรอดชีวิตมาได้ ณ เวลานั้นน้อยกว่าดังนั้น ความน่าจะเป็นของการเอาชีวิตรอดจากการที่ด้อยกว่าสูงกว่ากล่าวอีกนัยหนึ่งคือต้องรวมอย่างน้อยจุดยอด ซึ่งหมายความว่า.
เพื่อให้การพิสูจน์เสร็จสมบูรณ์ จะต้องแสดงให้เห็นว่าด้วยเหตุนี้ พฤติกรรมเชิงอะซิมโทติกของการอยู่รอดนั้นจำลองโดยกระบวนการแตกแขนงอย่างต่อเนื่อง แก้ไขและเริ่มต้นด้วยอีฟ โดยมีวันเกิดคือสมมติว่าเวลาเดินถอยหลัง ดังนั้นอีฟจึงให้กำเนิดบุตรในช่วงเวลาดังกล่าวด้วย การแจกแจงปัวซงที่มีความหนาแน่นหนึ่งหน่วยความน่าจะเป็นที่อีฟจะมีการเกิดคือโดยการปรับเงื่อนไขตามเวลาเกิดมีการกระจายอย่างอิสระและสม่ำเสมอบนการเกิดทุกครั้งที่อีฟให้กำเนิดนั้นประกอบด้วย...ลูกหลานที่เกิดเวลาเดียวกันทั้งหมดกระบวนการนี้จะทำซ้ำสำหรับลูกหลานแต่ละตัว สามารถแสดงได้ว่าสำหรับทุกๆมีอยู่ดังนั้นจึงมีความน่าจะเป็นสูงกว่าอีฟมีเวลาอย่างมากที่สุดลูกหลาน
ต้นไม้ที่มีรากซึ่งมีแนวคิดเกี่ยวกับพ่อแม่ ลูก ราก ลำดับการเกิด และพี่น้องร่วมครรภ์ จะเรียกว่าต้นไม้สายวิวัฒนาการ โดยกำหนดให้ต้นไม้สายวิวัฒนาการมีจำนวนจำกัดเรากล่าวสำหรับแต่ละจุดยอดว่ามันจะอยู่รอดหรือตาย จุดยอดที่ไม่มีลูกหลานจะอยู่รอด จุดยอดจะตายก็ต่อเมื่อมันมีลูกหลานอย่างน้อยหนึ่งกลุ่มและทุกกลุ่มรอดชีวิต ให้แสดงถึงความน่าจะเป็นที่อีฟจะรอดชีวิตในต้นไม้แห่งสายเลือดโดยกำหนดตามกระบวนการข้างต้น วัตถุประสงค์คือเพื่อแสดงให้เห็นแล้วสำหรับค่าคงที่ใดๆสามารถแสดงให้เห็นได้ว่าความสัมพันธ์ทั้งสองนี้ทำให้ข้อโต้แย้งของเราสมบูรณ์
เพื่อแสดง, อนุญาต. สำหรับเล็ก,โดยประมาณแล้วก็คืออีฟที่เริ่มต้น ณ เวลาอาจมีการเกิดในช่วงเวลาที่กำหนดลูกๆ ของพวกเขาทุกคนมีชีวิตรอด ในขณะที่อีฟไม่มีลูกเลยซึ่งลูก ๆ ของพวกเขาทั้งหมดรอดชีวิต ปล่อยให้ส่งผลให้ได้สมการเชิงอนุพันธ์ค่าเริ่มต้นนำเสนอวิธีแก้ปัญหาที่ไม่เหมือนใครโปรดทราบว่าแท้จริงแล้ว.
เพื่อพิสูจน์ลองพิจารณาขั้นตอนที่เราเรียกว่า History ซึ่งจะยกเลิกหรือสร้างสายวิวัฒนาการ History ประกอบด้วยเซตของจุดยอด ในตอนเริ่มต้น.จะมีโครงสร้างต้นไม้ผสมพันธุ์ที่มีราก.เป็นได้ทั้งแบบแปรรูปแล้วและยังไม่แปรรูปในขั้นต้นยังไม่ผ่านกระบวนการใดๆ สำหรับแต่ละได้รับการกำหนดเวลาเกิดเราเริ่มต้นประวัติศาสตร์คือการนำเอาสิ่งที่ไม่ผ่านกระบวนการมาประมวลผลและดำเนินการดังต่อไปนี้ สำหรับค่าทั้งหมดกับแต่ไม่มีที่ได้รับการประมวลผลไปแล้ว หากอย่างใดอย่างหนึ่งมีและกับหรือบางส่วนมีกับและจากนั้นกระบวนการประวัติศาสตร์จะถูกยกเลิก มิฉะนั้นสำหรับแต่ละกับเพิ่มทั้งหมดถึงในฐานะเพื่อนร่วมครรภ์กับพ่อแม่และวันเกิดทั่วไป. ตอนนี้ถือว่าดำเนินการเสร็จสิ้นแล้ว ประวัติการทำงานจะหยุดลง หากไม่ถูกยกเลิก เมื่อทุกอย่างเสร็จสิ้นจะถูกประมวลผล หากประวัติไม่ยกเลิก ให้ดำเนินการกับ rootรอดชีวิตจากต้นพันธุ์ก็ต่อเมื่ออยู่รอดมาได้จนถึงเวลาสำหรับต้นพันธุ์ที่กำหนดไว้ ให้แสดงถึงความน่าจะเป็นที่กระบวนการแตกกิ่งจะให้ต้นพันธุ์ดังนั้น ความน่าจะเป็นที่ประวัติศาสตร์จะไม่ยุติลงคือเนื่องจากกระบวนการแตกแขนงมีขอบเขตจำกัดผลรวมของต้นไม้พ่อแม่พันธุ์ทั้งหมดและประวัติศาสตร์ก็ไม่ยุติลงการกระจายตัวของต้นพันธุ์เข้าใกล้การกระจายตัวของกระบวนการแตกแขนง ดังนั้น.
การกัดของ Rödl
ในปี 1985 โรดล์ได้พิสูจน์ข้อสันนิษฐานของพอล เออร์ดอส โดยใช้วิธีที่เรียกว่า โรดล์นิบเบิล ผลลัพธ์ของโรดล์สามารถกำหนดได้ในรูปแบบของปัญหาการบรรจุหรือปัญหาการครอบคลุม สำหรับหมายเลขการครอบคลุมที่ระบุโดยแสดงขนาดครอบครัวขั้นต่ำของ-เซตย่อยขององค์ประกอบซึ่งมีคุณสมบัติที่ทุกๆ-ชุดองค์ประกอบมีอยู่ในอย่างน้อยหนึ่งรายการ. พอล เออร์โดสและคณะ การคาดเดาคือ
- .
ที่ไหนข้อสันนิษฐานนี้หมายความโดยคร่าวๆ ว่าการจัดเรียงเชิงยุทธวิธีนั้นสามารถบรรลุได้ในเชิงอะซิมโทติก เราอาจกำหนดจำนวนการบรรจุในทำนองเดียวกันได้ขนาดสูงสุดของครอบครัวของ-เซตย่อยขององค์ประกอบมีคุณสมบัติที่ทุกคน-ชุดองค์ประกอบมีอยู่ในอย่างมากที่สุดหนึ่งชุด.
การบรรจุภายใต้เงื่อนไขที่เข้มงวดกว่า
ในปี 1997 โนกา อาลอน , จอง ฮัน คิมและโจเอล สเปนเซอร์ก็ได้จัดหาขอบเขตที่ดีให้กับภายใต้เงื่อนไขโคดีกรีที่เข้มงวดกว่าซึ่งแต่ละคู่ที่แตกต่างกันมีขอบร่วมกันอย่างมากที่สุดเพียงหนึ่งขอบ
สำหรับ ไฮ เปอร์กราฟk- เอกรูป D-ปกติ บน จุดยอด nจุด ถ้าk > 3 จะมีการบรรจุPที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกิน 3 จุดถ้าk = 3 จะมีการบรรจุPที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกิน 3 จุด.
ขอบเขตนี้เป็นที่ต้องการในแอปพลิเคชันต่างๆ เช่นระบบสามเท่าของสไตเนอร์ (Steiner Triple System ) ระบบสามเท่าของสไตเนอร์เป็นไฮเปอร์กราฟแบบง่าย 3-เอกรูป (3-uniform simple hypergraph) ซึ่งทุกคู่ของจุดยอดจะอยู่ในขอบเพียงหนึ่งเดียวเท่านั้น เนื่องจากระบบสามเท่าของสไตเนอร์เป็นแบบปกติd = ( n -1)/2 อย่างชัดเจน ขอบเขตข้างต้นจึงให้การปรับปรุงเชิงอะซิมโทติกดังต่อไปนี้
ระบบสามเหลี่ยมสไตเนอร์ใดๆ บน จุดยอด nจุด จะมีการบรรจุที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกิน.