מושגים בתורת הגרפים
גרף:
בגרף G=(V,E) , V קבוצת הקדקודים (vertices) או צמתים nodes)) , E קבוצת הקשתות (edges) .
בגרף מכוון הקשתות מכוונות ובגרף לא מכוון הקשתות לא מכוונות.
גרף התשתית (הלא מכוון) של גרף מכוון הוא הגרף המתקבל מהגרף המכוון, כאשר מתעלמים מכווני הקשתות.
לולאה:
לולאה היא קשת מקדקוד אל עצמו.
קשתות מקבילות:
לקשתות מקבילות אותן קצוות, ובגרפים מכוונים, שתי קשתות מקבילות שכוונן הפוך נקראות קשתות אנטי מקבילות.
מולטיגרף:
מולטיגרף יכול להכיל קשתות מקבילות.
גרף פשוט:
גרף פשוט לא מכיל לולאות או קשתות מקבילות.
קשת:
לכל קשת שני קדקודי קצה , בין שני קדקודים שכנים עוברת קשת, ולשתי קשתות סמוכות יש קדקוד קצה משותף. קשת סמוכה לכל קדקוד קצה שלה.
דרגת קדקוד:
דרגת קדקוד היא מספר הקשתות שהוא מהוה קצה שלהן, ובגרף מכוון דרגת הכניסה שווה למספר הקשתות המכוונות אל הקדקוד, ודרגת היציאה שווה למספר הקשתות המכוונות מהקדקוד. קדקוד מדרגה 0 נקרא מבודד.
מסלול פשוט:
במסלול פשוט/מעגל פשוט אין חזרה על קדקודים.
קליקה:
קליק הוא תת-גרף שבו כל שני קדקודים מחוברים בקשת.
בקבוצה בלתי תלויה (ב"ת) של קדקודים אין אף זוג קדקודים המחובר בקשת.
גרף דו-צדדי הוא גרף שניתן לחלק את קדקודיו לשתי קבוצות זרות, כך שלכל קשת בגרף יש קצה אחד בכל אחת מהקבוצות.
סימונים:
Pn הוא הגרף שצורתו מסלול על n קדקודים.
Cn הוא הגרף שצורתו מעגל על n קדקודים.
Kn הוא גרף שלם על n קדקודים, כלומר קיימת קשת בין כל שני קדקודים בגרף.
Km,n הוא גרף דו-צדדי שלם, כלומר יש לו m קדקודים בצד אחד, n קדקודים בצידו האחר וקשת בין כל שני קדקודים שאינם באותו צד.
נגישות:
u נגיש מ- v אם קיים מסלול (מכוון אם הגרף מכוון) מ- v אל u.
בגרף לא מכוון קשיר יש מסלול מכל קדקוד אל כל קדקוד אחר.
רכיב קשירות בגרף לא מכוון הוא תת-גרף קשיר מקסימלי, כלומר אין תת-גרף קשיר אחר שמכיל אותו.
גרף קשיר בחזקה הוא גרף מכוון שבו יש מסלול מכוון מכל קדקוד אל כל קדקוד אחר.
רכיב קשירות חזקה (רק"ח) הוא תת-גרף קשיר בחזקה, מקסימלי, כלומר אין תת-גרף קשיר חזק אחר שמכיל אותו.
מקור:
מקור בגרף מכוון הוא קדקוד שדרגת הכניסה שלו 0.
בור:
בור בגרף מכוון הוא קדקוד שדרגת היציאה שלו 0.
עץ:
עץ הוא גרף לא מכוון קשיר וחסר מעגלים.
יער:
יער הוא גרף לא מכוון וחסר מעגלים.
עלה:
עלה הוא קדקוד מדרגה 1 בעץ או ביער.