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

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

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

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

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

גרף דה ברויין

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

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

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

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

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

הערות שוליים

1. de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758-764, 1946.
2. *de Bruijn, N. G. "Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2ⁿ zeros and ones that show each n-letter word exactly once", T.H.-Report 75-WSK-06, Technological University Eindhoven, 13 pages, 1975.
3. Good, I. J. (1946). "Normal recurring decimals". Journal of the London Mathematical Society. 21 (3): 167–169. doi:10.1112/jlms/s1-21.3.167.
4. לדוגמה Pavel A. Pevzner, Haixu Tang, Glenn Tesler: De novo repeat classification and fragment assembly. RECOMB 2004, 213-222

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