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

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

האובייקטים האלה נקראים קודקודים או צמתים. קודקוד הוא נקודה שמייצגת אובייקט, והקבוצה שלהם מסומנת באות V.

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

גרף מסומן לעיתים כ־G=(V,E).

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

תת־גרף הוא גרף שנוצר על ידי בחירה של תת־קבוצה של הקודקודים ותת־קבוצה של הקשתות מתוך גרף קיים. כלומר, תת־גרף משתמש רק בחלק מהקודקודים והקשתות של הגרף המקורי.

תת־גרף נקרא תת־גרף מושרה אם הוא כולל בדיוק את כל הקשתות שבגרף המקורי שמחברות בין הקודקודים שנבחרו, ולא מוסיף קשתות חדשות.

גרף הוא ציור של נקודות וקווים שמחברים אותן.

הנקודות נקראות קודקודים או צמתים. הקווים נקראים צלעות או קשתות. צלע מחברת שתי נקודות.

גרף בנוי משתי רשימות: רשימת נקודות ורשימת קווים.

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

תת־גרף הוא גרף קטן שעשוי מחלק מהנקודות ומהקווים של גרף גדול.

תת־גרף מושרה שומר את כל הקווים שבין הנקודות שנבחרו. הוא לא מוסיף קווים שלא היו בגרף הגדול.