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

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

סדרת דה ברויין היא סדרה מעגלית מעל אלפבית בגודל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle k} שמכילה כל רצף באורך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle n} מעל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle A} בדיוק פעם אחת. אורך סדרה כזאת הוא בדיוק הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle k^n} . הסדרות קרויות על שמו של המתמטיקאי ההולנדי ניקולאס חוברט דה ברויין שכתב עליהן מאמר ב-1946[1]. מאוחר יותר הסתבר שסדרות אלה היו ידועות קודם לכן[2]. באותה תקופה גם המתמטיקאי היהודי-אנגלי אירווינג ג'ון גוד (I. J. Good) גילה את הסדרות ובנייתן[3].

סדרות כאלה שימושיות למשל כדי לאתר מקום בסדרה לצורכי סנכרון - לאחר קריאת תת-סדרה כלשלהי באורך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle n} ניתן לדעת את מיקומה המדויק.

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

ניתן להגדיר סדרת דה ברויין בינארית באמצעות גרף המכונה גרף דה ברויין. גרף דה ברויין מסדר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} מעל אלפבית בגודל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ k} הוא גרף מכוון עם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle k^{n}} קודקודים, שכל קודקוד מייצג מחרוזת מעל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle A} באורך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle n} , כלומר . קבוצת הקשתות מוגדרת על ידי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\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}\}.} , דהיינו כל קודקוד הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle v} מחובר לקודקודים שמתקבלים על ידי הזזה במקום אחד של המחרוזת שלו תוך השמטת האות הראשונה ותוספת של אות כלשהי בקוארדינטה האחרונה.

נסמן באופן טבעי את הקשתות באות החדשה שנוספה. ניתן לראות כי דרגת היציאה ודרגת הכניסה שתיהן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \displaystyle k} וכי הגרף קשיר היטב (כדי להגיע מ הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (v_1,v_2,\dots,v_{n})} אל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (w_1,w_2,\dots,w_{n})} יש לעקוב אחרי המסלול שקשתותיו מסומנות ב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w_1,w_2,\dots,w_{n}} ) ולכן יש בגרף מעגל אוילרי. המעגל האוילרי מגדיר סדרה על פי סימוני הקשתות שלאורכו. נוסף, ניתן לראות כי המעגל האוילרי בגרף מסדר מגדיר באופן טבעי מעגל המילטון בגרף מסדר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} ושניהם מגדירים את אותה סדרה. כדי לודא כי הסדרה המוגדרת היא אכן סדרת דה ברויין, נראה כי הרצף הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b_1,b_2,\ldots,b_{n})} מופיע בסדרה בדיוק ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} המקומות שמובילים אל הצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b_1,b_2,\ldots,b_{n})} במעגל ההמילטוני בגרף דה ברויין מסדר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 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. ^ 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
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
Logo hamichlol.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0