קאווע שטיבל

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



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

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

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

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

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

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

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

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

דא אונטן איז די זעלבע מאפע פון קאָניגסבּערג מיט אירע בריקן אויסגעשטעלט אלס א גרעף.

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

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

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

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

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

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

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

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

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


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

*

אין דעם סוגיא איז דא די העדווידזשער-נעלסאן פראבלעם. דאס פרעגט אז אויב מאך איך פונקטן וואס צווישן יעדעס איינס אין אנדערן/נעקסטן איז דא די זעלבע לענג, וויפיל קאלירן וועל איך דארפן אז א פונקט אין אלע אירע ארומיגע זאלן נישט זיין די זעלבע? מ׳ווייסט אז 7 איז גענוג און אז 4 איז נישט גענוג.

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

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

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

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

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

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

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

***

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

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

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

דאס איז א משל:



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

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

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

עס איז דא א קאנצעפט אין טאפּאלאגיע וכו׳ פון א מינימעל סורפעס. בקיצור נמרץ מאד זענען דאס סארטן פון שׁעיפּס וואס אונטער געוויסע וואליוּמס וואס מ׳וויל ארומנעמען לויט די קאנטעקסט וועט דאס האבן די ווייניגסטע סורפעס עריע [ארום די סורפעסעס פון די גאנצע שׁעיפּ] א ספיִר/בּאָל איז א גאר פשוטע פאל און משל. ס׳איז געווען א סארט מינימעל סורפעס וואס קאמפיוטערס [מאדעלס] האבן געצייגט אז עס קען עקזיסטירן אבער מאטעמאטיקער, עפ״י אלגעמיינע כללים אין פּרופס וכו׳, זענען געווען שטארק סקעפטיש דערין. האבן זיי דאס גערופן א האָרגען סורפעס על שמו פון דעם דזשאן האָרגען וואס האט געהאלטן אז קאמפיוטערס גייען איבערנעמען אוי ריפּלעיסען געהעריגע מאטעמאטישע פּרופס. צום סוף האבן זיי געהאט א נקמה ווען זיי האבן אויפגעוואוזן, געהעריג, אז די סארט סורפעס עקזיסטירט טאקע נישט. זיי האבן עס אנגעהויבן רופן א נאן-האָרגען סורפעס.

אין די סוגיא איז דא די פרייליכע ענדינג טעארעם. דאס צו מסביר זיין דארף מען מקדים זיין די חילוק צווישן א קאנוועקס פּאַליגאַן/שׁעיפּ און איינס וואס איז נישט קאנוועקס. א קאנוועקס שׁעיפּ באדייט אז אירע עקן גייען זיך נישט ״אריינ״שטעקן אינעם שׁעיפּ, משא״כ ביי א שׁעיפּ וואס איז נישט קאנוועקס. אין אנדערע ווערטער, יעדע ענגעל פון אן עק/ווערטעקס פון א קאנוועקס שׁעיפּ, פון אינעווייניג אינעם שׁעיפּ, וועט נישט זיין מער ווי 180 דעגריס. למשל, א פּענטאגאן איז א קאנוועקס שׁעיפּ אבער א שטערן איז נישט.

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

זשעקערעס צוזאמען מיט פּאָל ערדאס האבן קאנדזשעקטשורד ברייטער אז אויב וויל איך וויסן די מינימאלע צאל פון וויפיל נוֺידס/פונקטן איך וועל דארפן צו קענען זיכער שאפן דורך זיי א דייקא קאנוועקס שׁעיפּ פון א געוויסע צאל עקן, איז די נעם איך 2 צו די עקספאנענט פון צוויי ווייניגער ווי די צאל עקן וואס איך וויל אינעם שׁעיפּ און דערנאך לייג איך צו 1. אין אונזער פאל איז די צאל פון עקן 4, איז 2 צו אן עקספאנענט פון 4-2=2, דהיינו 2² איז 4 און דערנאך נאך 1 איז 5, וואס דאס האט מען טאקע אויפגעוואוזן פאר א פיר-עק.

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

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

***

רעדענדיג פון א העמילטאניען דרך, א דרך/גרעף וואס באזוכט יעדעס נוֺיד נאר איינמאל, איז אינטרעסאנט צו דערמאנען די סקווער סומע פראבלעם אין ריקריעישאנעל מאטעמאטיקס. דאס פרעגט אז אויב דו האסט א סעט פון נומערן זאלסטו דאס שטעלן אין א סדר אזוי אז יעדע צוויי נומערן וואס זענען נאנט איינע צו די אנדערע זאלן צוזאמען זיין א (פּערפעקט) סקווער (עיין באשכול זו). למשל, אז מ׳האט די נומערן 1,3,6,8,10 קען איך דאס אויסשטעלן אלס 10,6,3,1,8. ווייל 10 מיט די 6 נעבן עס איז צוזאמען 16 וואס איז 4², דערנאך 6 מיט די 3 נעבן עס איז 9 וואס איז 3², וכן הלאה.

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

