די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאריע

אין דער וועלט פון נאטור און וויסנשאפט

די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאריע

הודעהדורך מי אני » פרייטאג מאי 22, 2020 4:03 pm

די פּרעגעל טייך לויפט דורך דעם שטאט קאָניגסבּערג (היינטיגע קאלינינגראד), צוטיילענדיג דעם שטאט אין צו צוויי אינזלען וממילא אין צו פיר לאנד מאסעס. באהעפטענדיג דאס אלעס אין 1736 זענען געווען זיבן בריקן כזה:
IMG_6962.png
IMG_6962.png (34.16 KiB) געזען געווארן 354 מאל



דער בירגערמייסטער פון א דערנעבענדן שטאט קארל גאטליבּ איִלער, וואס איז געווען א שטיקל מאטעמאטיקער, איז געווען נייגעריג צו מ׳קען מאכן א וועג וואו מ׳גייט דורך יעדעס בריק אָן איבערגיין א בריק צוויי מאל. (און פארשטייט זיך אז מ׳מוז נוצן די ברקים אנצוקומען צום לאנד מאסע און מ׳שטעלט זיך נישט אפ אינמיטן א בריק.) ער האט געשיקט די פראגע צום בארימטן מאטעמאטיקער לעאנהערד אוילער.

צום ערשט האט אוילער נישט געהאלטן אז דאס האט אזוי ווייט מיט מאטעמאטיקס. דערנאך האט ער אבער אריינגעקלערט אז דאס האט יא א שייכות מיט דזשיאמעטרי; וואס ער האט גערופן די דזשיאמעטרי ״פון פּאזיציע״. ער האט באמערקט אז די איינציגסטע זאך וואס איז נוגע דא זענען די בריקן. ולא זו בלבד, נאר אפילו די פאזיציעס וואו די לאנד מאסעס זענען איז בעצם אויך נישט ממש רעלעוואנט. דהיינו, יעדע לאנד מאסע ווערט גערעכענט ווי איין נוֺיד/ווערטעקס [א פּונקט] און די בריקן זענען ליינס וואס באהעפטן איין נוֺיד/ווערטעקס צום אנדערן. אין אזא פאל קען מען אפילו אויסשטעלן די נוֺידס/ווערטעקסעס אין א גראדע שורה נאר מ׳מאכט ליינס פון איין נוֺיד/ווערטעקס צום אנדערן לויט וויפיל בריקן באהעפטן זיי. למשל, די מיטעלסטע לאנד מאסע, נוֺיד/ווערטעקס, גייט האבן 5 ליניעס ארויסקומען דערפון: צוויי צו וואו אימער איך שטעל דעם אויבערשטען פונקט, צוויי צו וואו אימער איך שטעל דעם אונטערשטן פונקט, און איינס צו וואו אימער איך שטעל דעם רעכטן פונקט. ווען איך רעכן נאר נוֺידס/ווערטעקסעס [פונקטן] און ליינס רופט זיך דאס א גרעף.

דערנאך האט ער איינגעזעהן אז אויב איינער גייט צו א פונקט דורך א בריק מוז ער דאך ארויסקומען פון דארט, און דאס קען דאך נאר זיין דורך אן אנדערן בריק כנ״ל; עס מוז האבן אן איִווען נומער פון בריקן. די איינציגסטע יוצאי מן הכלל פון דעם זענען די פּונקטן וואו מ׳הייבט אן און וואו מ׳ענדיגט. פון דעם קומט אויס אז נאר צוויי פּונקטן קענען האבן אן אַדד נומער פון ליינס וואס קומען ארויס דערפון.

