עם זאת, ישנם סוגים רבים של גרפים שונים בהתאם למספר הקודקודים, מספר הקצוות, הקישוריות ההדדית והמבנה הכללי שלהם, חלק מסוגי הגרפים הנפוצים הם כדלקמן:
1. גרף אפס
א גרף null הוא גרף שאין בו קצוות בין הקודקודים שלו. גרף ריק נקרא גם גרף ריק.
דוגמא
גרף ריק עם n קודקודים מסומן ב-Nn.
2. גרף טריוויאלי
א גרף טריוויאלי הוא הגרף שיש לו רק קודקוד אחד.
דוגמא
בגרף לעיל, יש רק קודקוד 'v' אחד ללא שום קצה. לכן, זה גרף טריוויאלי.
3. גרף פשוט
א גרף פשוט הוא הגרף הבלתי מכוון עם ללא קצוות מקבילים ו ללא לולאות .
גרף פשוט בעל n קודקודים, המדרגה של כל קודקוד היא לכל היותר n -1.דוגמא
בדוגמה שלמעלה, גרף ראשון אינו גרף פשוט כי יש לו שני קצוות בין הקודקודים A ו-B ויש לו גם לולאה.
הגרף השני הוא גרף פשוט מכיוון שהוא אינו מכיל לולאה וקצוות מקבילים.
4. גרף לא מכוון
א גרף לא מכוון הוא גרף שהקצוות שלו הם לא מכוון .
דוגמא
בגרף הנ'ל מכיוון שאין קצוות מכוונים, לכן זה גרף לא מכוון.
5. גרף מכוון
א גרף מכוון הוא גרף שבו ה הקצוות מכוונים לפי חיצים.
גרף מכוון ידוע גם בשם דיגרפים .
דוגמא
בגרף לעיל, כל קצה מכוון על ידי החץ. לקצה מכוון יש חץ מ-A ל-B, כלומר A קשור ל-B, אבל B לא קשור ל-A.
6. השלם גרף
נקרא גרף שבו כל זוג קודקודים מצטרף בקצה אחד בדיוק גרף שלם . הוא מכיל את כל הקצוות האפשריים.
גרף שלם עם n קודקודים מכיל בדיוק nC2 קצוות ומיוצג על ידי Kn.
דוגמא
בדוגמה שלמעלה, מכיוון שכל קודקוד בגרף מחובר עם כל הקודקודים הנותרים דרך קצה אחד בדיוק, לכן, שני הגרפים הם גרפים שלמים.
7. גרף מחובר
א גרף מחובר הוא גרף שבו אנו יכולים לבקר מכל קודקוד אחד לכל קודקוד אחר. בגרף מחובר, קיים לפחות קצה או נתיב אחד בין כל זוג קודקודים.
דוגמא
בדוגמה לעיל, אנו יכולים לעבור מכל קודקוד אחד לכל קודקוד אחר. זה אומר שקיים לפחות נתיב אחד בין כל זוג קודקודים ולכן, זה גרף מחובר.
8. גרף מנותק
א גרף מנותק הוא גרף שבו כל נתיב אינו קיים בין כל זוג קודקודים.
דוגמא
הגרף לעיל מורכב משני רכיבים עצמאיים אשר מנותקים. מכיוון שלא ניתן לבקר מקודקודים של רכיב אחד לקודקודים של רכיבים אחרים לכן, מדובר בגרף מנותק.
9. גרף רגיל
א גרף רגיל הוא גרף שבו דרגת כל הקודקודים זהה.
אם המדרגה של כל הקודקודים היא k, אז זה נקרא גרף k-רגיל.
דוגמא
בדוגמה לעיל, לכל הקודקודים יש תואר 2. לכן הם נקראים 2- גרף רגיל .
10. גרף מחזורי
גרף עם 'n' קודקודים (כאשר, n>=3) וקצוות 'n' היוצרים מחזור של 'n' עם כל הקצוות שלו, ידוע בתור גרף מחזור .
גרף המכיל לפחות מחזור אחד מכונה a גרף מחזורי .
בגרף המחזור, דרגת כל קודקוד היא 2.
גרף המחזור שיש לו n קודקודים מסומן ב-Cn.
מחרוזת מרובת שורות של javascript
דוגמה 1
בדוגמה לעיל, לכל הקודקודים יש תואר 2. לכן כולם גרפים מחזוריים.
דוגמה 2
מכיוון שהגרף הנ'ל מכיל בתוכו שני מחזורים ולכן הוא גרף מחזורי.
11. גרף אציקלי
גרף שאינו מכיל בתוכו מחזור כלשהו נקרא an גרף אציקלי .
דוגמא
מכיוון שהגרף שלעיל אינו מכיל בו שום מחזור ולכן הוא גרף א-ציקלי.
12. גרף דו-צדדי
א גרף דו-צדדי הוא גרף שבו ניתן לחלק את קבוצת הקודקודים לשתי קבוצות כך שהקצוות יעברו רק בין קבוצות, לא בתוכם.
גרף G (V, E) נקרא גרף דו-חלקי אם ניתן לפרק את מערך הקודקודים שלו V(G) לשתי תת-קבוצות לא ריקות מפורקות V1(G) ו-V2(G) באופן שכל קצה e ∈ E (G) יש את המפרק האחרון שלו ב-V1(G) ונקודה אחרונה אחרת ב-V2(G).
המחיצה V = V1 ∪ V2 ידועה כדו-מחיצה של G.
דוגמה 1
דוגמה 2
13. שלם גרף דו-צדדי
א גרף דו-צדדי מלא הוא גרף דו-צדדי שבו כל קודקוד בקבוצה הראשונה מחובר לכל קודקוד בקבוצה השנייה בקצה אחד בדיוק.
גרף דו-חלקי שלם הוא גרף דו-חלקי שלם.
Complete Bipartite graph = Bipartite graph + Complete graph
דוגמא
הגרף שלמעלה ידוע בשם K4,3.
14. גרף כוכבים
גרף כוכבים הוא גרף דו-צדדי שלם שבו לקודקודים n-1 יש תואר 1 ולקודקוד בודד יש תואר (n -1). זה בדיוק נראה כמו כוכב שבו (n - 1) קודקודים מחוברים לקודקוד מרכזי אחד.
גרף כוכבים עם n קודקודים מסומן ב-Sנ.
דוגמא
בדוגמה שלמעלה, מתוך n קודקודים, כל הקודקודים (n-1) מחוברים לקודקוד בודד. לפיכך, זהו גרף כוכבים.
15 גרף משוקלל
גרף משוקלל הוא גרף שהקצוות שלו סומנו עם כמה משקלים או מספרים.
אורכו של נתיב בגרף משוקלל הוא סכום המשקולות של כל הקצוות בנתיב.
דוגמא
בגרף שלמעלה, אם הנתיב הוא a -> b -> c -> d -> e -> g, אז אורך הנתיב הוא 5 + 4 + 5 + 6 + 5 = 25.
16. רב גרף
גרף שבו יש קצוות מרובים בין כל זוג קודקודים או שיש קצוות מקודקוד לעצמו (לולאה) נקרא גרף רב .
דוגמא
בגרף לעיל, ערכת קודקודים B ו-C מחוברים בשני קצוות. באופן דומה, קבוצות קודקוד E ו-F מחוברות עם 3 קצוות. לכן, זהו גרף רב.
17. גרף מישורי
א גרף מישורי הוא גרף שנוכל לצייר במישור כך שאין שני קצוות שלו חוצים זה את זה אלא בקודקוד שאליו הם נופלים.
דוגמא
ייתכן שהגרף שלמעלה לא נראה מישורי מכיוון שיש לו קצוות חוצים זה את זה. אבל אנחנו יכולים לצייר מחדש את הגרף לעיל.
שלושת רישומי המישור של הגרף לעיל הם:
שלושת הגרפים שלעיל אינם מורכבים משני קצוות שחוצים זה את זה ולכן, כל הגרפים לעיל הם מישוריים.
18. גרף לא מישורי
גרף שאינו גרף מישורי נקרא גרף לא מישורי. במילים אחרות, גרף שלא ניתן לצייר ללא לפחות על זוג הקצוות שלו מכונה גרף לא מישורי.
דוגמא
הגרף לעיל הוא גרף לא מישורי.