היפרגרף (אנגלית: 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


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