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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

סדרות כאלה שימושיות למשל כדי לאתר מקום בסדרה לצורכי סנכרון - לאחר קריאת תת-סדרה כלשלהי באורך \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.‏‏[4]

הערות שוליים[עריכת קוד מקור | עריכה]

  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 2n zeros and ones that show each n-letter word exactly once", T.H.-Report 75-WSK-06, Technological University Eindhoven, 13 pages, 1975.
  3. ^ I. J. Good (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
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.