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