היפרגרף

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

היפרגרף (אנגלית: Hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים. בעוד שבגרף פשוט קשת בין קודקוד וקודקוד מסומנת על ידי הזוג , בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל .

באופן פורמלי, היפרגרף בלתי מכוון מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת היא קבוצה של שני צמתים או יותר מ-, ומתקיים כי: , כלומר: הקבוצה היא תת-קבוצה של קבוצת החזקה של הקבוצה .

היפרגרף מכוון מוגדר בדומה לגרף מכוון, כאשר כל קשת מורכבת משתי קבוצות כל אחת בעלת צומת אחד או יותר מ-, קבוצה של צמתים מהם הקשת יוצאת וקבוצה של צמתים אליהם הקשת נכנסת.

היפרגרף נקרא -היפרגרף אם כל קשת מכילה צמתים. בפרט, גרף הוא -היפרגרף.

סדרת הדרגות[עריכת קוד מקור | עריכה]

הדרגה של צומת בהיפרגרף היא מספר הקשתות בהיפרגרף המכילות את .

סדרת הדרגות של היפרגרף עם צמתים וסדר של הצמתים היא הסדרה . סדרה נקראת -גרפית אם היא סדרת הדרגות של איזשהו -היפרגרף. בעיית ההחלטה האם סדרה נתונה היא -גרפית פתירה בזמן פולינומי עבור ([1] Erdős and Gallai, 1960) אך NP-complete לכל ([2] 2018 ,.Deza et al).

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  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


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