הצגת המקור של הדף "סדרת דה ברויין"

'''סדרת דה ברויין''' <math>\displaystyle B(k,n)</math> היא סדרה מעגלית מעל [[אלפבית]] <math>\displaystyle A</math>  בגודל <math>\displaystyle k</math> שמכילה כל רצף באורך <math>\displaystyle n</math> מעל <math>\displaystyle A</math> בדיוק פעם אחת. אורך סדרה כזאת הוא בדיוק  <math>\displaystyle k^n</math>. הסדרות קרויות על שמו של המתמטיקאי ה[[הולנד]]י [[ניקולאס חוברט דה ברויין]] שכתב עליהן מאמר ב-1946{{הערה|de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758-764, 1946. }}. מאוחר יותר הסתבר שסדרות אלה היו ידועות קודם לכן{{הערה|*de Bruijn, N. G. [http://alexandria.tue.nl/repository/books/252901.pdf "Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2<sup>n</sup> zeros and ones that show each n-letter word exactly once"], T.H.-Report 75-WSK-06, Technological University Eindhoven, 13 pages, 1975. }}. באותה תקופה גם המתמטיקאי היהודי-אנגלי אירווינג ג'ון גוד (I. J. Good)  גילה את הסדרות ובנייתן{{הערה|1={{cite journal
  | author = Good, I. J.
  | authorlink = I. J. Good
  | title = Normal recurring decimals
  | journal = Journal of the London Mathematical Society
  | volume = 21
  | issue = 3
  | year = 1946
  | pages = 167–169
  | doi = 10.1112/jlms/s1-21.3.167}}}}.

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

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

ניתן להגדיר סדרת דה ברויין בינארית באמצעות גרף המכונה '''גרף דה ברויין'''. גרף דה ברויין מסדר <math>\ n</math> מעל אלפבית בגודל <math>\ k</math> הוא גרף מכוון עם <math>\displaystyle k^{n}</math>
קודקודים, שכל קודקוד מייצג מחרוזת מעל <math>\displaystyle A</math> באורך <math>\displaystyle n</math>, כלומר <math>V=\{(v_1,v_2,\ldots,v_{n}): v_i \in A\}.</math>. קבוצת הקשתות מוגדרת על ידי <math> 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}\}.</math>, דהיינו כל קודקוד  <math>\displaystyle v</math>   מחובר לקודקודים שמתקבלים על ידי הזזה במקום אחד של המחרוזת שלו תוך  השמטת האות הראשונה ותוספת של אות כלשהי בקוארדינטה האחרונה. 
[[קובץ:De bruijn graph-for binary sequence of order 4.svg|שמאל|ממוזער|250px|גרף דה ברויין]]
נסמן באופן טבעי את הקשתות באות החדשה שנוספה. ניתן לראות כי דרגת היציאה ודרגת הכניסה שתיהן <math>\displaystyle k</math> וכי הגרף [[גרף קשיר|קשיר היטב]] (כדי להגיע מ <math>(v_1,v_2,\dots,v_{n})</math>
אל <math>(w_1,w_2,\dots,w_{n})</math> יש לעקוב אחרי המסלול שקשתותיו מסומנות ב <math>w_1,w_2,\dots,w_{n}</math>) 
ולכן יש בגרף [[מסלול אוילר|מעגל אוילרי]].  המעגל האוילרי מגדיר סדרה על פי סימוני הקשתות שלאורכו. נוסף, ניתן לראות כי המעגל האוילרי בגרף מסדר <math>\ n-1</math> מגדיר  באופן טבעי [[מעגל המילטון]] בגרף מסדר <math>\ n</math> ושניהם מגדירים את אותה סדרה. כדי לודא כי הסדרה המוגדרת  היא אכן סדרת דה ברויין, נראה כי הרצף <math>(b_1,b_2,\ldots,b_{n})</math>
מופיע בסדרה בדיוק ב-<math>\ n</math> המקומות שמובילים אל הצומת <math>(b_1,b_2,\ldots,b_{n})</math>
במעגל ההמילטוני בגרף דה ברויין מסדר <math>\ n</math>.

לגרף  דה ברויין יש חשיבות גם כ[[טופולוגיית רשת]] המאפשרת [[ניתוב]] מהיר ויעיל.  הוא אף קשור ל[[ריצוף DNA|שיטות ריצוף]] של [[DNA]].{{כ}}{{הערה|1= לדוגמה Pavel A. Pevzner, Haixu Tang, Glenn Tesler: De novo repeat classification and fragment assembly. RECOMB 2004, 213-222}}

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}
{{קצרמר|מתמטיקה}}

[[קטגוריה:תורת הגרפים]]