-
האלגוריתם של קרוסקל
כל מה שרצית לדעת על האלגוריתם של קרוסקל:האלגוריתם של קרוסקל הוא אלגוריתם חמדן לפתרון בעיית מציאת עץ פורש מינימלי בגרף ממושקל לא מכוון, שתואר לראשונה במאמר של ג'וזף קרוסקל בשנת 1956. המטרה היא למצוא תת קבוצה של הקשתות שתיצור עץ המכיל את כל הקודקודים המקוריים, כאשר סכום משקלי הקשתות בתת-קבוצה זו הינו מינימלי. לפי אלגוריתם…
-
אלגוריתם פלויד-וורשאל
כל מה שרצית לדעת על אלגוריתם פלויד-וורשאל:אלגוריתם פלויד-וורשאל הוא אלגוריתם במדעי המחשב המשמש למציאת המסלולים הקצרים ביותר בין כל שני זוגות צמתים, בגרף ממושקל ומכוון. האלגוריתם מבוסס על פרדיגמת התכנון הדינמי. האלגוריתם פועל גם על גרפים שמכילים קשתות עם משקלים שליליים, בניגוד לאלגוריתם דייקסטרה, אבל לא על גרפים עם מעגל שלילי. סיבוכיות זמן הריצה של…
-
אלגוריתם בלמן-פורד
כל מה שרצית לדעת על אלגוריתם בלמן-פורד:אלגוריתם בלמן-פורד הוא אלגוריתם הפועל על גרף מכוון וממושקל, ומשמש למציאת המסלול הקל ביותר מצומת אחד מסוים אל כל אחד משאר הצמתים בגרף. בכך, אלגוריתם זה משיג אותה תוצאה כמו אלגוריתם דייקסטרה, אך בניגוד לאלגוריתם דייקסטרה הוא עובד גם כאשר הגרף מכיל קשתות בעלות משקל שלילי. יתר על כן,…
-
אלגוריתם חיפוש לרוחב
כל מה שרצית לדעת על אלגוריתם חיפוש לרוחב:אלגוריתם חיפוש לרוחב (אנגלית: Breadth-first search, ראשי תיבות: BFS) הוא אלגוריתם המשמש למעבר על צמתי גרף, לרוב תוך חיפוש צומת המקיים תכונה מסוימת. צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי , והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ, ואז על כל הצמתים במרחק 2 צלעות מ…
-
מסלול
כל מה שרצית לדעת על מסלול:האם התכוונתם ל… מסלול (מושב) – מושב בצפון הנגב מסלול (פיזיקה) – העקומה המתארת את תנועתו של גוף במרחב טיסה מסלולית – שיגור רכב חלל למסלול סביב כדור הארץ: מסלול לווייני נמוך מסלול לווייני בינוני מסלול גיאוסטציונרי מסלול קוטבי מסלול (תורת הגרפים) – מונח בתורת הגרפים מסלול (תורת החבורות) –…
-
משפט פרון-פרובניוס
כל מה שרצית לדעת על משפט פרון-פרובניוס:משפט פרון-פרובניוס הוא משפט באלגברה לינארית, המתאר את הערכים העצמיים של מטריצה ריבועית בעלת ערכים ממשיים חיוביים. לפי המשפט, למטריצה כזו יש וקטור עצמי יחיד שכל רכיביו חיוביים, והוא שייך לערך העצמי המקסימלי. למשפט יש יישומים בהסתברות (בפרט בתהליכי מרקוב), מערכות דינמיות, תורת הגרפים, כלכלה, דמוגרפיה ועוד. את המשפט…
-
תכונת ליוביל
כל מה שרצית לדעת על תכונת ליוביל:תכונת ליוביל היא תכונה של גרפים שקיומה מצביע על כך שפיזור המסה בגרף מחקה את משפט ליוביל על המישור המרוכב. כל הגרפים הסופיים מקיימים את תכונת ליוביל, באופן טריוויאלי. גם גרף הסריג מקיים את תכונת ליוביל. התכונה אינה נשמרת תחת קוואזי-איזומטריות. נלקח מויקיפדיה הגדרות נוספות הקשורות לתכונת ליוביל:•תורת הגרפים•אנליזה…
-
שיטת חיפוש היוריסטית
כל מה שרצית לדעת על שיטת חיפוש היוריסטית:שיטת חיפוש היוריסטית היא שיטת חיפוש המתבטאת בהערכה וניחוש המצמצמים את אזור החיפוש של פתרון מסוים לבעיה, ולכן מקצרים את זמן החיפוש מחד גיסא, אך אינם מבטיחים הצלחה מאידך גיסא. בשיטות היוריסטיות מעבר ממצב אחד למצב הבא נקבע על סמך שיקולים היוריסטיים, המציינים את מידת הכדאיות לעבור למצב…
-
רשתות עולם קטן
כל מה שרצית לדעת על רשתות עולם קטן:רשת עולם קטן היא סוג של גרף מתמטי מענף המתמטיקה של תורת הגרפים ומוגדרת כמקרה פרטי של רשת מורכבת. בו מרבית הצמתים אינן שכנות אך ניתן להגיע אליהן מכל אחת מהצמתים האחרות על ידי מספר מעברים קטן. בהגדרה מתמטית רשת עולם קטן מוגדרת כרשת בה המרחק (L) בין…
-
עץ פורש מינימלי
כל מה שרצית לדעת על עץ פורש מינימלי:עץ פורש בשביל גרף זה, הוא קבוצה חלקית הכוללת רק את המסלולים שאינם סגורים במעגל, ועדיין כל בית יהיה מחובר. ייתכנו מספר עצים פורשים לגרף אחד. עץ פורש מזערי הוא עץ פורש, בעל המשקל הכולל הנמוך ביותר. אם יש קשתות שמשקלן שווה, הרי שיכולים להיות מספר עצים פורשים…