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