ในทางคณิตศาสตร์ โครงสร้างความสัมพันธ์เชิงตกกระทบ ( incidence structure)คือระบบนามธรรมที่ประกอบด้วยวัตถุสองประเภทและความสัมพันธ์เพียงหนึ่งเดียวระหว่างวัตถุทั้งสองประเภทนี้ ลองพิจารณาจุดและเส้นตรงในระนาบยุคลิดเป็นวัตถุสองประเภท และละเว้นคุณสมบัติทางเรขาคณิตทั้งหมด ยกเว้นความสัมพันธ์ระหว่างจุดกับเส้นตรงว่าจุดใดตกกระทบกับเส้นตรงใด สิ่งที่เหลืออยู่คือโครงสร้างความสัมพันธ์เชิงตกกระทบของระนาบยุคลิด

โครงสร้างเหตุการณ์มักถูกพิจารณาในบริบททางเรขาคณิต โดยที่โครงสร้างเหล่านี้ถูกแยกออกจากระนาบ (เช่นระนาบแอฟฟิ น ระนาบโปรเจคทีฟและระนาบโมเบียส ) และจึงทำให้เป็นภาพรวม แต่แนวคิดนี้กว้างมากและไม่จำกัดเฉพาะการตั้งค่าทางเรขาคณิต แม้ในการตั้งค่าทางเรขาคณิต โครงสร้างเหตุการณ์ก็ไม่ได้จำกัดอยู่แค่จุดและเส้นเท่านั้น วัตถุที่มีมิติสูงกว่า ( ระนาบของแข็งปริภูมิ n มิติภาคตัดกรวย ฯลฯ) ก็สามารถนำมาใช้ได้ เช่นกัน การศึกษาโครงสร้างจำกัดบางครั้งเรียกว่าเรขาคณิตจำกัด^{[ 1 ]}

โครงสร้างเหตุการณ์คือสามสิ่ง ( P , L , I ) โดยที่Pคือเซตที่มีองค์ประกอบเรียกว่าจุด L คือเซตที่แตกต่างกันซึ่งมีองค์ประกอบเรียกว่าเส้นและI ⊆ P × Lคือความสัมพันธ์เหตุการณ์องค์ประกอบของIเรียกว่าธงถ้า ( p , l ) อยู่ในIแล้วเราอาจกล่าวได้ว่าจุดp "อยู่บน" เส้นlหรือว่าเส้นl "ผ่าน" จุดpคำศัพท์ที่ "สมมาตร" มากกว่า เพื่อสะท้อนถึง ลักษณะ สมมาตรของความสัมพันธ์นี้ คือ " pเป็นเหตุการณ์กับl " หรือ " l ^เป็นเหตุการณ์กับp " และใช้สัญลักษณ์p I lแทน( p , l ) ∈ I [ ^{2 ]}

ในบางสถานการณ์ทั่วไปLอาจเป็นเซตของเซตย่อยของPซึ่งในกรณีนี้ ความสัมพันธ์Iจะเป็นการบรรจุ ( p I lก็ต่อเมื่อpเป็นสมาชิกของl ) โครงสร้างความสัมพันธ์ประเภทนี้เรียกว่าเซตเชิงทฤษฎี [ ^{3 ] นี่}ไม่ใช่กรณีเสมอไป ตัวอย่างเช่น ถ้าPเป็นเซตของเวกเตอร์และLเป็นเซตของเมทริกซ์จัตุรัสเราอาจกำหนด ตัวอย่างนี้ยังแสดงให้เห็นว่าในขณะที่ใช้ภาษาเรขาคณิตของจุดและเส้น ประเภทของวัตถุไม่จำเป็นต้องเป็นวัตถุทางเรขาคณิตเหล่านี้ $${\displaystyle I=\{(v,M):{\vec {v}}{\text{ เป็นเวกเตอร์ลักษณะเฉพาะของเมทริกซ์ }}M\}.}$$