בנוגע סייקעלס אין א גרעף איז דא די ערדאס-גיארפאס קאנדזשעקטשור. דאס לויטעט אז אויב האט די גרעף א נוֺיד/פונקט וואס האט א דעגרי פון צום ווייניגסטנס 3, דהיינו אז עס האט צום ווייניגסטנס 3 ליינס וואס קומען ארויס דערפון, דעמאלטס וועט מען קענען מאכן דערין א פשוט׳ע סייקל, דהיינו א דרך וואו איך קום צוריק אן צו וואו איך האב אנגעהויבן אן אדורכגיין איין פונקט מער ווי איין מאל, וואס די לענג [אין פּונקטן] וועט אלעמאל זיין א נומער וואס איך קען באקומען דורכ׳ן גיבן א גאנצע נומער עקספאנענט צו 2. דער מאטעמאטיקער דר. פּאָל ערדאס האט צוגעזאגט $100 פאר ווער עס ווייזט עס אויף און $50 פאר ווער עס פרעגט עס אפ.

מ׳ווייסט אז אויב איז דאס נישט אמת מוז עס זיין ביי א גרעף וואס האט צום ווייניגסטענס 17 נוֺידס, און טאמער האט דאס נאר נוֺידס וואס יעדעס איינע האט 3 ליינס/ווערטיסיִס וואס קומען ארויס דערפון [א קיוּבּיק גרעף] וועט דאס דארפן האבן צום ווייניגסטענס 30 נוֺידס.

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

כמובן קען די קראמעטיק נומער פונעם גרעף נישט זיין מער ווי די סומע פון נוֺידס וואס עס האט. ווי אויך אויב איז דא א ליין/עדזש צווישן צוויי נוֺידס קען עס נישט זיין ווייניגער ווי 2. ווי אויך אויב איז עס א פשוט׳ע סייקל און עס האט אן איִווען צאל פון נוֺידס דארף איך נישט מער ווי 2 קאלירן, און אויב האט עס אן אַדד צאל פון נוֺידס דארף איך נישט מער ווי 3.

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

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

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

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

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

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

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

דערנאך איז דא אין דעם די געדאנק פון די עקוויטעבּל קראמעטיק נומער. דאס איז ווען איך לייג צו נאך א תנאי צום קאלארינג פונעם גרעף וואו איך וויל אז נאכדעם וואס איך קאליר אלע נוֺידס מיט די תנאים כנ״ל און דערנאך צייל איך וויפיל נוֺידס עס זענען דא פון יעדע קאליר זאלן זיי אלע זיין די זעלבע אדער עכ״פ נישט מער ווי 1 גערוקט אין צאל איינע פונעם צווייטן. דאס רופט זיך אן עקוויטעבּל קאלארינג.

אין דעם איז דא די האזשנאל-זשעמערעדי טעארעם. דאס לויטעט אז יעדע גרעף גייט זיכער האבן אן עקוויטעבּל קאלארינג מיט כאטש אזויפיל קאלירן ווי 1 מער ווי די גרעסטע דעגרי דערין [די מערסטע ליינס וואס קומען ארויס פון 1 נוֺיד]. אבער אויף געוואוּר צו ווערן אויב א געוויסע גרעף האט אן עקוויטעבּל קאלארינג מיט א געוויסע צאל פון קאלירן איז אויך אן NP שווער (ואפילו לרבות קאָמפּליט) פראבלעם.

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

דא איז א בילד פון א משל וואו די ״געוויסע צאל״ איז 4:

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

מ׳אפפערט $500 פאר ווער עס קען עס אויפווייזן.

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

אפאר תנאים וואס א פּלאנאר גרעף, וואס אלע אירע נוֺידס זענען באהאפטן צום גרעף און עס איז פשוט [איין ספעציפישע נוֺיד צו אן אנדערע ספעציפישע נוֺיד האט נישט מער ווי איין ליין], דארף האבן איז אז אויב האט עס 3 נוֺידס אדער מער דעמאלטס:

1). אויב עס האט נישט אין זיך קיינע סייקלס פון מער ווי 3 נוֺידס, גייען די צאל פון אירע עדזשעס/ליינס נישט זיין מער ווי 6 ווייניגער ווי 3 מאל די צאל פון אירע נוֺידס.

