อ่าน 3 นาที
การวาดภาพแบบครอบงำ
การวาดแบบโดมิแนนซ์เป็นรูปแบบการวาดกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งทำให้ ความสัมพันธ์ ในการเข้าถึงระหว่างจุดยอดปรากฏให้เห็นได้ชัดเจน ในการวาดแบบโดมิแนนซ์
การวาดภาพแบบครอบงำ

การวาดแบบโดมิแนนซ์เป็นรูปแบบการวาดกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งทำให้ ความสัมพันธ์ ในการเข้าถึงระหว่างจุดยอดปรากฏให้เห็นได้ชัดเจน ในการวาดแบบโดมิแนนซ์ จุดยอดจะถูกวางไว้ที่จุดที่แตกต่างกันบนระนาบยูคลิดและจุดยอดvสามารถเข้าถึงได้จากจุดยอดuก็ต่อเมื่อพิกัดคาร์ทีเซียนของv ทั้งสอง มากกว่าหรือเท่ากับพิกัดของuขอบของการวาดแบบโดมิแนนซ์อาจวาดเป็นส่วนของเส้น ตรง หรือในบางกรณีเป็นโซ่รูปหลายเหลี่ยม[ 1 ]
กราฟระนาบ
กราฟระนาบst ที่ ลดรูปเชิงส่งผ่าน ทุก กราฟ ซึ่งเป็น กราฟระนาบแบบมีทิศทางที่ไม่มีวงจรมีแหล่งกำเนิดเดียวและจุดรับเดียว ทั้งสองอยู่บนหน้าด้านนอกของการฝังตัวของกราฟนั้น จะมีภาพวาดแบบครอบงำ (dominance drawing) อัลกอริทึมแบบซ้าย-ขวาสำหรับการค้นหาภาพวาดเหล่านี้ กำหนด พิกัด xของทุกจุดยอดให้เป็นตำแหน่งของจุดยอดนั้นใน ลำดับ การค้นหาแบบเจาะลึก (depth-first search)ของกราฟ โดยเริ่มจากsและให้ความสำคัญกับขอบในลำดับจากขวาไปซ้าย และกำหนด พิกัด yให้ได้ในลักษณะเดียวกัน แต่ให้ความสำคัญกับขอบในลำดับจากซ้ายไปขวา อัลกอริทึมการวาดภาพแบบครอบงำโดยทั่วไปจะรวมขั้นตอนการบีบอัดอีกขั้นตอนหนึ่งหลังจากกำหนดพิกัดนี้ โดยเลื่อนจุดยอดลงและไปทางซ้ายให้มากที่สุดเท่าที่จะเป็นไปได้ในขณะที่ยังคงรักษาคุณสมบัติของภาพวาดแบบครอบงำไว้ ภาพวาดที่ได้จะอยู่ภายในตารางจำนวนเต็มn × nและแสดงสมมาตรหลายอย่างของการฝังตัวเชิงโทโพโลยีพื้นฐาน ภาพวาดนี้ และโดยทั่วไปแล้วภาพวาดการครอบงำทุกภาพของ กราฟ st -planar ที่ลดทอนแบบถ่ายทอด จะต้องเป็นระนาบที่มีขอบเป็นเส้นตรง[ 1 ] [ 2 ]
สำหรับ กราฟระนาบ stที่ไม่ได้ลดรูปอย่างถ่ายทอด กราฟที่ลดรูปอย่างถ่ายทอดที่เทียบเท่ากันอาจได้มาโดยการแบ่งขอบแต่ละขอบออก อย่างไรก็ตาม การวาดเส้นตรงของกราฟที่ลดรูปอย่างถ่ายทอดที่ได้ จะสร้างภาพวาดของกราฟดั้งเดิมซึ่งขอบบางขอบมีส่วนโค้งงอ ณ จุดยอดเสมือนที่เกิดจากการแบ่งย่อย[ 1 ] [ 2 ]การวาดแบบครอบงำระนาบไม่จำเป็นต้องเป็นการวาดแบบระนาบขึ้นด้านบนเสมอไป เพราะขอบบางขอบอาจเป็นแนวนอน แต่การหมุน 45° จะทำให้ได้ภาพวาดแบบระนาบขึ้นด้านบนอย่างแน่นอน[ 1 ] เมื่อเปรียบเทียบกับวิธีการอื่นๆ สำหรับการวาดกราฟแบบไม่มีวงจรทิศทาง พบว่าอัลกอริทึมซ้าย-ขวา (พร้อมกับขั้นตอนการประมวลผลล่วงหน้าแบบระนาบ) ทำงานได้ดีในแง่ของพื้นที่ของภาพวาดที่สร้างขึ้น จำนวนส่วนโค้งงอ และอัตราส่วนของภาพวาด แต่ทำงานได้ไม่ดีนักในแง่ของความยาวขอบทั้งหมด[ 3 ]
กราฟที่ไม่ระนาบ
กราฟแบบมีทิศทางที่ไม่มีวงจร (โดยไม่คำนึงถึงระนาบ) จะมีภาพวาดการครอบงำก็ต่อเมื่อเซตของจุดยอดที่เรียงลำดับบางส่วนซึ่งเรียงลำดับตามการเข้าถึงได้มีมิติลำดับสอง ภาพวาดการครอบงำ (ที่หมุนแล้ว) ของกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งลดทอนแบบส่งผ่านอาจใช้เป็นแผนภาพ Hasseของลำดับบางส่วนที่สอดคล้องกัน[ 4 ]
การครอบงำร่วม
เมื่อกำหนดภาพวาดการครอบงำของกราฟแบบมีทิศทางที่ไม่มีวงจรD 1 = ( V , E 1 ) การกลับการตีความแกนหนึ่งจะส่งผลให้เกิดความสัมพันธ์ใหม่ที่เรียกว่าการเข้าถึงร่วมกันได้ดังนั้น จุด ( x a , y a ) อาจถือว่าเข้าถึงร่วมกันได้จากจุด ( x b , y b ) เมื่อใดก็ตามที่x a ≥ x bแต่y a ≤ y bด้วยวิธีนี้ ภาพวาดการครอบงำอาจถูกมองว่าเหนี่ยวนำให้เกิดกราฟแบบมีทิศทางที่ไม่มีวงจรที่สองD 2 = ( V , E 2 ) บนเซตจุดยอดเดียวกัน คู่ {≤ 1 , ≤ 2 } ของลำดับบางส่วนบนเซตพื้นฐานที่ใช้ร่วมกันซึ่งอนุญาตให้มีการแสดงพร้อมกันดังกล่าวโดยภาพวาดเดียว—ซึ่งตีความในแง่ของการเข้าถึงและการเข้าถึงร่วมกันได้—เรียกว่าcodominant [ 5 ]
การวาดภาพที่มีอำนาจเหนือกว่าอย่างอ่อนแอ
สำหรับกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งลำดับการเข้าถึงมีมิติสูงกว่าการวาดแบบครอบงำอย่างอ่อนคือการวาดที่ขอบทุกเส้นมีทิศทางขึ้น ไปทางขวา หรือทั้งสองอย่าง แต่มีคู่ของจุดยอด ( u , v ) ที่uครอบงำvตามพิกัด แต่vไม่สามารถเข้าถึงได้จากuในกราฟ เรากล่าวว่าจุดยอดuครอบงำจุดยอดv อีกจุดหนึ่ง หากพิกัด (u_x, u_y) ของuน้อยกว่าหรือเท่ากับพิกัด (v_x, v_y) ของv กล่าว คือ u_x <= v_x และ u_y <= v_y เมื่อพิจารณาระนาบ XY เป้าหมายในการวาดแบบนี้คือการลดจำนวน เส้นทางที่บ่งบอกผิดพลาด ดัง กล่าวให้น้อยที่สุด[ 6 ]
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ การวาดภาพแบบครอบงำ
การวาดแบบโดมิแนนซ์เป็นรูปแบบการวาดกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งทำให้ ความสัมพันธ์ ในการเข้าถึงระหว่างจุดยอดปรากฏให้เห็นได้ชัดเจน ในการวาดแบบโดมิแนนซ์
กราฟระนาบ
กราฟระนาบ st ที่ ลดรูปเชิงส่งผ่าน ทุก กราฟ ซึ่งเป็น กราฟระนาบ แบบมีทิศทางที่ไม่มีวงจรมีแหล่งกำเนิดเดียวและจุดรับเดียว ทั้งสองอยู่บนหน้าด้านนอกของการฝังตัวของกราฟนั้น จะมีภาพวาดแบบครอบงำ (dominance drawing) อัลกอริทึมแบบซ้าย-ขวา สำหรับการค้นหาภาพวาดเหล่านี้...
กราฟที่ไม่ระนาบ
กราฟแบบมีทิศทางที่ไม่มีวงจร (โดยไม่คำนึงถึงระนาบ) จะมีภาพวาดการครอบงำก็ต่อเมื่อ เซต ของจุดยอดที่เรียงลำดับบางส่วนซึ่งเรียงลำดับตามการเข้าถึงได้มี มิติลำดับ สอง ภาพวาดการครอบงำ (ที่หมุนแล้ว) ของกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งลดทอนแบบส่งผ่านอาจใช้เป็น แผนภาพ...
การครอบงำร่วม
เมื่อกำหนดภาพวาดการครอบงำของกราฟแบบมีทิศทางที่ไม่มีวงจร D 1 = ( V , E 1 ) การกลับการตีความแกนหนึ่งจะส่งผลให้เกิดความสัมพันธ์ใหม่ที่เรียกว่า การเข้าถึงร่วมกันได้ ดังนั้น จุด ( x a , y a ) อาจถือว่าเข้าถึงร่วมกันได้จากจุด ( x b , y b ) เมื่อใดก็ตามที่ x a ≥ x b...