อ่าน 4 นาที
เมทริกซ์คู่
ในทฤษฎีแมทรอยด์คู่ขนานของแมทรอยด์คือแมทรอยด์อีกตัวหนึ่งที่มีองค์ประกอบเดียวกันกับและเซตจะเป็นอิสระก็ต่อเมื่อมีเซตฐานที่ไม่ทับซ้อนกับเซตฐานนั้น เอ็ม{\displaystyle...
เมทริกซ์คู่
ในทฤษฎีแมทรอยด์คู่ขนานของแมทรอยด์คือแมทรอยด์อีกตัวหนึ่งที่มีองค์ประกอบเดียวกันกับและเซตจะเป็นอิสระก็ต่อเมื่อมีเซตฐานที่ไม่ทับซ้อนกับเซตฐานนั้น[ 1 ] [ 2 ] [ 3 ]
คู่แมทรอยด์ย้อนกลับไปถึงเอกสารต้นฉบับของHassler Whitneyที่กำหนดแมทรอยด์[ 4 ]พวกมันขยายแนวคิดของความเป็นคู่ของกราฟระนาบ ไปยังแมทรอย ด์
คุณสมบัติพื้นฐาน
ความเป็นคู่คือการผกผัน : สำหรับทุก, . [ 1 ] [ 3 ] [ 4 ]
นิยามทางเลือกของ matroid คู่คือชุดฐานของมันคือส่วนเติมเต็มของชุดฐานของ สัจพจน์การแลกเปลี่ยนฐานที่ใช้ในการกำหนด matroid จากฐานของมันนั้นเป็นสัจพจน์ที่เติมเต็มตัวเอง ดังนั้น matroid คู่จึงเป็น matroid อย่างแน่นอน[ 3 ]
แฟลตของเป็นส่วนเติมเต็มของเซตวัฏจักร (การรวมกันของวงจร) ของและในทางกลับกัน[ 3 ]
ถ้าเป็นฟังก์ชันอันดับของแมทรอยด์บนเซตพื้นฐานฟังก์ชันอันดับของแมทรอยด์คู่คือ[ 1 ] [ 3 ] [ 4 ]
ผู้เยาว์
ไมเนอร์ของแมทรอยด์ถูกสร้างขึ้นจากแมทรอยด์ที่ใหญ่กว่าโดยการดำเนินการสองอย่าง: การจำกัดจะลบองค์ประกอบออกจากโดยไม่เปลี่ยนแปลงความเป็นอิสระหรืออันดับของเซตที่เหลือ และการหดตัวจะลบออกจากหลังจากลบหนึ่งออกจากอันดับของทุกเซตที่เป็นสมาชิก การดำเนินการทั้งสองนี้เป็นแบบคู่กัน: และดังนั้น ไมเนอร์ของแบบคู่กันจึงเป็นสิ่งเดียวกันกับแบบคู่กันของไมเนอร์[ 5 ]
แมทรอยด์คู่ตัวเอง
แมทรอยด์แต่ละตัวจะเป็นแบบคู่ตัวเอง (โดยทั่วไปแล้วจะเป็นโพลีเฮดราแบบคู่ตัวเองสำหรับแมทรอยด์กราฟิก) หากมันสมมาตรกับคู่ของตัวเอง ความสมมาตรอาจทำให้องค์ประกอบของแมทรอยด์คงที่ แต่ไม่จำเป็นต้องเป็นเช่นนั้น อัลกอริทึมใดๆ ที่ทดสอบว่าแมทรอยด์ที่กำหนดเป็นแบบคู่ตัวเองหรือไม่ โดยให้สิทธิ์ในการเข้าถึงแมทรอยด์ผ่านออราเคิลอิสระจะต้องทำการสอบถามออราเคิลจำนวนเลขชี้กำลัง และด้วยเหตุนี้จึงไม่สามารถใช้เวลาแบบพหุนามได้[ 6 ]
ตระกูล Matroid
ตระกูลแมทริกซ์ที่สำคัญหลายตระกูลเป็นแบบคู่ในตัวเอง หมายความว่า แมทริกซ์ตัวหนึ่งจะอยู่ในตระกูลนั้นก็ต่อเมื่อคู่ของมันอยู่ในตระกูลนั้นด้วยเท่านั้น ตระกูลแมทริกซ์อื่นๆ อีกมากมายก็มาเป็นคู่ ตัวอย่างของปรากฏการณ์นี้ได้แก่:
- เมทริกซ์ไบนารี (เมทริกซ์ที่แสดงแทนได้เหนือGF(2) ) เมทริกซ์ที่แสดงแทนได้เหนือฟิลด์อื่น ๆ และเมทริกซ์ปกติล้วนเป็นตระกูลคู่ตัวเอง[ 7 ]
- แกมมอยด์ก่อตัวเป็นตระกูลคู่ตัวเอง แกมมอยด์ที่เข้มงวดเป็นคู่ตรงข้ามกับ แมทรอย ด์ตามขวาง[ 8 ]
- แมทรอยด์สม่ำเสมอและแมทรอยด์แบ่งส่วนเป็นคู่ของตัวเอง คู่สมของแมทรอยด์สม่ำเสมอคือแมทรอยด์สม่ำเสมอภายในตระกูลของแมทรอยด์สม่ำเสมอ แมทรอยด์ใดๆ ที่เป็นคู่สมกับตัวมันเองอย่างสมบูรณ์[ 9 ]
- เมทริกซ์ คู่ของเมทริกซ์กราฟิกจะเป็นเมทริกซ์กราฟิกก็ต่อเมื่อกราฟพื้นฐานเป็นกราฟระนาบเท่านั้น เมทริกซ์คู่ของกราฟระนาบจะเหมือนกับเมทริกซ์คู่ของเมทริกซ์ของกราฟ ดังนั้น ตระกูลของเมทริกซ์กราฟิกของกราฟระนาบจึงเป็นเมทริกซ์คู่ในตัวเอง[ 10 ]
- ในบรรดา matroid กราฟิก และโดยทั่วไปในบรรดา matroid ไบนารีmatroid แบบ bipartite (matroid ที่ทุกวงจรเป็นคู่) นั้นเป็นคู่ตรงข้ามกับmatroid แบบ Eulerian (matroid ที่สามารถแบ่งออกเป็นวงจรที่ไม่ซ้ำกันได้) [ 11 ] [ 12 ]
ยังคงเป็นคำถามที่ยังไม่มีคำตอบว่าตระกูลของเมทริกซ์พีชคณิตนั้นเป็นเมทริกซ์ทวิภาคในตัวเอง หรือไม่
ถ้าVเป็นปริภูมิเวกเตอร์และV * เป็นส่วนเติมเต็มเชิงตั้งฉาก ของ V แล้วเมทริกซ์เชิงเส้นของVและเมทริกซ์เชิงเส้นของV * จะเป็นคู่กัน ผลที่ตามมาคือ คู่กันของเมทริกซ์เชิงเส้นใดๆ ก็เป็นเมทริกซ์เชิงเส้นเช่นกัน[ 13 ]
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ เมทริกซ์คู่
ในทฤษฎีแมทรอยด์คู่ขนานของแมทรอยด์คือแมทรอยด์อีกตัวหนึ่งที่มีองค์ประกอบเดียวกันกับและเซตจะเป็นอิสระก็ต่อเมื่อมีเซตฐานที่ไม่ทับซ้อนกับเซตฐานนั้น เอ็ม{\displaystyle...
คุณสมบัติพื้นฐาน
ความเป็นคู่คือ การผกผัน : สำหรับทุก, . [ 1 ] [ 3 ] [ 4 ] เอ็ม {\displaystyle M} ( เอ็ม * ) * = เอ็ม {\displaystyle (M^{\ast })^{\ast }=M}
ผู้เยาว์
ไมเนอร์ของแมทรอยด์ ถูกสร้างขึ้นจากแมทรอยด์ที่ใหญ่กว่าโดยการดำเนินการสองอย่าง: การจำกัดจะลบองค์ประกอบออกจากโดยไม่เปลี่ยนแปลงความเป็นอิสระหรืออันดับของเซตที่เหลือ และการหดตัวจะลบออกจากหลังจากลบหนึ่งออกจากอันดับของทุกเซตที่เป็นสมาชิก...
แมทรอยด์คู่ตัวเอง
แมทรอยด์แต่ละตัวจะเป็นแบบคู่ตัวเอง (โดยทั่วไปแล้วจะเป็น โพลีเฮดราแบบคู่ตัวเอง สำหรับแมทรอยด์กราฟิก) หากมันสมมาตรกับคู่ของตัวเอง ความสมมาตรอาจทำให้องค์ประกอบของแมทรอยด์คงที่ แต่ไม่จำเป็นต้องเป็นเช่นนั้น อัลกอริทึมใดๆ...