Loading AI tools
מתמטיקה מוויקיפדיה, האנציקלופדיה החופשית
סדרת דה ברויין היא סדרה מעגלית מעל אלפבית בגודל שמכילה כל רצף באורך מעל בדיוק פעם אחת. אורך סדרה כזאת הוא בדיוק . הסדרות קרויות על שמו של המתמטיקאי ההולנדי ניקולאס חוברט דה ברויין שכתב עליהן מאמר ב-1946[1]. מאוחר יותר הסתבר שסדרות אלה היו ידועות קודם לכן[2]. באותה תקופה גם המתמטיקאי היהודי-אנגלי אירווינג ג'ון גוד (I. J. Good) גילה את הסדרות ובנייתן[3].
סדרות כאלה שימושיות למשל כדי לאתר מקום בסדרה לצורכי סנכרון - לאחר קריאת תת-סדרה כלשלהי באורך ניתן לדעת את מיקומה המדויק.
ניתן להגדיר סדרת דה ברויין בינארית באמצעות גרף המכונה גרף דה ברויין. גרף דה ברויין מסדר מעל אלפבית בגודל הוא גרף מכוון עם קודקודים, שכל קודקוד מייצג מחרוזת מעל באורך , כלומר . קבוצת הקשתות מוגדרת על ידי , דהיינו כל קודקוד מחובר לקודקודים שמתקבלים על ידי הזזה במקום אחד של המחרוזת שלו תוך השמטת האות הראשונה ותוספת של אות כלשהי בקוארדינטה האחרונה.
נסמן באופן טבעי את הקשתות באות החדשה שנוספה. ניתן לראות כי דרגת היציאה ודרגת הכניסה שתיהן וכי הגרף קשיר היטב (כדי להגיע מ אל יש לעקוב אחרי המסלול שקשתותיו מסומנות ב ) ולכן יש בגרף מעגל אוילרי. המעגל האוילרי מגדיר סדרה על פי סימוני הקשתות שלאורכו. נוסף, ניתן לראות כי המעגל האוילרי בגרף מסדר מגדיר באופן טבעי מעגל המילטון בגרף מסדר ושניהם מגדירים את אותה סדרה. כדי לודא כי הסדרה המוגדרת היא אכן סדרת דה ברויין, נראה כי הרצף מופיע בסדרה בדיוק ב- המקומות שמובילים אל הצומת במעגל ההמילטוני בגרף דה ברויין מסדר .
לגרף דה ברויין יש חשיבות גם כטופולוגיית רשת המאפשרת ניתוב מהיר ויעיל. הוא אף קשור לשיטות ריצוף של DNA.[4]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.