העולה מכל זה איז אז אויב וויל מען וויסן מעיקרא צו מען וועט קענען מאכן אזא סארט [טרעווערסיבּל] דרך וואו מ׳גייט דורך א ליין נאר איינמאל, איז אדער וועלן אלע פונקטן וואס די ליינס טוהן באהעפטן האבן נאר אן איִווען צאל פון ליינס וואס קומען ארויס פון זיי, אדער אז נאר פונקטליך צוויי פון די פּונקטן האבן אן אַדד צאל פון ליינס וואס קומען ארויס פון זיי (און די איבעריגע האבן אן איִווען צאל). די צוויי אַדד נומערן וועלן זיין וואו מ׳הייבט אן און וואו מ׳ענדיגט, או אויב אלע זענען איִווען ענדיגט מען בעצם וואו מ׳הייבט אן [אן אוילעריען סירקוּט].

אין קאָניגסבערג האבן אלע 4 פּונקטן אן אַדד צאל פון ליינס/בריקן וואס באהעפטן זיי איינע צו די אנדערע [3, 3, 3, און 5]. דעריבער האט עס נישט קיין אוילעריען דרך און עס איז נישט מעגליך צו אריבערגיין אלע בריקן אן נוצן א בריק צוויי מאל.

בשעת׳ן צווייטן וועלט קריג האבן די רוסן באמבאדירט צוויי פון די בריקן, וואס דאס האט געשאפן אז טאקע נאר צוויי פון די פּונקטן האבן געהאט דריי בריקן וואס באהעפטן זיי צו אנדערע פּונקטן [אן אַדד נומער], און די אנדערע צוויי האבן געהאט צוויי בריקן [אן איווען נומער], וממילא איז דעמאלטס יא געווארן שייך אריבערצוגיין אלע בריקן אן אריבערגיין איינס צוויי מאל.

דאס קען מען נוצן ביי די סארט חידות וואו מ׳גיבט א סארט שׁעיפּ און מ׳פרעגט אויב מ׳קען (מיט א פּען) מאכ׳ן א דרך מיט׳ן אריבערגיין די שׁעיפּ, אָן אויפהייבן די פּען און אָן אריבערגיין א ליין צוויי מאל. דאס רופט זיך אן אוילעריען דרך על שמו. די פריערדערמאנטע כלל זאגט אויב ס׳איז בכלל שייך.

פון דעם איז ארויסגעוואקסן א נייע פעלד אין מאטעמאטיקס: גרעף טעאריע.

דא אונטן איז די זעלבע מאפע פון קאָניגסבּערג מיט אירע בריקן אויסגעשטעלט אלס א גרעף.
בייגעלייגטע פיילס
IMG_6963.png
IMG_6962.png
IMG_6962.png (34.16 KiB) געזען געווארן 357 מאל
רעדאגירט געווארן צום לעצט דורך מי אני אום פרייטאג מאי 22, 2020 4:37 pm, רעדאגירט געווארן איין מאל בסך הכל.
"איך בין אפילו נישט זיכער אז איך עקזיסטיר, ווי אזוי קען איך זיין זיכער אז"... - יאיר דא
באניצער אוואטאר
מי אני
שריפטשטעלער
שריפטשטעלער
 
הודעות: 1197
זיך רעגיסטרירט: פרייטאג אקטאבער 05, 2018 4:32 pm
האט שוין געלייקט: 6113 מאל
האט שוין באקומען לייקס: 878 מאל

הודעהדורך פארוואס? » פרייטאג מאי 22, 2020 4:21 pm

ייש"כ פארן נעמען די מיה צו אונז געבן א טעימה פון די גראף טעאריע.

דאס איז זייער נוגע אין אסאך תחומים פון לעבן, און צומאל אין אומערווארטעטע סיטואציעס.
א גראף קען ווערן גענוצט צו באשרייבן א מאדעל פון א געוויסע פראבלעם.
עס ווערט אפט גענוצט אין קאמפיוטער סייענס, אין פיזיקס/קעמיסטרי און אפילו אין סאציעלע סטודיס.

