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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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