היפרגרף

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

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

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

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

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

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

קישורים חיצוניים




הערות שוליים

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