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

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

עריכות