חישוב מספר המסלולים בגרף דה ברוין

שלום לכולם,
אני מנסה לפתור את השאלה הבאה:

בגרף דה ברוין עם 32 צמתים כמה מסלולים שונים באורך 30 מהצומת 00000 לצומת 11111 קיימים? מה התשובה כאשר בגרף יש 234 צמתים?

אני מכיר את התכונות המיוחדות של גרף דה ברוין אבל אני לא מצליח להבין איך לגשת אל השאלה.
תודה לכולם :smiley:

היי גלעד,
נתון כי הגרף מכיל 32 צמתים מעל האלפבית \sum=\{0,1\} ולכן נקבל:

V=\sum\,^{n-1} \Leftrightarrow32=2^{n-1} \Leftrightarrow n=6

כמו כן, נוכל להסיק כי \sigma=2. לכן גרף דה-ברויין עם 32 צמתים הוא הגרף G_{2,6}=(V,E). כדי להגיע מצומת 00000 לצומת 11111, נוכל לבצע כל מסלול שנרצה, העיקר שחמשת הצעדים האחרונים יכניסו 1 למספר. לכן, נרצה למצוא את מספר המסלולים השונים באורך 30-5=25. לכל צומת יש שתי אפשרויות לצומת הבאה ולכן 2^{25} אפשרויות. כאשר מגיעים לצומת 25, קיים רק מסלול אחד כדי להגיע ל-11111.

עתה, נתבונן על גרף המכיל 234 צמתים מעל האלפבית \sum=\{0,1,2\} כך שנקבל:

V=\sum\,^{n-1} \Leftrightarrow234=3^{n-1} \Leftrightarrow n=6

כמו כן, נוכל להסיק כי \sigma=3. לכן גרף דה-ברויין עם 234 צמתים הוא הגרף G_{3,6}=(V,E). כמו קודם, כדי להגיע מצומת 00000 לצומת 11111, נוכל לבצע כל מסלול שנרצה, העיקר שחמשת הצעדים האחרונים יכניסו 1 למספר. לכן, נרצה למצוא את מספר המסלולים השונים באורך 30-5=25. לכל צומת יש שלוש אפשרויות לצומת הבאה ולכן 3^{25} אפשרויות. כאשר מגיעים לצומת 25, קיים רק מסלול אחד כדי להגיע ל-11111.
מקווה שמובן :slight_smile:

לייק 1