היפרגרף

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

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

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

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

סדרת הדרגות

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

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

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

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: היפרגרף
תמונות ומדיה בוויקישיתוף: היפרגרף

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

הערות שוליים

1. P. Erdős, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lopak 11, 1960, עמ' 264-274
2. 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

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