גרף (תורת הגרפים)

גרף לא מכוון בעל 6 קודקודים ו-7 קשתות

גרף מכוון בעל 4 קודקודים ו-5 קשתות

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

האובייקטים הניתנים לקישור מכונים קודקודים או צמתים (באנגלית: vertex), וקבוצת הקודקודים מסומנת באות $V$.

הקישורים בין הקודקודים מכונים צלעות או קשתות (באנגלית: edge), וקבוצת הצלעות מסומנת באות $E$. מתקיים כי קבוצת הצלעות מקיימת: $E\subseteq V\times V$, כלומר: כל צלע היא זוג הקודקודים, אותם היא מקשרת (ללא חשיבות לסדר, נהוג לייצג באמצעות קבוצה).

גרף, אשר קבוצת הקודקודים שלו היא $V$ וקבוצת הצלעות שלו היא $E$ מסומן באופן הבא: $G=(V,E)$.

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

סוגי גרפים

• גרף בלתי מכוון ולעיתים בפשטות גרף הוא קבוצה של צמתים וקבוצה של קשתות. כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון $G$ מוגדר על ידי $(V,E)$ כאשר $V$ היא קבוצת הצמתים ו-$E\subseteq \{\{u,v\}\mid u,v\in V\}$ היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים מקרה פרטי של גרפים מכוונים (בהם עבור כל זוג צמתים $u$ ו-$v$, הקשתות מ-$u$ ל-$v$ ומ-$v$ ל-$u$ קיימות שתיהן, או חסרות שתיהן).
• גרף מכוון הוא קבוצה של צמתים (גם: קודקודים או נקודות) וקבוצה של קשתות מכוונות. כאשר ישנה משמעות לכיוונה של קשת מכוונת - היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון $D$ מוגדר על ידי $(V,E)$ כאשר $V$ היא קבוצת הצמתים ו-$E\subseteq V\times V$ היא קבוצת הקשתות. קשת $e=(u,v)\in E$ יוצאת מ-$u$ ונכנסת ל-$v$.
  • גרף תשתית של גרף מכוון הוא גרף בלתי מכוון, אשר מכיל אותה קבוצת צמתים כמו הגרף המכוון, ומכיל את הקשתות בין זוגות הצמתים אשר היו ביניהם קשתות בגרף המקורי (פורמלית, אם $D=(V,E)$‎ הוא גרף מכוון אז $D'=(V,\{\{u,v\}|(u,v)\in E\})$ הוא גרף התשתית של $D$).
• גרף מעורב הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.
• לולאה (גם: חוג עצמי) היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו.
• גרף פשוט גרף לא מכוון ללא לולאות וללא קשתות מקבילות.
• גרף סופי גרף שקבוצת הצמתים שלו סופית.
• גרף אינסופי גרף שקבוצת הצמתים שלו היא אינסופית.
• גרף ממושקל הוא גרף שבו לכל קשת יש ערך, לרוב מספרי, המכונה משקל. באופן פורמלי, גרף ממושקל בלתי מכוון הוא שלשה $(V,E,w)$, כאשר $V$ ו-$E$ מוגדרים כמקודם, ו-$w$ היא פונקציית המשקל מ-$E$ לקבוצה כלשהי (למשל $\mathbb {R}$).
• גרף בלתי מתויג הוא גרף שבו לא ניתן להבחין בין הצמתים. כלומר, אין אף מזהה ייחודי (כגון שם או מספר) לצומת בגרף.

תת גרף

תת גרף $G'=\left(V',E'\right)$ של גרף $G=\left(V,E\right)$ הוא גרף המורכב משתי תתי קבוצות של צומתי וקשתות G, דהיינו: $V'\subseteq V$ וכן $E'\subseteq E$ כך שהקשתות $E'$ נפרשות על ידי $V'$.

או במילים אחרות: אם $G=\left(V,E\right)$ ו-$H=\left(W,F\right)$ הם שני גרפים, אזי $H$ הוא תת-גרף של $G$ אם: $W\subseteq V$ וגם $F\subseteq E$.

תת גרף $H$ של גרף $G$ הוא תת גרף מושרה אם לכל זוג של צמתים $x$ ו-$y$ ב-$H$, ‏$xy$ היא קשת של $H$ אם ורק אם היא קשת של $G$. במילים אחרות, $H$ הוא תת-גרף מושרה של $G$ אם הוא מכיל את כל הקשתות של $G$ המתאימות לצמתים של $H$ ולא מכיל אף קשת נוספת.

ראו גם

• גרף מעגל
• מבנה נתונים

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

• גרף, באתר MathWorld (באנגלית)

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

גרף (תורת הגרפים)34907085Q141488