โครงสร้างการเกิดเหตุการณ์จะเรียกว่าสม่ำเสมอหากแต่ละเส้นเชื่อมต่อกับจุดจำนวนเท่ากัน ตัวอย่างทั้งหมดนี้ ยกเว้นตัวอย่างที่สอง เป็นแบบสม่ำเสมอ โดยมีสามจุดต่อเส้น

กราฟใดๆ(ซึ่งไม่จำเป็นต้องเป็นกราฟแบบง่าย อาจ มีวงวนและเส้นขอบหลายเส้นก็ได้) เป็นโครงสร้างความสัมพันธ์แบบสม่ำเสมอ โดยมีจุดสองจุดต่อหนึ่งเส้น สำหรับตัวอย่างเหล่านี้ จุดยอดของกราฟประกอบเป็นเซตของจุด เส้นขอบของกราฟประกอบเป็นเซตของเส้น และความสัมพันธ์หมายความว่าจุดยอดเป็นจุดปลายของเส้นขอบ

โครงสร้างเหตุการณ์มักไม่ค่อยได้รับการศึกษาอย่างครบถ้วนสมบูรณ์ โดยทั่วไปแล้วมักจะศึกษาโครงสร้างเหตุการณ์ที่สอดคล้องกับสัจพจน์เพิ่มเติมบางประการ ตัวอย่างเช่นปริภูมิเชิงเส้นบางส่วนเป็นโครงสร้างเหตุการณ์ที่สอดคล้องกับเงื่อนไขดังต่อไปนี้:

1. จุดสองจุดที่แตกต่างกันจะอยู่บนเส้นร่วมอย่างมากที่สุดเพียงเส้นเดียว และ
2. เส้นทุกเส้นจะตัดกับจุดอย่างน้อยสองจุด

หากแทนที่สัจพจน์แรกข้างต้นด้วยสัจพจน์ที่แข็งแกร่งกว่า:

3. จุดสองจุดที่แตกต่างกันจะอยู่บนเส้นตรงร่วมกันเพียงเส้นเดียวเท่านั้น

โครงสร้างเหตุการณ์เรียกว่าพื้นที่เชิงเส้น^{[ 4 ] [ 5 ]}

ตัวอย่างที่เฉพาะเจาะจงมากขึ้นคือk -netนี่คือโครงสร้างความสัมพันธ์ที่เส้นตรงแบ่งออกเป็นk กลุ่มขนานกันโดยที่เส้นตรงสองเส้นในกลุ่มขนานเดียวกันจะไม่มีจุดร่วมกัน แต่เส้นตรงสองเส้นในกลุ่มขนานที่ต่างกันจะมีจุดร่วมกันเพียงจุดเดียว และแต่ละจุดจะอยู่บนเส้นตรงเพียงเส้นเดียวจากแต่ละกลุ่มขนาน ตัวอย่างของk -net คือเซตของจุดบนระนาบเชิงเส้นพร้อมกับkกลุ่มขนานของเส้นตรงเชิงเส้น

ถ้าเราสลับบทบาทของ "จุด" และ "เส้น" ใน เราจะได้โครงสร้างคู่ขนานโดย ที่I ^∗คือความสัมพันธ์ผกผันของIซึ่งเป็นไปตามนิยามโดยตรงว่า: $${\displaystyle C=(P,L,I)}$$$${\displaystyle C^{*}=(แอล,พี,ฉัน^{*})}$$$${\displaystyle C^{**}=C}$$

นี่คือเวอร์ชันนามธรรมของความเป็นคู่เชิงฉายภาพ^{[ 2 ]}

โครงสร้างCที่สมมาตรกับโครงสร้างคู่C ^∗เรียกว่าโครงสร้างคู่ตัวเอง (self-dual ) ระนาบฟาโนด้านบนเป็นโครงสร้างเหตุการณ์คู่ตัวเอง (self-dual incidence structure)

