היפרגרף
היפרגרף (אנגלית: 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 $ ([1] Erdős and Gallai, 1960) אך NP-complete לכל $ k\geq 3 $ ([2] 2018 ,.Deza et al).
קישורים חיצוניים
הערות שוליים
- ↑ P. Erdős, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lopak 11, 1960, עמ' 264-274
- ↑ Antoine Deza, Asaf Levin, Syed M. Meesum, Shmuel Onn, Optimization over Degree Sequences, SIAM Journal on Discrete Mathematics 32, 2018-01, עמ' 2067–2079 doi: 10.1137/17M1134482
| נושאים בתורת הגרפים | ||
|---|---|---|
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי | |
היפרגרף30735315Q840247