ในทฤษฎีกราฟไมเนอร์ตื้นหรือไมเนอร์ที่มีความลึกจำกัดคือรูปแบบที่จำกัดของไมเนอร์กราฟซึ่งกราฟย่อยที่ถูกยุบเพื่อสร้างไมเนอร์นั้นมีเส้นผ่านศูนย์กลาง เล็ก ไมเนอร์ตื้นได้รับการแนะนำโดยPlotkin, Rao & Smith (1994)ซึ่งระบุว่าการคิดค้นนี้เป็นผลงานของCharles E. Leisersonและ Sivan Toledo ^{[ 1 ]}

วิธีหนึ่งในการกำหนดไมเนอร์ของกราฟแบบไม่มีทิศทางGคือการระบุซับกราฟHของGและกลุ่มของเซตย่อยที่ไม่ซ้ำกันS ของจุดยอดของGซึ่งแต่ละเซตย่อยจะสร้างซับกราฟเหนี่ยวนำที่เชื่อมต่อกันH ของHไมเนอร์จะมีจุดยอดv สำหรับแต่ละเซตย่อยS และมีขอบ v v เมื่อใดก็ตามที่มีขอบจากS ไปยังS ที่ อยู่ในH

ในการกำหนดสูตรนี้ ไมเนอร์ตื้น d (หรือเรียกอีกอย่างว่าไมเนอร์ตื้นที่มีความลึกd ) คือไมเนอร์ที่สามารถกำหนดได้ในลักษณะที่กราฟย่อยH แต่ละกราฟ มีรัศมีไม่เกินdซึ่งหมายความว่ามีจุดยอดกลางc ที่อยู่ภายในระยะd จาก ^จุดยอดอื่นๆ ทั้งหมดของH โปรดทราบว่าระยะทางนี้วัดจากจำนวนฮอปในH และด้วยเหตุนี้จึงอาจมีขนาดใหญ่กว่าระยะทางในG ^{[ 1} ]

ไมเนอร์ตื้นที่มีความลึกเป็นศูนย์นั้นเหมือนกับซับกราฟของกราฟที่กำหนด สำหรับค่าd ที่มีขนาดใหญ่พอสมควร (รวมถึงค่าทั้งหมดที่มีขนาดใหญ่อย่างน้อยเท่ากับจำนวนจุดยอด) ไมเนอร์ตื้น dของกราฟที่กำหนดจะตรงกับไมเนอร์ทั้งหมดของกราฟนั้น^{[ 1 ]}

Nešetřil & Ossona de Mendez (2012)ใช้ไมเนอร์ตื้นเพื่อแบ่งตระกูลของกราฟจำกัดออกเป็นสองประเภท พวกเขากล่าวว่าตระกูลกราฟFมีความหนาแน่นในบางจุดหากมีค่าd ที่จำกัด ซึ่ง ไมเนอร์ตื้น dของกราฟในFประกอบด้วยกราฟจำกัดทุกกราฟ มิฉะนั้น พวกเขากล่าวว่าตระกูลกราฟนั้น ไม่มี ความหนาแน่นในบางจุด^{[ 2 ]}คำศัพท์นี้ได้รับการพิสูจน์แล้วจากข้อเท็จจริงที่ว่า หากFเป็นคลาสของกราฟที่ไม่มีความหนาแน่นในบางจุด (สำหรับทุก ε > 0) กราฟ nจุดยอดในFจะมี ขอบ O ( n ^{1 + ε} ) ดังนั้น กราฟที่ไม่มีความหนาแน่นในบางจุดจึงเป็นกราฟเบาบาง^{[ 3 ]}

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

ดังที่Plotkin, Rao & Smith (1994)แสดงให้เห็น กราฟที่มีไมเนอร์ตื้นที่ถูกยกเว้นสามารถแบ่งส่วนได้ในลักษณะเดียวกับทฤษฎีบทตัวแยกระนาบสำหรับกราฟระนาบโดยเฉพาะอย่างยิ่ง หากกราฟสมบูรณ์K ไม่ใช่ไมเนอร์ตื้นd ของกราฟ nจุดยอดGแล้วจะมีเซตย่อยSของGที่มีขนาดO ( dh ² log n + n / d )ซึ่งแต่ละส่วนประกอบที่เชื่อมต่อกันของG \ Sมีจุดยอดไม่เกิน 2 n /3 จุด ผลลัพธ์นี้เป็นแบบสร้างสรรค์ กล่าวคือ มีอัลกอริทึมเวลาพหุนามที่สามารถค้นหาตัวแยกดังกล่าว หรือไมเนอร์ตื้นd K ^{[ 5 ]} ผลที่ตามมาคือ พวกเขาแสดงให้เห็นว่าตระกูลกราฟที่ปิดไมเนอร์ทุกตระกูลปฏิบัติตามทฤษฎีบทตัวแยกที่แข็งแกร่งเกือบเท่ากับทฤษฎีบทสำหรับกราฟระนาบ

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

โดยทั่วไปแล้ว ตระกูลกราฟที่สืบทอดทางพันธุกรรมจะมีทฤษฎีบทตัวคั่น โดยที่ขนาดของตัวคั่นจะเป็นกำลังย่อยเชิงเส้นของnก็ต่อเมื่อมีการขยายพหุนาม^{[ 6 ]}

• ดโวชาก, Zdeněk ; Norin, Sergey (2015), ตัวคั่นซับลิเนียร์แบบ Strongly และการขยายตัวแบบพหุนาม , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D.
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc . 5th ACM-SIAM Symp. on Discrete Algorithms (SODA) , pp.  462–470.
• Teng, Shang-Hua (1998), "แง่มุมเชิงการจัดเรียงของกราฟเรขาคณิต", Comput. Geom. , 9 (4): 277– 287, doi : 10.1016/S0925-7721(96)00008-9 , MR  1609578.
• Wulff-Nilsen, Christian (2011), "ทฤษฎีบทตัวคั่นสำหรับกราฟที่ไม่มีไมเนอร์และกราฟที่ไม่มีไมเนอร์แบบตื้น พร้อมการประยุกต์ใช้", Proc. 52nd IEEE Symp. Foundations of Computer Science (FOCS) , หน้า  37–46 , arXiv : 1107.1292 , doi : 10.1109/FOCS.2011.15 , ISBN 978-0-7695-4571-4.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.