2). אויב יא גייען די צאל פון אירע עדזשעס/ליינס נישט זיין מער ווי 4 ווייניגער ווי 2 מאל די צאל פון אירע נוֺידס.

3). אירע פנימער [דאז הייסט אין וויפיל חלקים טוהן די ליינס פון די גרעף צוטיילן מקום ווען עס איז אין איר פּלענאר פארעם] גייען נישט זיין מער ווי 4 ווייניגער ווי 2 מאל די צאל פון אירע נוֺידס.

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

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

אין דעם איז געווען טעיט׳ס קאנדזשעקטשור וואס האט געקלערט אז אויב איז דאס א פּלענאר גרעף וואס איז קיוּבּיק, דהיינו אז אלע אירע נוֺידס/ווערטיסיִס האבן דריי עדזשעס/ליינס וואס קומען ארויס פון זיי, און מ׳קען נישט מאכן די גרעף אומבאהאפטן אן צום ווייניגסטענס אוועקנעמען 3 נוֺידס, וועט דאס זיכער האבן א העמילטאניען סייקל. דער בריטישער מאטעמאטיקער וויליאם טאמאס טאָט האט אויפגעוואוזן אז דאס איז נישט אמת.

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

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

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

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

אין דעם איז דא די לאוואש קאנדזשעקטשור. דאס לויטעט אז יעדע ווערטעקס-טראנסיטיוו גרעף, וואס אלע אירע נוֺידס זענען באהאפטן און עס איז פיניט, וועט פארמאגן א העמילטאניען דרך. מ׳ווייסט פון 5 אזעלכע סארט גרעפס וואס האבן א העמילטאניען דרך אבער נישט א העמילטאניען סייקל; די אנדערע וואס מ׳ווייסט האבן אלע העמילטאניען סייקלס. איז דא וואס ווילן נעמען דעם קאנדזשעקטשור נאך ווייטער און זאגן אז אלע ווערטעקס-טראנסיטיוו גרעפס וועלן האבן העמילטאניען סייקלס חוץ די 5 וואס מ׳ווייסט וואס האבן נאר העמילטאניען דרכים.

אין דעם פון העמילטאניען סייקלס ביי פּאליִהיִדרא, 3D שׁעיפּס געמאכט אזוי אין צו 2D אין צו א גרעף אזוי אז יעדע פון אירע ווערטיסיִס/עקן זענען א פונקט אין דעם גרעף און די זייטן פון די 2D שׁעיפּס וואס שאפן דאס זענען די עדזשעס/ליינס פון איין פונקט צום צווייטן [פריער איז די משל געווען מיט די פּלעטאניק סאלידס], איז דא בּאַרנעט׳ס קאנדזשעקטשור. דאס אנבאלאנגט בּייפּארטייט גרעפס און סימפּל פּאַליטוֺיפּס.

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

‏סימפּל פּאַליטוֺיפּס זענען שׁעיפּס וואס אלע אירע עקן/ווערטיסיִס דערין וועלן זיין עקן פון אזויפיל גראדע עקן (נישט ״קאָרנערס״ וואו ס׳קומען זיך צאם די עקן, וואס דאס איז די ווערטעקס אליין) ווי די דיימענשאן פון די שׁעיפּ, ווי אויך וועלן די צאל פון פּענימער פון די (איין-דיימענשאן ווייניגער) שׁעיפּס וואס נעמען דאס ארום זיין די צאל פון די דיימענשאן פונעם שׁעיפּ. למשל, א קיוּבּ איז אזא סארט פּאַליִטוֺיפּ. עס איז א 3D פּאַליִהיִדראן וואס יעדע קאָרנער/ווערטעקס דערפון האט 3 ״גראדע״ עקן [עדזשעס] וואס קומען ארויס דערפון, און עס האט 3 זייטן [פּענימער] פון [2D] סקווערס וואס נעמען דאס ארום.

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

מ׳ווייסט זיכער אז דאס איז אמת ביז אזא סארט גרעף וואס פארמאגט 86 פונקטן. מ׳ווייסט אויך אז טאמער ביי אזא סארט גרעף וועלן אלע אירע אפגעטיילטע חלקים/חללים האבן ארום זיך 4 אדער 6 ליינס/עדזשעס וועט עס זיכער זיין העמילטאניען.

***

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

