תורת הגרפים — הסבר
גרף הוא מבנה המורכב מצמתים (קודקודים) ומקשתות המחברות ביניהם, ומשמש למידול קשרים — רשתות, מפות וקשרי תלות. גרף יכול להיות מכוון או לא מכוון, והוא מיוצג בדרך כלל בעזרת מטריצת סמיכויות או רשימת סמיכויות.
תורת הגרפים בבגרות
תורת הגרפים בבגרות במדעי המחשב מופיעה בחלק התיאורטי של שאלון 381, לצד המודלים החישוביים, כשאלת בחירה. השאלות בודקות ניתוח גרפים: דרגות צמתים, קשירות ורכיבי קשירות, מציאת מסלולים, סריקה לרוחב (BFS) ולעומק (DFS), ועצים פורשים — לרוב כשאלות ניתוח טענות והוכחה יותר מאשר כתיבת קוד ארוך.
איך מתכוננים לתורת הגרפים?
כדי להתכונן, כדאי לתרגל מעבר בין ייצוגי גרף, זיהוי רכיבי קשירות, מעקב אחר סריקות DFS ו-BFS ובניית עצים פורשים. פתרון שאלות בגרות בתורת הגרפים עם הסבר ופתרונות מלאים בונה את האינטואיציה לניתוח גרפים.
- ייצוג גרפים: מטריצת סמיכויות מול רשימת סמיכויות
- גרף מכוון ולא מכוון, דרגות צמתים וקשירות (רכיבי קשירות)
- סריקות גרף: לרוחב (BFS) ולעומק (DFS)
- מסלולים בגרף ועצים פורשים