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

נוספו 1,267 בתים ,  לפני 15 שנים
שכתוב
(שכתוב)
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] [[קשירות (תורת הגרפים)|קשיר]] G הוא [[תת גרף]] [[קשירות (תורת הגרפים)|קשיר]] של G, המכיל את כל צמתי G, ואין לו מעגלים. תת-גרף כזה הוא [[עץ (תורת הגרפים)|עץ]].
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] נתון G הוא [[עץ (תורת הגרפים)|עץ]] שהוא [[תת גרף]] של G (קשתותיו הן קשתות של G), ומכיל את כל צמתי G. ניתן לחשוב אינטואיטיבית על עץ פורש כעל מה שמתקבל מגרף לאחר שהורדנו את כל הקשתות שאפשר להוריד מבלי לפגום בקשירות של הגרף. מקרה פרטי חשוב של עץ פורש הוא זה של [[עץ פורש מינימלי]], שהוא עץ פורש של גרף שקשתותיו ממושקלות, כך שסכום המשקולות על הקשתות הוא הקטן ביותר האפשרי. זו בעיה שקל לראות את ההשלכות המעשיות שלה: למשל, כאשר רוצים לסלול רשת כבישים בין ערים כך שיהיה מסלול בין כל שתי ערים, ולעשות זאת במחיר מינימלי, מחפשים את העץ הפורש המינימלי של הגרף שצמתיו הם הערים וקשתותיו הכבישים הפוטנציאליים ביניהן. ניתן לתת דוגמה דומה גם עבור רשתות תקשורת.
 
אפשר לקבל עץ פורש על-ידי הסרת קשתות מן הגרף, בזו אחר זו, בלי לפגוע בקשירות: אם הגרף כולל מעגל (כלומר, סדרה של קודקודים <math>\ v_0,v_1,\dots,v_n</math> שבה כל זוג קודקודים סמוכים, וכן הזוג <math>\ v_0,v_n</math>, מחוברים בקשת), אפשר להסיר את אחת הקשתות של המעגל. על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש. מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות.
בהינתן גרף פשוט בעל <math>\ n</math> צמתים ממוספרים שמכיל את כל הקשתות האפשריות,קיימים לו בדיוק <math>\ n^{n-2}</math> עצים פורשים. תוצאה זו נקראת [[נוסחת קיילי]]. שיטה כללית יותר, למציאת מספר העצים הפורשים של כל גרף נתונה ב[[משפט קירקהוף (תורת הגרפים)|משפט קירכהוף]].
 
את מספר העצים הפורשים של גרף אפשר לקבל מ[[משפט קירכהוף (תורת הגרפים)|משפט קירכהוף]]: אם A היא [[מטריצת שכנויות|מטריצת השכנויות]] של הגרף ו- D ה[[מטריצה אלכסונית|מטריצה האלכסונית]] שרכיבי האלכסון שלה הם ה[[דרגה (תורת הגרפים)|דרגות]] של הקודקודים, אז המטריצה <math>\ D-A</math> אינה [[מטריצה הפיכה|הפיכה]] (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת ה[[ערך עצמי|ערכים העצמיים]] השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש).
 
במקרה המיוחד של הגרף השלם על n קודקודים (הגרף שכל שני קודקודים שלו מחוברים בקשת אחת), מספר העצים הפורשים הוא <math>\ n^{n-2}</math>. לתוצאה זו, הקרויה [[נוסחת קיילי]], ידועות הוכחות רבות.
 
כאשר בגרף הנתון יש "משקל" לכל קשת (כלומר, זהו [[גרף ממושקל]]), טבעי לחפש עץ פורש שלו משקל כולל מינימלי. עץ כזה נקרא [[עץ פורש מינימלי]], ולבעיה של מציאת עץ כזה יש השלכות מעשיות רבות. לדוגמא, כאשר רוצים לסלול רשת כבישים בין ערים כך שיהיה מסלול בין כל שתי ערים, ולעשות זאת במחיר מינימלי, מחפשים את העץ הפורש המינימלי של הגרף שצמתיו הם הערים וקשתותיו הכבישים הפוטנציאליים ביניהן (המשקל בכל מקרה הוא אורך הכביש שיהיה צורך לסלול).
 
{{קצרמר מתמטיקה}}
[[קטגוריה: תורת הגרפים]]