แนวคิดของโครงสร้างเหตุการณ์นั้นเรียบง่ายมากและเกิดขึ้นในหลายสาขาวิชา โดยแต่ละสาขาวิชาได้นำเสนอคำศัพท์เฉพาะของตนเองและระบุประเภทของคำถามที่มักถามเกี่ยวกับโครงสร้างเหล่านี้ โครงสร้างเหตุการณ์ใช้ศัพท์ทางเรขาคณิต แต่ในทฤษฎีกราฟเรียกว่าไฮเปอร์กราฟและในทฤษฎีการออกแบบเชิงการจัดเรียงเรียกว่าการออกแบบบล็อกนอกจากนี้ยังรู้จักกันในชื่อระบบเซตหรือตระกูลของเซตในบริบททั่วไป อีกด้วย

แต่ละไฮเปอร์กราฟหรือระบบเซตสามารถมองได้ว่าเป็นโครงสร้างความสัมพันธ์แบบเหตุการณ์ โดยที่เซตสากลทำหน้าที่เป็น "จุด" กลุ่มของเซตย่อย ที่สอดคล้องกัน ทำหน้าที่เป็น "เส้น" และความสัมพันธ์แบบเหตุการณ์คือการเป็นสมาชิกของเซต " ∈ " ในทางกลับกัน โครงสร้างความสัมพันธ์แบบเหตุการณ์ทุกโครงสร้างสามารถมองได้ว่าเป็นไฮเปอร์กราฟโดยการระบุเส้นกับเซตของจุดที่เชื่อมต่อกับเส้นเหล่านั้น

แบบแผนบล็อก (ทั่วไป) คือเซตXพร้อมกับกลุ่มFของเซตย่อยของX (อนุญาตให้มีเซตย่อยซ้ำได้) โดยปกติแล้ว แบบแผนบล็อกจะต้องเป็นไปตามเงื่อนไขความสม่ำเสมอเชิงตัวเลข ในฐานะโครงสร้างเหตุการณ์Xคือเซตของจุด และFคือเซตของเส้น ซึ่งโดยทั่วไปเรียกว่าบล็อกในบริบทนี้ (บล็อกที่ซ้ำกันต้องมีชื่อที่แตกต่างกัน ดังนั้นFจึงเป็นเซต ไม่ใช่มัลติเซต) ถ้าเซตย่อยทั้งหมดในFมีขนาดเท่ากัน แบบแผนบล็อกนั้นเรียกว่า แบบแผนบล็อก เอกรูปถ้าแต่ละองค์ประกอบของXปรากฏในจำนวนเซตย่อยเท่ากัน แบบแผนบล็อกนั้นเรียกว่า แบบแผนบล็อกปกติแบบแผนคู่ขนานของแบบแผนเอกรูปคือแบบแผนบล็อกปกติ และในทางกลับกัน

พิจารณารูปแบบบล็อก/ไฮเปอร์กราฟที่กำหนดโดย: $${\displaystyle {\begin{aligned}P&=\{1,2,3,4,5,6,7\},\\[2pt]L&=\left\{{\begin{array}{ll}\{1,2,3\},&\{1,4,5\},\\\{1,6,7\},&\{2,4,6\},\\\{2,5,7\},&\{3,4,7\},\\\{3,5,6\}\end{array}}\right\}.\end{aligned}}}$$

โครงสร้างการตกกระทบนี้เรียกว่าระนาบฟาโน (Fano plane ) ในแง่ของการออกแบบบล็อก มันมีความสม่ำเสมอและเป็นระเบียบ

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

โครงสร้างเหตุการณ์อาจแสดงได้หลายวิธี หากเซตPและLเป็นเซตจำกัด การแสดงผลเหล่านี้สามารถเข้ารหัสข้อมูลที่เกี่ยวข้องทั้งหมดเกี่ยวกับโครงสร้างได้อย่างกระชับ

