היפרגרף (אנגלית: 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 (באנגלית)
• היפרגרפים, דף שער בספרייה הלאומית

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