היפרגרף

בתורת הגרפים, היפרגרף (hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים. בעוד שבגרף פשוט קשת בין קודקוד $u$ וקודקוד $v$ מסומנת על ידי הזוג $(u,v)$, בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל $(u_1, u_2, u_3, \ldots)$.

באופן פורמלי, היפרגרף בלתי מכוון $\ G=(V,E)$ מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת $\ e \in E$ היא קבוצה של שני צמתים או יותר מ-$\ V$, ומתקיים כי: $E \sube \mathcal{P}(V)$, כלומר: הקבוצה $\ E$ הינה תת-קבוצה של קבוצת החזקה של הקבוצה $\ V$.

היפרגרף מכוון מוגדר בדומה לגרף מכוון, כאשר כל קשת $\ e \in E$ מורכבת משתי קבוצות כל אחת בעלת צומת אחד או יותר מ-$\ V$, קבוצה של צמתים מהם הקשת יוצאת וקבוצה של צמתים אליהם הקשת נכנסת.

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.