เมทริกซ์เหตุการณ์ของโครงสร้างเหตุการณ์ (จำกัด) คือเมทริกซ์ (0,1)ที่มีแถวที่จัดทำดัชนีโดยจุด{p _i }และคอลัมน์ที่จัดทำดัชนีโดยเส้น{ l _j }โดยที่ รายการ ijเป็น 1 ถ้าp _i I l _jและเป็น 0 มิฉะนั้น^{[ a ]} ​​เมทริกซ์เหตุการณ์ไม่ได้ถูกกำหนดอย่างเฉพาะเจาะจง เนื่องจากขึ้นอยู่กับการเรียงลำดับโดยพลการของจุดและเส้น^{[ 6 ]}

โครงสร้างการเกิดเหตุการณ์ที่ไม่สม่ำเสมอที่แสดงในภาพด้านบน (ตัวอย่างที่ 2) กำหนดโดย: $${\displaystyle {\begin{aligned}P&=\{A,B,C,D,E,P\}\\[2pt]L&=\left\{{\begin{array}{ll}l=\{C,P,E\},&m=\{P\},\\n=\{P,D\},&o=\{P,A\},\\p=\{A,B\},&q=\{P,B\}\end{array}}\right\}\end{aligned}}}$$

เมทริกซ์อุบัติการณ์สำหรับโครงสร้างนี้คือ: ซึ่งสอดคล้องกับตารางอุบัติการณ์: $${\displaystyle {\begin{pmatrix}0&0&0&1&1&0\\0&0&0&0&1&1\\1&0&0&0&0&0\\0&0&1&0&0&0\\1&0&0&0&0&0\\1&1&1&1&0&1\end{pmatrix}}}$$

ถ้าโครงสร้างเหตุการณ์Cมีเมทริกซ์เหตุการณ์Mแล้ว โครงสร้างคู่C ^∗จะมีเมทริกซ์ทรานสโพสM ^Tเป็นเมทริกซ์เหตุการณ์ (และถูกกำหนดโดยเมทริกซ์นั้น)

โครงสร้างเหตุการณ์จะเรียกว่าเป็นคู่ในตัวเอง (self-dual) หากมีการเรียงลำดับจุดและเส้นที่ทำให้เมทริกซ์เหตุการณ์ที่สร้างขึ้นด้วยการเรียงลำดับนั้นเป็น เมทริกซ์สมมาตร

