#algorithms #computer_science

סגור טרנזיטיבי של גרף מכוון

נגדיר את הסגור הטרנזיטיבי של גרף מכוון $G$ להיות גרף $G^{*} = (V, E^{*})$ כאשר:

E^{*} = {(u, v) | u \overset{G}{⇝} v}

כלומר בסגור טרנזיטיבית יש קשת בין שני קודקודים אמ״מ יש בינהם מסלול בגרף המקורי.

אחת השיטות לחישוב של $G^{*}$ היא לתת משקל של $1$ לכל קשת בגרף $G$ ולהריץ את פלויד וורשאל בסיום הריצה נבדוק את המטריצה $D^{(n)}$ ואם נקבל שם ערך $d_{i j}^{(n)} \leq n$ אז אנחנו יודעים שקיים מסלול בין $i, j$ .

נוכל לבנות אלגוריתם למציאת גרף כזה שמאוד דומה ל floyd ושרץ אותו זמן ריצה אבל חוסך בזכרון כי הוא מתבסס על פעולות לוגיות שמהירות יותר לחישוב בניגוד לפעולות אריתמטיות.

אם כן נחליף את פעולה ה $m i n$ ב $\lor$ ואת פעולת ה $+$ ב $\land$ .
נגדיר $t_{i j}^{(k)}$ להיות $1$ אם קיים מסלול ב $G$ מקודקוד $i$ ל $j$ כאשר קודקודי הביניים הם מהקבוצה $[k]$ ו $0$ אחרת.
לבסוף $t_{i j}^{(n)}$ יכיל את הפתרון שלנו, אם יש $1$ אז קיים מסלול ואחרת אין..

כלומר -

(i, j) \in E^{*} \leftrightarrow t_{i j}^{(n)} = 1

ההגדרה הריקורסיבית:

\begin{matrix} t_{i j}^{(0)} = {\begin{cases} 0 & i \neq j and (i, j) \neq E \\ 1 & i = j or (i, j) \in E \end{cases} \\ \forall_{1 \leq k \leq n} : t_{i j}^{(k)} = t_{i j}^{(k - 1)} \lor (t_{i k}^{(k - 1)} \land t_{k j}^{(k - 1)}) \end{matrix}

המשמעות היא שבראשון מחזירים אחד אם יש קשת ישירה ובשני אנחנו בודקים אם קיים מסלול מ $i, j$ שמשתמש רק בקבוצת קודקודי הביניים ללא $k$ או שקיימים שתי מסלולים בין $i$ ל $k$ ובין $k$ ל $j$ כיוון שאנחנו יודעים שבהכרח אחד מהשניים מתקיים או שאף אחד מהם לא מתקיים (ההסבר דומה למה שהראנו על המסלול המינימלי בהסבר על פלויד).

כמו בפלויד נחשב מטריצת $T^{(k)}$ בסדר עולה מ $1$ עד $n$ והאחרונה תכיל את הפתרון.

transitive_closure(G):
	n = |G.V|
	let T[0] = new matrix[n,n]
	for i = 1 to n
		if i == j or (i,j) in G.E
			t_ij[0] = 1
		else 
			t_ij[0] = 0
	for k = 1 to n 
		let T[K] = new matrix[n,n]
		for i = 1 to n
			for j = 1 to n
				t_ij[k] = t_ij[k-1] ∨ (t_ik[k-1] ∧ t_kj[k-1])
	return T[n]

זמן הריצה כפי שאמרנו הוא $O (| V |^{3})$
Pasted image 20230204191629.png|350

כמובן שניתן להשתמש באלגוריתם אחרים שאנחנו מכירים כמו גונסון או כל אלגוריתם APSP אחר כיוון שאם קיים מרחק קצר ביותר אז קיים מסלול יש יחס ישר בין הדברים. למעשה לא חייב כלל לשנות את האלגוריתם ולהתאים אותו במיוחד כפי שהתאמנו. נוכל פשוט להריץ כל אלגוריתם APSP ולבדוק פשוט עבור כל קודקוד את ערך המסלול הקצר ביותר שלו עם כל קודקוד אחר והיכן שהערך הוא לא $\infty$ להוסיף קשת לסגור טרנזיטיבי. כמובן שכדי לשנות את פונקציית המשקל ל $1$ לפני שעושים את זה אבל זה לא מחייב בפרט נוכל להריץ BFS מכל קודקוד ולקבל את אותה תוצאה. היתרון היחיד באלגוריתם הנ״ל הוא השימוש שלו בפעולות לוגיות ולא אריתמטיות.

הבחנה:

לבעיית הסגור טרנזיטיבי יש קשר ישיר עם בעיית כפל מטריצות מהיר . כלומר אם את האחת נוכל לפתור בזמן מהיר יותר אז גם את השנייה נוכל לייעל בהתאמה. באופן פורמלי יותר ננסח זאת כך
אם ניתן לחשב כפל מטריצות בוליאניות מגודל $n \times n$ בזמן $f (n) = Ω (n^{2})$ אזי ניתן לחשב סגור טרנזיטיבי של גרף מכוון $G = (V, E)$ בזמן $O (f (| V |))$ ובפרט אפשר להחליף את $f$ באלגוריתם כפל מטריצות מהיר שהוא $O (| V |^{ω})$