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

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

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

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

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

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

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

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

סוגי גרפים

• גרף מכוון (directed graph, digraph) הוא קבוצה של צמתים (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של קשתות מכוונות (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת - היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון $\ D$ מוגדר על ידי $\ (V,E)$ כאשר $\ V$ היא קבוצת הצמתים ו-$\ E\subseteq V\times V$ היא קבוצת הקשתות. קשת $\ e=(u,v)\in E$ יוצאת מ-$\ u$ ונכנסת ל-$\ v$.
• גרף בלתי מכוון (undirected graph), ולעיתים בפשטות גרף הוא קבוצה של צמתים וקבוצה של קשתות (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון $\ G$ מוגדר על ידי $\ (V,E)$ כאשר $\ V$ היא קבוצת הצמתים ו-$\ E\subseteq \{uv\mid u,v\in V\}$ היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים מקרה פרטי של גרפים מכוונים (בהם עבור כל זוג צמתים u ו-v, הקשתות מ-u ל-v ומ-v ל-u קיימות שתיהן, או חסרות שתיהן).
• גרף מעורב (mixed graph) הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.
• לולאה (מכונה גם חוג עצמי) היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו. גרף לא מכוון ללא לולאות וללא קשתות מקבילות נקרא גרף פשוט.
• גרף סופי (finite graph) הוא גרף שקבוצת הצמתים שלו סופית. גרף אינסופי (infinite graph) הוא גרף שקבוצת הצמתים שלו היא אינסופית.
• גרף משוקלל (weighted graph) הוא גרף (מכוון או בלתי מכוון) שבו לכל קשת יש משקל, כלומר מספר או ערך שמייצג עלות, אורך או כל מדד אחר. באופן פורמלי, גרף משוקלל (בלתי) מכוון הוא שלשה $\ (V,E,w)$, כאשר $\ V$ ו-$\ E$ מוגדרים כמקודם, ו-$\ w$ היא פונקציית המשקל מ-$\ E$ ל-$\ \mathbb {N}$, ל-$\ \mathbb {R}$, או לקבוצת משקולות אחרת.
• גרף בלתי מתויג (unlabeled graph) הוא גרף שבו לא ניתן להבחין בין הצמתים. כלומר, אין אף מזהה ייחודי (כגון שם או מספר) לצומת בגרף.

תת־גרף

תת־גרף $G'=(V',E')$ של גרף $G=(V,E)$ הוא גרף המורכב מתת קבוצה של צומתי וקשתות 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$ ולא מכיל אף קשת נוספת.

ראו גם

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