גרף (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←סוגי גרפים: הגהה לשם הבחנה ברורה |
הנדב הנכון (שיחה | תרומות) |
||
שורה 1:
[[תמונה:6n-graf.svg|שמאל|ממוזער|150px|גרף לא מכוון בעל 6 קודקודים ו-7 קשתות]]
[[תמונה:Directed graph.svg|ממוזער|שמאל|150px|גרף מכוון בעל 4 קודקודים ו-5 קשתות]]
ב[[תורת הגרפים]], '''גרף'''
האובייקטים הניתנים לקישור מכונים '''קודקודים''' או '''צמתים''' (באנגלית: vertex), וקבוצת הקודקודים מסומנת באות <math>\ V</math>.
הקישורים בין הקודקודים מכונים '''צלעות''' או '''קשתות''' (באנגלית: edge), וקבוצת הצלעות מסומנת באות <math>\ E</math>. מתקיים כי קבוצת הצלעות מקיימת: <math>E \sube V\times V</math>, כלומר: כל צלע
גרף, אשר קבוצת הקודקודים שלו היא <math>\ V</math> וקבוצת הצלעות שלו היא <math>\ E</math> מסומן באופן הבא: <math>\ G=(V,E)</math>.
שורה 25:
או במילים אחרות: אם <math>G=\left(V, E\right)</math> ו-<math>H=\left(W, F\right)</math> הם שני גרפים, אזי <math>H</math> הוא תת-גרף של <math>G</math> אם: <math>W\subseteq V</math> וגם <math>F\subseteq E</math>.
תת גרף H של גרף G הוא '''תת גרף מושרה''' אם לכל זוג של צמתים x ו-y ב-H, {{כ}}xy היא קשת של H [[אם ורק אם]] היא קשת של G. במילים אחרות, H הוא תת-גרף מושרה של G אם הוא מכיל את כל הקשתות של G המתאימות לצמתים של H ואף קשת נוספת.
== ראו גם ==
| |||