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

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

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

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

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

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

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

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

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

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

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

למשל, א קעניג׳ס גרעף, והיינו א גרעף וואס רעפּרעזענטירט אלע מעגליכע וועגן א קעניג אויפ׳ן שאך-ברעט קען זיך רוקן כזה:

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

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

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

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

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

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

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

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

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

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

***

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

***

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