הבדלים בין גרסאות בדף "עץ פורש"

נוספו 8 בתים ,  לפני 8 שנים
מ
בוט החלפות
מ (בוט מסיר: ka:დამფარავი ხე (deleted))
מ (בוט החלפות)
[[Imageקובץ:4x4 grid spanning tree.svg|thumbממוזער|עץ פורש (הקשתות הכחולות) של גרף הגריד]]
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] [[גרף קשיר|קשיר]] G הוא [[תת גרף]] קשיר של G, המכיל את כל צומתי G, ואין לו מעגלים. תת-גרף כזה הוא [[עץ (תורת הגרפים)|עץ]].
 
אפשר לקבל עץ פורש על ידי הסרת קשתות מן הגרף, בזו אחר זו, כל עוד הקשירות לא נפגעת. אם הגרף כולל מעגל (כלומר, סדרה של קודקודים <math>\ v_0,v_1,\dots,v_n</math> שבה כל זוג קודקודים סמוכים, וכן הזוג <math>\ v_0,v_n</math>, מחוברים בקשת), נוכל להסיר את אחת מקשתות המעגל בלי לפגוע בקשירות. על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש. מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות (<math> \displaystyle n-1 </math>). דרכים יעילות יותר למציאת עץ פורש הם באמצעות [[אלגוריתם חיפוש לעומק]] או [[אלגוריתם חיפוש לרוחב]]. אלגוריתמים אלו ירוצו ב[[סיבוכיות|זמן]] ליניארילינארי במספר הקשתות בגרף.
 
==ספירת מספר העצים הפורשים==