אלגוריתמים לעץ פורש מינימלי בגרף – מה הרעיון הכללי?

בפוסט הקודם תיארתי את הבעיה המתמטית שאנחנו רוצים לפתור: מציאת עץ פורש מינימלי של גרף ממושקל. בפוסט הזה ניגש ישר לעסק ונתאר איך עושים את זה. בפוסטים הבאים אני הולך לתאר שני אלגוריתמים שעושים את זה – של קרוסקל ושל … להמשיך לקרוא

על גרפים, עצים פורשים ואיך זה נראה בקוד

בפוסט הקודם הצגתי באופן מאוד לא פורמלי ולא מחוייב שני אלגוריתמים לייצור מבוכים – של קרוסקל ושל פרים. המבוכים היו רק תירוץ כדי להציג את האלגוריתמים הללו, שמיועדים לטפל בסיטואציות הרבה יותר כלליות – אלו אלגוריתמים למציאת עץ פורש מינימלי … להמשיך לקרוא

כיבוי אורות (או: תורת הגרפים והאלגברה הלינארית מחסלות עוד משחק תמים)

"כיבוי אורות", או Lights Out הוא משחק תמים שהולך כך: נתון לוח משבצות של $latex 5\times5$, כך שכל משבצת יכולה להיות מוארת או כבויה; נניח מכאן ואילך עד לסוף הפוסט (כמעט) שבתחילת המשחק כל המשבצות כבויות. כל לחיצה על משבצת … להמשיך לקרוא

כפל מטריצות – מה, לעזאזל?

בפוסט הקודם הצגתי מטריצות בתור כלי שעוזר לי לפתור מערכת משוואות – במקום לכתוב כל פעם את כל מערכת המשוואות, אני כותב מטריצה ו"מדרג" אותה והתהליך חוסך לי כתיבה מיותרת וקצת יותר קל לקריאה. זו מן הסתם לא הסיבה למה … להמשיך לקרוא

משפט המטריצה-עץ של קירכהוף

אני רוצה לדבר הפעם על מה שלטעמי הוא משפט יפהפה ביותר, גם בשל מה שהוא אומר וגם בשל ההוכחה שלו, שלטעמי מייצגת את כל מה שטוב במתמטיקה – גם דורשת הבנה טכנית לא טריוויאלית, וגם מכילה תובנה עמוקה שמאפשרת לראות … להמשיך לקרוא

משפט טורן והולדת תורת הגרפים האקסטרמלית

לא מזמן כתבתי פוסט על משפט רמזי שעסק בשאלה כמה גדולה צריכה להיות קבוצת ילדים על מנת שתיווצר בה קבוצה מגודל מסויים שכולם בה חברים או כולם בה לא חברים. זה היה מקרה פרטי של השאלה שבה עוסקים בתורת רמזי … להמשיך לקרוא

בעיית וויל האנטינג

נקודת המוצא העלילתית של הסרט "סיפורו של וויל האנטינג" (וכאן אני עומד לגלות טיפה מפרטי העלילה – אבל לא משהו שלא מתגלה ממילא בעשר הדקות הראשונות של הסרט, ואיננו מהותי כל כך) היא חידה מתמטית שפרופסור ב-MIT נותן לסטודנטים בקורס … להמשיך לקרוא

מים, חשמל וגז, והקשר שלהם לגרפים מישוריים

די מפתיעה אותי כמות הנשמות התועות שמגיעות לבלוג הזה בחיפושים נואשים אחרי פתרון לחידת ה"מים, חשמל, גז". גיגול קצר הראה כי החידה המטופשת הזו אכן פופולרית למדי – אפילו יש משחקי פלאש עבורה. הנה תיאור קצר למי שאינו מכיר: ישנם … להמשיך לקרוא

“הוא חיפש על העץ…”

יש שתי גישות אפשריות לעיסוק בגרפים; האחת היא לחשוב על הגרף כעל יצור מתמטי אבסטרקטי ולנסות לחקור אותו – מה התכונות שלו, ואיזה אלגוריתמים בודקים אותן בצורה יעילה. משפט אוילר שעליו דיברתי בפוסט שעבר הוא דוגמה לאופן פעולה זה. הרעיון … להמשיך לקרוא

איך אוילר עוזר לנו לבנות בתים ולטייל על גשרים

שעשוע ידוע שנהוג לתת לילדים הוא זה: האתגר כאן פשוט – האם ניתן לצייר את ה"בית" מבלי להרים את העפרון מהדף, כלומר בקו אחד. התשובה חיובית – נסו למצוא איך. אחרי שהילדים פותרים את החידה הזו, נותנים להם חדשה דומה … להמשיך לקרוא