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

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

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

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

כלל ה-0-1 של גרפים – ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. … להמשיך לקרוא

כלל ה-0-1 של גרפים – הקדמה

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