הצגת המקור של הדף "היפרגרף"

'''היפרגרף''' ([[אנגלית]]: '''Hypergraph''') הוא הכללה של [[גרף (תורת הגרפים)|גרף]], שבה כל [[קשת (תורת הגרפים)|קשת]] היא תת-קבוצה לא ריקה של קודקודים. בעוד שבגרף פשוט קשת בין [[קודקוד]] <math>u</math> וקודקוד <math>v</math> מסומנת על ידי ה[[זוג סדור|זוג]] <math>(u,v)</math>, בהיפרגרף כל קשת היא [[n-יה סדורה|n-יה]] (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל <math>(u_1, u_2, u_3, \ldots)</math>.

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

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

היפרגרף נקרא '''<math>k</math>-היפרגרף''' אם כל קשת מכילה <math>k</math> צמתים. בפרט, [[גרף (תורת הגרפים)|גרף]] הוא <math>2</math>-היפרגרף.

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

'''סדרת הדרגות''' של היפרגרף עם <math>n</math> צמתים וסדר <math>v_1,...,v_n</math> של הצמתים היא הסדרה <math>d(G)=\left(d(v_1),...,d(v_n)\right)</math>. סדרה נקראת '''<math>k</math>-גרפית''' אם היא סדרת הדרגות של איזשהו <math>k</math>-היפרגרף. בעיית ההחלטה האם סדרה נתונה היא <math>k</math>-גרפית פתירה בזמן פולינומי עבור <math>k=2</math> (<ref>{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}</ref> [[פאול ארדש|Erdős]] and Gallai, 1960) אך NP-complete לכל <math>k\geq 3</math> (<ref>{{צ-מאמר|שם=Optimization over Degree Sequences|קישור=https://epubs.siam.org/doi/10.1137/17M1134482|כתב עת=SIAM Journal on Discrete Mathematics|שנת הוצאה=2018-01|עמ=2067–2079|כרך=32|doi=10.1137/17M1134482|מחבר=Antoine Deza, Asaf Levin, Syed M. Meesum, Shmuel Onn}}</ref> 2018 ,.Deza et al).

==קישורים חיצוניים==
{{מיזמים|ויקימילון=היפרגרף}}
* {{MathWorld}}
* {{דף שער בספרייה הלאומית|987007536189705171|היפרגרפים}}

==הערות שוליים==
{{הערות שוליים}}

{{תורת הגרפים}}

{{בקרת זהויות}}

{{קצרמר|מתמטיקה}}

[[קטגוריה:תורת הגרפים]]