היפרגרף

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

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

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

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

סדרת הדרגות

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

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

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

• תבנית:MathWorld
• תבנית:דף שער בספרייה הלאומית