מענין לענין באותו ענין פון א שׁאַך-פערד׳ס דרך איז דא אן אינטרעסאנטע סיִקווענס דערין פונעם מאטעמאטיקער דר. ניעל סלוֺין וואס ער רופט די טרעפּט נייט [פערד] סיקווענס. דאס הייבט זיך אן וואו איך מאך א סקווער אולאם ספּיירעל אויף א(ן אינפיניט) שאך ברעט. דהיינו, איך הייב אן ביי א קעסטל פון 1, די קעסטל אונטער דעם איז 2, צו לינקס דערפון 3, העכער דעם 4, העכער דעם 5, [דערנאך בין איך שוין העכער דעם 1] רעכטס דערפון 6 אא״וו. דערנאך לייג איך דעם פערד אויף קעסטל 1. איך זאג אז איך קען נאר רוקן דעם פערד צום קעסטל מיט די נידעריגסטע נומער שייך און איך קען אים נישט רוקן צו א קעסטל וואו ער איז שוין געווען. די ערשטע נומערן קומען אויס צו א סיִקווענס פון 1,10,3,6,9,4,7 אא״וו.

עס גייט אויסקומען אז נאך די 2015׳סטע רוק וועט עס בלייבן געפאנגען וואו עס גייט נישט קענען דערנאך גיין אין ערגעץ [ווייל עס איז שוין געווען אויף אלע קעסטעלעך וואו עס איז שייך צו גיין]. דאס איז אויף קעסטל נומער 2084 אינעם ספּיירעל.

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

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

‏ובאנו לענין זו, ועיין להלן שם ובכל האשכול שם בכלל.

רעדענדיג פון פונקטן און ליינס איז דא אין מאטעמאטיקס די קיינע דריי פונקטן אין א ליין פראבלעם. דאס פרעגט אז אויב האב איך א סקווער גריד פון קעסטעלעך, למשל א שאך ברעט וואס איז 8x8 קעסטעלעך, וואס איז די מערסטע צאל פון פונקטן וואס איך קען לייגן און אנפולען אינעם גאנצע גריד [א פונקט פאר א קעסטל] אזוי אז עס זאל נישט אויסקומען אז איך קען מאכן א גראדע ליין וואס אנהאלט דריי פונקטן? מ׳ווייסט אז די צאל פונקטן וואס איך קען לייגן אויפ׳ן ברעט אז עס זאל אזוי אויסקומען קען זיכער נישט זיין מער ווי 2 מאל די צאל פון ווי לאנג/ברייט [אין קעסטעלעך] די ברעט איז.

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

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

בנוגע שאך מיני מאטעמאטישע סארט פראבלעמען איז דא די n-מלכּוֺת [קוויִנס] פראבלעם. דאס פרעגט אז אויב האב איך א סקווער שאך ברעט פון א געוויסע צאל קעסטעלעך, וואו דערויף קען איך לייגן די צאל פון שאך מלכּוֺת אזוי אז קיין איינס קען נישט ״נאַקן״ אן אנדערע? ביי א געהעריגע שאך ברעט פון 8x8 קעסטעלעך וויל איך וויסן וואו אויפ׳ן ברעט קען איך לייגן און אויסשטעלן 8 מלכּוֺת אזוי אז קיין איינס קען נישט ״נאַקן״ אן אנדערע?

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

דאס איז אן ענטפערט דערין וואס אויב איך גיי ארומדרייען די ברעט 180° וועט עס זיין די שפיגל אימעדזש [די מלכּוֺת] דערפון:

אלע סארט ברעט צאל ברייטקייטן האבן מעגליכקייטן צו אויסשטעלן דערויף די זעלבע צאל מלכּוֺת אויף אזא אופן חוץ ברעטן וואס זענען לאנג/ברייט 2 אדער 3.

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

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

אז מ׳רעדט פון גרעפס בענין שאַך איז אינטרעסאנט צו דערמאנען דעם רוּק’ס גרעף, וואס אנהאלט אין זיך אסאך אנדערע סארטן גרעפס. דאס איז א גרעף וואו איך רעכען אויס יעדעס רוק/מאָוו די רוּק קען מאכן: יעדעס פלאץ עס קען פארנעמען אלס א נוֺיד און צו וואו עס קען גיין אלס אן עדזש. למשל כזה ביי א געהעריגן שאַך ברעט:

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

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

דערנאך ווי אזוי זיי זענען באהאפטן:

דערנאך נעם איך אוועק די גאנצע אריגינעלע גרעף.

עס קומט אויס אז אויב מאך איך פון א קאָמפּליִט בּייפּארטייט גרעף א ליין גרעף איז עס א רוּק׳ס גרעף.

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

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

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

