גרף קשיר – הבדלי גרסאות

[[גרף מכוון]] נקרא '''קשיר היטב (או קשיר בחוזקה)''' אם קיים מסלול מכל צומת שבו אל כל צומת אחר. עבור גרף מכוון כללי, ניתן תמיד לפרק את הגרף ל'''רכיבים קשירים היטב''' - תתתתי-גרפים מקסימליים של הגרף המקורי (גם: רק"ח - רכיבי קשירות חזקה), שכל אחד מהם הוא גרף קשיר היטב בפני עצמו. פירוק זה מהווה חלוקה של הגרף למחלקות זרות - שני רכיבים שונים לא יכולים להכיל צומת משותף.

'''גרף יתרמכוון עלחסר כן,מעגלים''' הגרף(גמ"ל שכל- צומתDAG): גרף בו מייצגכל אחדצומת מהרכיבים(וקשתותיו הקשיריםהיוצאות) היטבמהווה רק"ח יחיד, ויש קשת מכוונת בין שני צמתים אם ורק אם יש קשת בין הרכיבים בגרף המקורי, הוא גרף מכוון חסר מעגלים (DAG).