היפרגרף

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

בתורת הגרפים, היפרגרף (hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים. בעוד שבגרף פשוט קשת בין קודקוד u וקודקוד v מסומנת על ידי הזוג (u,v), בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל (u_1, u_2, u_3, \ldots).

באופן פורמלי, היפרגרף בלתי מכוון \ G=(V,E) מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת \ e \in E היא קבוצה של שני צמתים או יותר מ-\ V, ומתקיים כי: E \sube \mathcal{P}(V), כלומר: הקבוצה \ E הינה תת-קבוצה של קבוצת החזקה של הקבוצה \ V.

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


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