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

אין שינוי בגודל ,  לפני 15 שנים
מ
בוט - מחליף דוגמא בדוגמה
מ (robot Adding: lt)
מ (בוט - מחליף דוגמא בדוגמה)
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] נתון G הוא [[עץ (תורת הגרפים)|עץ]] שהוא [[תת גרף]] של G (קשתותיו הן קשתות של G), ומכיל את כל צמתי G. ניתן לחשוב אינטואיטיבית על עץ פורש כעל מה שמתקבל מגרף לאחר שהורדנו את כל הקשתות שאפשר להוריד מבלי לפגום בקשירות של הגרף. מקרה פרטי חשוב של עץ פורש הוא זה של [[עץ פורש מינימלי]], שהוא עץ פורש של גרף שקשתותיו ממושקלות, כך שסכום המשקולות על הקשתות הוא הקטן ביותר האפשרי. זו בעיה שקל לראות את ההשלכות המעשיות שלה: למשל, כאשר רוצים לסלול רשת כבישים בין ערים כך שיהיה מסלול בין כל שתי ערים, ולעשות זאת במחיר מינימלי, מחפשים את העץ הפורש המינימלי של הגרף שצמתיו הם הערים וקשתותיו הכבישים הפוטנציאליים ביניהן. ניתן לתת דוגמאדוגמה דומה גם עבור רשתות תקשורת.
 
בהינתן גרף פשוט בעל <math>\ n</math> צמתים ממוספרים שמכיל את כל הקשתות האפשריות,קיימים לו בדיוק <math>\ n^{n-2}</math> עצים פורשים. תוצאה זו נקראת [[נוסחת קיילי]]. שיטה כללית יותר, למציאת מספר העצים הפורשים של כל גרף נתונה ב[[משפט קירקהוף (תורת הגרפים)|משפט קירקהוף]].
68,018

עריכות