עס וואלט געווען אינטרעסאנט, אויב דו קענסט טרעפן נאך גוטע דוגמאות פון נוצבארע פראבלעמען אין גראף טעאריע.
אסור ליראת שמים שתדחק את המוסר הטבעי של האדם, כי אז אינה עוד יראת שמים טהורה.
סימן ליראת שמים טהורה הוא כשהמוסר הטבעי, הנטוע בטבע הישר של האדם, הולך ועולה על פיה במעלות יותר גבוהות ממה שהוא עומד מבלעדה.

~ אורות ישראל להגראי"ה קוק
פארוואס?
שריפטשטעלער
שריפטשטעלער
 
הודעות: 893
זיך רעגיסטרירט: פרייטאג יאנואר 31, 2014 12:28 pm
האט שוין געלייקט: 1479 מאל
האט שוין באקומען לייקס: 1743 מאל

Re: די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאר

הודעהדורך מי אני » פרייטאג מאי 22, 2020 5:16 pm

א באקאנטע נושא בתוך גרעף טעאריע איז די טרעוועלינג סעילסמאן פראבלעם. דאס פרעגט אז א מענטש וואס דארף ארומגיין צו א פאר שטעט [״פונקטן״], וואס איז די קערצטע וועג אין וואס ער קען דאס מאכן [די קורצסטע/ווייניגסטע ״ליינס״ וואס באהעפטן די ״פונקטן״]? דאס איז ענליך צום פראגע וואס מאטערן מוסדות יערליך איבער וויאזוי צו מאכן די שנעלסטע/קורצסטע בּאָס רוּט... די שאלה, אין אלגעמיין נעמט נאר אריין די וועריעבּל פון לענג בלבד (נישט איכות: טראפיק פון איין קורצע ליין וואס איז מער און שטאַטער ווי א לאנגע ליין וכו׳).

די שאלה איז א דוגמא פון א שאלה וואס מ׳קען גרינג מברר זיין איר ענטפער לאחר המעשה, אבער איז (אסאך) שווערער אויפצוקומען מיט אן אלגאריטם וכו׳ מעיקרא דאס צו מסדר זיין (ועיין כאן).

אן אינטרעסאנטע זאך מיט די שאלה איז אז די אויבן-אויף׳דיגע סברא אז פון די פונקט וואו מ׳הייבט אן זאל מען גיין צום נענטסטן פונקט, און פון דארט צום נענטסטן פונקט אא״וו גייט בדרך כלל נישט גיבן די שנעלסטע/קורצסטע וועג, ובפרט טאמער דארף מען צוריקומען צו וואו מ׳האט אנגעהויבן. קאָמפּיוּטערס וכדומה רעכענען אויס די פראבלעם דורכ׳ן אויסשטעלן א רוּט און דערנאך פארעכטען די לענג צווישן צוויי פון די פונקטן (אינעם קאנטעקסט פון די אנדערע און לענג אָוועראָל) צו א קורצערע וכן הלאה, ביז מ׳קומט אן צו א רוּט וואס איז די קורצטסטע אָוועראָל.
"איך בין אפילו נישט זיכער אז איך עקזיסטיר, ווי אזוי קען איך זיין זיכער אז"... - יאיר דא
באניצער אוואטאר
מי אני
שריפטשטעלער
שריפטשטעלער
 
הודעות: 1197
זיך רעגיסטרירט: פרייטאג אקטאבער 05, 2018 4:32 pm
האט שוין געלייקט: 6113 מאל
האט שוין באקומען לייקס: 878 מאל

די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאריע

הודעהדורך מי אני » פרייטאג מאי 22, 2020 6:11 pm

