טיוטה:סגור טרנזיטיבי

סגור טרנזיטיבי

תכונה של קבוצת קודקודים בגרף

סגור טרנזיטיבי של גרף מכוון $G=(V,E)$ הוא גרף מכוון $T=(V,E_{T})$ כך ש: $e=u\rightarrow v\in E_{T}$ אם ורק אם יש מסלול מכוון לא ריק מ-u ל-v ב-G.

אלגוריתמים לחישוב סגור טרנזיטיבי של גרפים

אלגוריתם Warshall

ראו גם

• אלגוריתם פלויד-וורשאל
• האלגוריתם של ג'ונסון

קטגוריה:אלגוריתמים בתורת הגרפים