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

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

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

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

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

אלגוריתם Warshall

ראו גם

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