נאך אן אינטרעסאנטע זאך וואס האט א שייכות מיט גרעף טעאריע איז די פיר קאליר טעאריאָם. דאס לויטעט אז אויף א (נארמאלע גראדע) פאפיר וואס איז צוטיילט אין אסאך שׁעיפּס וואס די וואנט פון איינע רירט אן די צווייטע וכו׳, וועל איך נישט דארפן האבן מער ווי פיר קאלירן זיי אלע צו פארבן אויף אזא אופן אז קיין איין שׁעיפּ זאל נישט זיין די זעלבע קאליר פון עני פון די ארומיגע שׁעיפּס מיט וואס זי טוהט טיילן/שׁעירן א וואנט (נישט אן עק). פארשטייט זיך אז דאס רעדט זיך ווען איך מיש מיך נישט אריין אינדערמיט און זאג אז ״די שׁעיפּ מוז זיין די קאליר דוקא אזוי ווי די געוויסע אנדערע שׁעיפּ״. דאס קען פאסירן ביי א מאפע וואו איך מוז פארבן א געוויסע שׁעיפּ די זעלבע ווי א געוויסע אנדערע שׁעיפּ וואס געהערט צום זעלבן לאנד וכו׳. אין אזא פאל וועט די טעארעם נישט האלטן.

(דאס אז מ׳דארף נישט מער ווי 5 קאלירן האט מען געוואוסט אסאך פריער. אז מ׳דארף נישט מער ווי 4 קאלירן איז שווערער אויפצוווייזן.)

מ׳האט דאס אויפגעוואוזן עפ״י גרעף טעאריע. דהיינו, אז א גראדע גרעף איז פיר קאליר׳עבל. למשל, כזה:
IMG_6965.png


קיין איינע פון די פונקטן טוהט נישט זיך נישט באהעפטן דורך א ליין צו א פונקט וואס האט די זעלבע קאליר ווי איר.

*

אין דעם סוגיא איז דא די העדווידזשער-נעלסאן פראבלעם. דאס פרעגט אז אויב מאך איך פונקטן וואס צווישן יעדעס איינס אין אנדערן/נעקסטן איז דא די זעלבע לענג, וויפיל קאלירן וועל איך דארפן אז א פונקט אין אלע אירע ארומיגע זאלן נישט זיין די זעלבע? מ׳ווייסט אז 7 איז גענוג און אז 4 איז נישט גענוג.
"איך בין אפילו נישט זיכער אז איך עקזיסטיר, ווי אזוי קען איך זיין זיכער אז"... - יאיר דא
באניצער אוואטאר
מי אני
שריפטשטעלער
שריפטשטעלער
 
הודעות: 1197
זיך רעגיסטרירט: פרייטאג אקטאבער 05, 2018 4:32 pm
האט שוין געלייקט: 6113 מאל
האט שוין באקומען לייקס: 878 מאל

די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאריע

הודעהדורך מי אני » זונטאג מאי 24, 2020 12:10 am

די טרעוועלינג סעילסמאן פראבלעם איז א דוגמא פון וואס מ׳רופט אין גרעף טעאריע א העמילטאָניען דרך פראבלעם (בכלל). דהיינו, צו טרעפן א (קורצסטע) דרך וואו מ׳באזוכט יעדעס פּונקט נאר איינמאל (צומאל איז דאס א סייקל, ווען מ׳דארף צוריק קומען צום פונקט וואו מ׳האט אנגעפאנגן, און צומאל נישט; סתם א דרך).

די שוועריקייט פון טרעפן די דרך איז ווייל די מעגליכע דרכים זענען די פעקטאָריעל פון וויפיל פונקטן [נוידס] די גרעף האט. פאר (גאר) אסאך פונקטן איז דאס גאר (גאר) אסאך דרכים, און זיי דורכגיין איינס-ביי-איינס איז שטאַט אפילו פאר א שטארקע קאמפיוטער.

