היפרגרף

היפרגרף (אנגלית: Hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים. בעוד שבגרף פשוט קשת בין קודקוד $u$ וקודקוד $v$ מסומנת על ידי הזוג $(u,v)$, בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל $(u_{1},u_{2},u_{3},\ldots )$.

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

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

קישורים חיצוניים

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