עץ פורש – הבדלי גרסאות

ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] נתון G הוא [[עץ (תורת הגרפים)|עץ]] שהוא [[תת גרף]] של G (קשתותיו הן קשתות של G), ומכיל את כל צמתי G. ניתן לחשוב אינטואיטיבית על עץ פורש כעל מה שמתקבל מגרף לאחר שהורדנו את כל הקשתות שאפשר להוריד מבלי לפגום בקשירות של הגרף. מקרה פרטי חשוב של עץ פורש הוא זה של [[עץ פורש מינימלי]], שהוא עץ פורש של גרף שקשתותיו ממושקלות, כך שסכום המשקולות על הקשתות הוא הקטן ביותר האפשרי. זו בעיה שקל לראות את ההשלכות המעשיות שלה: למשל, כאשר רוצים לסלול רשת כבישים בין ערים כך שיהיה מסלול בין כל שתי ערים, ולעשות זאת במחיר מינימלי, מחפשים את העץ הפורש המינימלי של הגרף שצמתיו הם הערים וקשתותיו הכבישים הפוטנציאליים ביניהן. ניתן לתת דוגמה דומה גם עבור רשתות תקשורת.

 

 

{{קצרמר מתמטיקה}}