סדרת דה ברויין

סדרת דה ברויין $\displaystyle B(k,n)$ היא סדרה מעגלית מעל אלפבית $\displaystyle A$ בגודל $\displaystyle k$ שמכילה כל רצף באורך $\displaystyle n$ מעל $\displaystyle A$ בדיוק פעם אחת. אורך סדרה כזאת הוא בדיוק $\displaystyle k^{n}$. הסדרות קרויות על שמו של המתמטיקאי ההולנדי ניקולאס חוברט דה ברויין שכתב עליהן מאמר ב-1946. מאוחר יותר הסתבר שסדרות אלה היו ידועות קודם לכן. באותה תקופה גם המתמטיקאי היהודי-אנגלי אירווינג ג'ון גוד (I. J. Good) גילה את הסדרות ובנייתן.

סדרות כאלה שימושיות למשל כדי לאתר מקום בסדרה לצורכי סנכרון - לאחר קריאת תת-סדרה כלשלהי באורך $\displaystyle n$ ניתן לדעת את מיקומה המדויק.

בניית סדרות דה ברויין ממסלולים בגרפים

ניתן להגדיר סדרת דה ברויין בינארית באמצעות גרף המכונה גרף דה ברויין. גרף דה ברויין מסדר $\ n$ מעל אלפבית בגודל $\ k$ הוא גרף מכוון עם $\displaystyle k^{n}$ קודקודים, שכל קודקוד מייצג מחרוזת מעל $\displaystyle A$ באורך $\displaystyle n$, כלומר $V=\{(v_{1},v_{2},\ldots ,v_{n}):v_{i}\in A\}.$. קבוצת הקשתות מוגדרת על ידי $E=\{((v_{1},v_{2},\dots ,v_{n}),(w_{1},w_{2},\dots ,w_{n})):v_{2}=w_{1},v_{3}=w_{2},\dots ,v_{n}=w_{n-1}\}.$, דהיינו כל קודקוד $\displaystyle v$ מחובר לקודקודים שמתקבלים על ידי הזזה במקום אחד של המחרוזת שלו תוך השמטת האות הראשונה ותוספת של אות כלשהי בקוארדינטה האחרונה.

גרף דה ברויין

נסמן באופן טבעי את הקשתות באות החדשה שנוספה. ניתן לראות כי דרגת היציאה ודרגת הכניסה שתיהן $\displaystyle k$ וכי הגרף קשיר היטב (כדי להגיע מ $(v_{1},v_{2},\dots ,v_{n})$ אל $(w_{1},w_{2},\dots ,w_{n})$ יש לעקוב אחרי המסלול שקשתותיו מסומנות ב $w_{1},w_{2},\dots ,w_{n}$) ולכן יש בגרף מעגל אוילרי. המעגל האוילרי מגדיר סדרה על פי סימוני הקשתות שלאורכו. נוסף, ניתן לראות כי המעגל האוילרי בגרף מסדר $\ n-1$ מגדיר באופן טבעי מעגל המילטון בגרף מסדר $\ n$ ושניהם מגדירים את אותה סדרה. כדי לודא כי הסדרה המוגדרת היא אכן סדרת דה ברויין, נראה כי הרצף $(b_{1},b_{2},\ldots ,b_{n})$ מופיע בסדרה בדיוק ב-$\ n$ המקומות שמובילים אל הצומת $(b_{1},b_{2},\ldots ,b_{n})$ במעגל ההמילטוני בגרף דה ברויין מסדר $\ n$.

לגרף דה ברויין יש חשיבות גם כטופולוגיית רשת המאפשרת ניתוב מהיר ויעיל. הוא אף קשור לשיטות ריצוף של DNA.‏

קישורים חיצוניים

מדיה וקבצים בנושא סדרת דה ברויין בוויקישיתוף

• סדרת דה ברויין, באתר MathWorld (באנגלית)

הערות שוליים

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