היפרגרף

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

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

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

היפרגרף נקרא $k$-היפרגרף אם כל קשת מכילה $k$ צמתים. בפרט, גרף הוא $2$-היפרגרף.

סדרת הדרגות

הדרגה $d(v)$ של צומת $v$ בהיפרגרף $G=\left(V,E\right)$ היא מספר הקשתות בהיפרגרף המכילות את $v$.

סדרת הדרגות של היפרגרף עם $n$ צמתים וסדר $v_{1},...,v_{n}$ של הצמתים היא הסדרה $d(G)=\left(d(v_{1}),...,d(v_{n})\right)$. סדרה נקראת $k$-גרפית אם היא סדרת הדרגות של איזשהו $k$-היפרגרף. בעיית ההחלטה האם סדרה נתונה היא $k$-גרפית פתירה בזמן פולינומי עבור $k=2$ ( Erdős and Gallai, 1960) אך NP-complete לכל $k\geq 3$ ( 2018 ,.Deza et al).

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

• היפרגרף, באתר MathWorld (באנגלית)
• היפרגרפים, דף שער בספרייה הלאומית

הערות שוליים

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