היפרגרף
היפרגרף (אנגלית: Hypergraph) הוא הכללה של גרף, שבה כל קשת היא תת-קבוצה לא ריקה של קודקודים. בעוד שבגרף פשוט קשת בין קודקוד וקודקוד מסומנת על ידי הזוג , בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל .
באופן פורמלי, היפרגרף בלתי מכוון מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת היא קבוצה של צומת אחת או יותר מ-, ומתקיים כי: , כלומר: הקבוצה היא איבר של קבוצת החזקה של הקבוצה .
היפרגרף מכוון מוגדר בדומה לגרף מכוון, כאשר כל קשת מורכבת משתי קבוצות כל אחת בעלת צומת אחד או יותר מ-, קבוצה של צמתים מהם הקשת יוצאת וקבוצה של צמתים אליהם הקשת נכנסת.
היפרגרף נקרא -היפרגרף אם כל קשת מכילה צמתים. בפרט, גרף הוא -היפרגרף.
סדרת הדרגות
[עריכת קוד מקור | עריכה]הדרגה של צומת בהיפרגרף היא מספר הקשתות בהיפרגרף המכילות את .
סדרת הדרגות של היפרגרף עם צמתים וסדר של הצמתים היא הסדרה . סדרה נקראת -גרפית אם היא סדרת הדרגות של איזשהו -היפרגרף. בעיית ההחלטה האם סדרה נתונה היא -גרפית פתירה בזמן פולינומי עבור ([1] Erdős and Gallai, 1960) אך NP-complete לכל ([2] 2018 ,.Deza et al).
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- היפרגרף, באתר MathWorld (באנגלית)
היפרגרפים, דף שער בספרייה הלאומית
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ 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-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.