היפרגרף

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

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

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

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

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


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