דאס איז ענליך צום געדאנק פון א דאמינעיטינג סעט ביי גרעפס. דאס איז א סעט פון נוֺידס/פונקטן אינעם גרעף וואס יעדעס נוֺיד/פונקט וואס איז נישט אין דעם דאמינעיטינג סעט איז מקושר צו (כאטש) איינע פון די נוֺידס/פונקטן וואס זענען יא אין דעם דאמינעיטינג סעט. צו טרעפן די דאמינעיטינג נומער, דהיינו די ווייניגסטע צאל פון נוֺידס/פונקטן אינעם גרעף וואס וועלן שאפן אזא סארט דאמינעיטינג סעט איז אויך אן NP קאָמפּליִט פראבלעם. דא איז א משל פון א דאמינעיטינג סעט מיט א דאמינעיטינג נומער פון 2 [די רויטע נוֺידס/פונקטן]:

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

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

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

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

עס קומט סתם אזוי אויס אז די רוּק׳ס גרעף וועט האבן אזויפיל נוֺידס ווי די עריע פונעם ברעט: די צאל פון קעסטעלעך פונעם ברייט טיימס די צאל קעסטעלעך פון די לענג. ווי אויך וועט יעדע נוֺיד זיין באהאפטן צו אזויפיל אנדערע נוֺידס ווי 2 ווייניגער פון די סומע פון וויפיל קעסטעלעך זענען אין די לענג און וויפיל עס זענען אין די ברייט.

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

דערנאך איז אויך דא דערין די עדזשעיסענסי מעיטריקס. דאס איז אויך א סקווער מעיטריקס וואו אין דעם לייג איך אריין די אינפארמאציע פון צו וועלכע נוֺיד א נוֺיד איז באהאפטן. למשל, דעם אויבן-דערמאנטן גרעף וועט האבן א עדזשעיסענסי מעיטריקס כזה: דאס איז ווייל איך שטעל אויס די רוֺיס אין די ברייט אנגעהויבן פון רעפרעזענטירן דעם ערשטן נוֺיד אא״וו ביזן זעקסטן. דאס זעלבע אין די קאלומנס אין די הייך. דערנאך, למשל, ביים קעסטל/פלאץ וואס איז אין די צווייטע רוֺי פון די ערשטע קאלומן וועט באדייטן ווי סאך באהעפטונגען די ערשטע נוֺיד האט צום צווייטן וואס דאס איז 1. וכן הלאה. די איבעריגע פלעצער אינעם מעיטריקס פיל איך אן מיט די נומער 0, דאס איז וויל די נוֺידס זענען נישט באהאפטן צו זיך אליין. אין א פאל וואו די גרעף האט נישט קיין לוּפּס וואו א נוֺיד האט א ליין צו זיך אליין און עס איז נישט א דירעקטעד גרעף, וואו די ליינס גייען פון ארויס פון א נוֺיד דוקא אהין און נישט צוריק, וועט די מעיטריקס זיין סימעטריש. די אייגענוועליוּס פון די מעיטריקס, עיין בהאשכול שציינתי לעיל, ווערן גערופן די ספּעקטרום פונעם גרעף. אויב צוויי גרעפס האבן די זעלבע אייגענוועליוּס פאר זייערע עידזשעסענסי מעיטריסיִס דעמאלטס ווערן זיי גערופן קאָספּעקטראל גרעפס.

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

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

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

ענליך צום עידזשעסענסי מעיטיריקס איז דאס אינסידענס מעיטיריקס. דאס איז ל״ד א סקווער מעיטריקס וויבאלד דא גיב איך די רוֺיס אין די ברייט פאר וויפיל נוֺידס עס זענען דא און די קאלומנס אין די הייך פאר וויפיל ליינס עס זענען דא אינעם גרעף; אנדערש ווי ביים עידזשעסענסי מעיטיריקס זענען סיי די רוֺיס און סיי די קאלומנס געווען פאר די נוֺידס. דערנאך אויב איז די ספעציפישע נוֺיד פון דעם רוֺי באהאפטן צום ספעציפישן ליין פונעם קאלומן גיב איך דאס אן 1 און אז נישט א 0.

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

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

יעצט, ווי דערמאנט אינעם אויבן-צוגעצייכענטן תגובה איבער מעיטריסיִס, איז אן אידענטיטעט מעיטיריקס א מעיטריקס פון א סקווער מעיטריקס [וואו די לענג פון די רוֺיס און קאלומנס זענען די זעלבע] וואס איז די זעלבע סקווער, נאר איך פארטויש עס אז נאר די מעין דייעגאנאל האבן אלע די נומער 1 און די איבעריגע פלעצער האבן א 0.

‏אויבן האבן מיר מסביר געווען ווי אזוי מ׳מאכט א ליין גרעף פון אן אריגינעלע גרעף וואס מ׳האט.

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