נאך אן אינטרעסאנטע סארט חקירה אין די סוגיא איז צו טרעפן אויף א שאך ברעט (פון א געוויסע לענג און ברייט פון קעסטעלעך; עס דארף נישט זיין די קלאסישע שאך ברעט) א פערד׳ס דרך. דהיינו, די פערד שטיקל פונעם שאך שפיל רוקט זיך, ווי באקאנט, דוקא [אין יעדע דירעקציע] צוויי גראד און דערנאך איינס צו לינקס אדער רעכטס. די מטרה פון די פראבלעם איז צו טרעפן א דרך וואו דאס פערד שטיקל זאל באזוכן יעדעס פלאץ אויפ׳ן ברעט נאר איין מאל. אויב ענדיגט זיך דאס ביי א פלאץ וואס איז איין פערד-רוק אוועק פון וואו עס האט זיך אנגעהויבן, איז עס א ״פארמאכטע״ דרך [א העמילטאָניען סייקל], אנדערש איז עס אן ״אפענע״ דרך [א העמילטאָניען דרך].

טאמער האט די ברעט סיי אין די לענג און סיי אין די ברייט אן אַדד צאל פון קעסטעלעך איז אומעגליך צו מאכן א ״פארמאכטע״ פערד׳ס דרך. ווי אויך איז דאס אומעגליך טאמער זענען די זייטן נאר 1, 2, אדער 4 קעסטעלעך לאנג. אדער טאמער איז די לענג און די ברייט פונעם ברעט נישט אייניג און די קלענערע זייט איז 3 קעסטעלעך לאנג, בשעת די לענגערע זייט איז 4, 6, אדער 8 קעסטעלעך לאנג.
ווי אויך איז אויפגעוואוזן אז טאמער איז די קלענערע זייט צום ווייניגסטענסט 5 קעסטעלעך לאנג איז זיכער דא כאטש אן ״אפענע״ דרך.

די פראבלעם האט מען גראדע א שטיקל געפארשט נאך פאר׳ן אויפשטייג פון גרעף טעאריע.

הגם, (ווי דערמאנט) זענען די סארט העמילטאָניען דרך פראבלעמען בדרך כלל שווער מפשר צו זיין מעיקרא און ארויסהאבן אן אלגאריטם דערפאר, איז די פערד דרך גרינגער אין אלגעמיין. למשל, אין דעם איז דא ווארנסדארף׳ס רוּל. דאס זאגט אז ווען איך האב אן אויסוואל פון אפאר קעסטעלעך וואו אהין צו רוקן דעם פערד, זאל איך אים רוקן צום קעסטעל פון וואו עס האט דערנאך די ווייניגסטע אויסוואלן וואו אהין צו גיין פון דארט. אין גרעף טעאריע מיינט דאס גיין צום פונקט פון וואו עס איז דא די ווייניגסטע ליינס וואס קומען ארויס דערפון. מ׳רעכענט נישט אלס אן אויסוואל קעסטעלעך וואס מ׳האט שוין באזוכט.

א וועריעישאן פון דעם סארט פראבלעם בכלליות איז צו טרעפן א דרך וואו די פערד קען באזוכן די מערסטע קעסטעלעך אָן אריבערגיין א פלאץ וואס דאס פערד איז אריבערגעפלויגן, אפילו עס האט נישט געלאנדעט אויף יענע קעסטעלעך.

***

די האנט-גיבן לעמאַ, אז ביי א צאמקום פון מענטשן וועט זיין אן איִווען צאל פון מענטשן וואס האבן יעדעס איינס געגעבן די האנט פאר אן אַדד מאל פון מענטשן (דערמאנט דא), קומט אויך אפיר פון גרעף טעאריע. דאס קומט אפיר אז ביי יעדע אומדירעקטירטע גרעף, דהיינו וואו די ליין פון איין פונקט צום אנדערן קען גיין אהין און/אדער צוריק [מיינענדיג איך קען עס אנקוקען פון נויד א׳ צו ב׳ פונקט אזוי ווי וואו פון נויד ב׳ צו א׳, אזוי ווי ביי צוויי אירע וואס גיבן זיך די האנט; ס׳איז מעגליך אזוי און/אדער פונקט אזוי מעגליך אזוי פארקערט], וועט זיין אן איִווען צאל פון פונקטן מיט אן אַדד צאל פון ליינס.
"איך בין אפילו נישט זיכער אז איך עקזיסטיר, ווי אזוי קען איך זיין זיכער אז"... - יאיר דא
באניצער אוואטאר
מי אני
שריפטשטעלער
שריפטשטעלער
 