โดยใช้ป้ายกำกับตามตัวอย่างที่ 1 ข้างต้น และเรียงลำดับจุดเป็นA , B , C , D , G , F , Eและเรียงลำดับเส้นเป็นl , p , n , s , r , m , qระนาบ Fano จะมีเมทริกซ์เหตุการณ์ดังนี้: เนื่องจากเป็นเมทริกซ์สมมาตร ระนาบ Fano จึงเป็นโครงสร้างเหตุการณ์แบบคู่ในตัวเอง $${\displaystyle {\begin{pmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{pmatrix}}.}$$

รูปเหตุการณ์ (นั่นคือ การแสดงโครงสร้างเหตุการณ์) ถูกสร้างขึ้นโดยการแสดงจุดด้วยจุดในระนาบ และมีวิธีการมองเห็นบางอย่างในการเชื่อมจุดเพื่อให้สอดคล้องกับเส้น^{[ 6 ]}จุดอาจวางในลักษณะใดก็ได้ ไม่มีข้อจำกัดเกี่ยวกับระยะห่างระหว่างจุดหรือความสัมพันธ์ใดๆ ระหว่างจุด ในโครงสร้างเหตุการณ์ไม่มีแนวคิดของจุดที่อยู่ระหว่างจุดอื่นสองจุด ลำดับของจุดบนเส้นไม่ถูกกำหนด เปรียบเทียบกับเรขาคณิตแบบเรียงลำดับซึ่งมีแนวคิดเรื่องความเป็นระหว่างกัน ข้อความเดียวกันนี้สามารถกล่าวได้เกี่ยวกับการแสดงเส้น โดยเฉพาะอย่างยิ่ง เส้นไม่จำเป็นต้องแสดงด้วย "ส่วนของเส้นตรง" (ดูตัวอย่าง 1, 3 และ 4 ข้างต้น) เช่นเดียวกับการแสดงกราฟ ด้วยภาพ การตัดกันของ "เส้น" สองเส้นที่ตำแหน่งใดๆ นอกเหนือจากจุดไม่มีความหมายในแง่ของโครงสร้างเหตุการณ์ มันเป็นเพียงอุบัติเหตุของการแสดงเท่านั้น ตัวเลขอุบัติการณ์เหล่านี้อาจดูคล้ายกราฟในบางครั้ง แต่จะไม่ใช่กราฟหากโครงสร้างของอุบัติการณ์นั้นไม่ใช่กราฟ

โครงสร้างเหตุการณ์สามารถจำลองได้ด้วยจุดและเส้นโค้งในระนาบยุคลิดโดยใช้ความหมายทางเรขาคณิตปกติของเหตุการณ์ โครงสร้างเหตุการณ์บางอย่างยอมรับการแสดงด้วยจุดและเส้นตรง โครงสร้างที่สามารถทำได้เรียกว่าโครงสร้างที่สามารถทำให้เป็นจริงได้หากไม่ได้กล่าวถึงพื้นที่โดยรอบ จะถือว่าใช้ระนาบยุคลิด ระนาบ Fano (ตัวอย่างที่ 1 ข้างต้น) ไม่สามารถทำให้เป็นจริงได้เนื่องจากต้องใช้เส้นโค้งอย่างน้อยหนึ่งเส้น การกำหนดค่า Möbius–Kantor (ตัวอย่างที่ 4 ข้างต้น) ไม่สามารถทำให้เป็นจริงได้ในระนาบยุคลิด แต่สามารถทำให้เป็นจริงได้ในระนาบเชิงซ้อน^{[ 7 ]}ในทางกลับกัน ตัวอย่างที่ 2 และ 5 ข้างต้นสามารถทำให้เป็นจริงได้ และรูปเหตุการณ์ที่ให้ไว้ในนั้นแสดงให้เห็นสิ่งนี้ Steinitz (1894) ^{[ 8 ]}ได้แสดงให้เห็นว่าการกำหนดค่าn ₃ (โครงสร้างเหตุการณ์ที่มีnจุดและnเส้น สามจุดต่อเส้นและสามเส้นผ่านแต่ละจุด) สามารถทำให้เป็นจริงได้หรือต้องใช้เพียงเส้นโค้งเส้นเดียวในการแสดง^{[ 9 ]}ระนาบ Fano เป็นเอกลักษณ์ ( 7 ₃ ) และการกำหนดค่า Möbius–Kantor เป็นเอกลักษณ์ ( 8 ₃ )

โครงสร้างเหตุการณ์C แต่ละอัน สอดคล้องกับกราฟสองส่วนที่เรียกว่ากราฟ Leviหรือกราฟเหตุการณ์ของโครงสร้างนั้น เนื่องจากกราฟสองส่วนใดๆ ก็สามารถระบายสีได้สองสี กราฟ Levi จึงสามารถระบายสีจุดยอดเป็น สีดำและสีขาว ได้ โดยที่จุดยอดสีดำสอดคล้องกับจุด และจุดยอดสีขาวสอดคล้องกับเส้นของCขอบของกราฟนี้สอดคล้องกับธง (คู่จุด/เส้นเหตุการณ์) ของโครงสร้างเหตุการณ์ กราฟ Levi ดั้งเดิมคือกราฟเหตุการณ์ของรูปสี่เหลี่ยมทั่วไปลำดับที่สอง (ตัวอย่างที่ 3 ข้างต้น) ^{[ 10 ]}แต่คำนี้ได้รับการขยายโดยHSM Coxeter ^{[ 11 ]}เพื่ออ้างถึงกราฟเหตุการณ์ของโครงสร้างเหตุการณ์ใดๆ^{[ 12 ]}

กราฟ Levi ของระนาบ Fanoคือกราฟ Heawoodเนื่องจากกราฟ Heawood เป็นกราฟเชื่อมต่อและกราฟสลับจุดยอดจึงมีออโตมอร์ฟิซึม (เช่นเดียวกับที่กำหนดโดยการสะท้อนเกี่ยวกับแกนตั้งในรูปของกราฟ Heawood) ที่สลับจุดยอดสีดำและสีขาว ซึ่งในทางกลับกันหมายความว่าระนาบ Fano เป็นระนาบทวิภาคในตัวเอง

ภาพแสดงเฉพาะทางด้านซ้ายของกราฟ Levi ของการจัดเรียงแบบ Möbius–Kantor (ตัวอย่างที่ 4 ด้านบน) แสดงให้เห็นว่าการหมุนπ /4รอบจุดศูนย์กลาง (ไม่ว่าจะตามเข็มนาฬิกาหรือทวนเข็มนาฬิกา) ของแผนภาพจะสลับจุดยอดสีน้ำเงินและสีแดง และแมปขอบไปยังขอบ กล่าวคือ มีออโตมอร์ฟิซึมที่สลับสีของกราฟนี้ ดังนั้น โครงสร้างเหตุการณ์ที่เรียกว่าการจัดเรียงแบบ Möbius–Kantor จึงเป็นแบบทวิภาคในตัวเอง

เป็นไปได้ที่จะขยายแนวคิดของโครงสร้างเหตุการณ์ให้ครอบคลุมวัตถุมากกว่าสองประเภท โครงสร้างที่มี วัตถุ kประเภทเรียกว่าโครงสร้างเหตุการณ์อันดับkหรือเรขาคณิตอันดับk ^{[ 12} ] ในทางรูปธรรม สิ่งเหล่า นี้ถูกกำหนดเป็นทูเปิลk + 1 S = ( P ₁ , P ₂ , ..., ^P k _, I )โดยที่P _i ∩ P _j = ∅และ $${\displaystyle I\subseteq \bigcup _{i<j}P_{i}\times P_{j}.}$$

กราฟ Levi สำหรับโครงสร้างเหล่านี้ถูกกำหนดให้เป็นกราฟหลายส่วนโดยที่จุดยอดที่สอดคล้องกับแต่ละประเภทจะมีสีเดียวกัน

• อุบัติการณ์ (เรขาคณิต)
• เรขาคณิตของการตกกระทบ
• การกำหนดค่าเชิงฉาย
• โพลีโทปนามธรรม

• เบธ, โทมัส; จุงนิคเคล, ดีเตอร์; เลนซ์, ฮันฟรีด (1986), ทฤษฎีการออกแบบ , สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, ISBN 3-411-01675-2
• บิลิออตติ, เมาโร; จา, วิกรม; Johnson, Norman L. (2001), รากฐานของเครื่องบินแปล , Marcel Dekker , ISBN 0-8247-0609-9
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (ฉบับที่ 2), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
• Dembowski, Peter (1968), Finite geometries , Ergebnisse der Mathematik und ihrer Grenzgebiete , Band 44, Berlin, New York: Springer-Verlag , ISBN 3-540-61786-8, MR  0233275
• มัวร์เฮาส์, จี. เอริค (2014). "เรขาคณิตของการเกิดเหตุการณ์" (PDF) – ผ่านทางจอห์น เบซที่มหาวิทยาลัยแคลิฟอร์เนีย ริเวอร์ไซด์
• Pisanski, Tomaž; Servatius, Brigitte (2013), การกำหนดค่าจากมุมมองกราฟิก , Springer, doi : 10.1007/978-0-8176-8364-1 , ISBN 978-0-8176-8363-4

• CRC Press (2000). คู่มือคณิตศาสตร์เชิงดิสครีตและเชิงการจัดเรียง (บทที่ 12.2), ISBN 0-8493-0149-1
• Harold L. Dorwart (1966) เรขาคณิตของการตกกระทบ , Prentice Hall