הודעות: 1197
זיך רעגיסטרירט: פרייטאג אקטאבער 05, 2018 4:32 pm
האט שוין געלייקט: 6113 מאל
האט שוין באקומען לייקס: 878 מאל

Re: די זיבן קאניגסבערג בריקן און דאס אויפשטייג פון גרעף טעאר

הודעהדורך מי אני » דאנערשטאג מאי 28, 2020 7:47 pm

אין דעם איז דא די גרעיספוּל בוים קאנדזשעקטשור. א ״בוים״ גרעף איז אזא סארט גרעף וואס הגם איין פונקט קען האבן ליינס צו מער ווי איין אנדערע פונקט, וועט אבער יעדע פונקט/נוֺיד האט נאר איין ליין וואס באהעפט עס צו אן אנדערע פונקט/נוֺיד. ועוד, דאס וועט נישט זיין א סייקליק גרעף, וואס באהעפט זיך אין אזא סארט וועג צו שאפן א רינג. (צווישן אפאר אנדערע פרטים וואס מאכן עס זיין א ״בוים״.)

די קאנדזשעקטשור לויטעט אז ביי אזא סארט ״בוים״ גרעף אויב האב איך עני סעט פון נומערן וואס איינס איז נישט די זעלבע ווי די אנדערע, איז דא א וועג ווי אזוי איך קען גיבן יעדעס פונקט אויף די גרעף איין נומער אזוי אז די חילוק צווישן די נומערן פון צוויי פונקטן וואס זענען נעבן איינע די אנדערע זאל אלעמאל זיין אנדערש ווי די חילוק פון עני אנדערע צוויי נומערן וואס זענען פון אנדערע נעבנ׳דיגע פונקטן. דאס רופט זיך א ״גרעיספוּל״ גרעף.

דאס איז א משל:
IMG_6989.png
IMG_6989.png (7.01 KiB) געזען געווארן 87 מאל



די קאנדזשעקטשור בכלליות איז נאך נישט אויפגעוואוזן. חלקים זענען אבער יא אויפגעוואוזן, ווי אויך אז דאס איז אמת ביי אנדערע סארטן גרעפס. למשל, ביי א ״קאטערפּילער״ גרעף, וואס איז א סארט ״בוים״ גרעף וואס האט א גראדע ליין פון פונקטן וואס פון דעם שטעקן זיך ארויס ״צווייגן״ צו פונקטן אזוי אז אלע פונקטן פון די ״צווייגן״ זענען די זעלבע ווייט פונעם גראדע ליין, איז די קאנדזשעקטשור יא אויפגעוואוזן צו זיין אמת. ווי אויך אויב האט די ״בוים״ גרעף נישט מער ווי 35 פונקטן איז די קאנדזשעקטשור אויך אויפגעוואוזן. ווי אויך, למשל, ביי אלע ״רעדל״ גרעפס, וואס זענען גרעפס ווי פונקטן מאכן א רינג דורך זייערע ליינס און אלע פונקטן זענען אויך באהאפטן צו א מיטעלסטע פונקט אינדערמיט פונעם רינג, איז די קאנדזשעקטשור אויך אויפגעוואוזן.
"איך בין אפילו נישט זיכער אז איך עקזיסטיר, ווי אזוי קען איך זיין זיכער אז"... - יאיר דא
באניצער אוואטאר
מי אני
שריפטשטעלער
שריפטשטעלער
 
הודעות: 1197
זיך רעגיסטרירט: פרייטאג אקטאבער 05, 2018 4:32 pm
האט שוין געלייקט: 6113 מאל
האט שוין באקומען לייקס: 878 מאל


גיי צוריק וויסנשאפט

ווער איז יעצט דא?

באניצער וואס לייענען דעם פארום: נישטא קיין אנליין באניצער און 2 געסט