רוי:גראף (מאטעמאטיק)
אין גראַפן־טעאָריע איז אַ גראַף אַ סכום פון אָביעקטן (שפּיצן) מיט בונדן (קאַנטן), וואָס קניפּן זיי צונויף. די אייגנשאַפטן פון גראַפן ווערן געפאָרשט אין ראַמען פון דער טעאָריע פון גראַפן, ווי אויך אין אינפאָרמאַטיק און קאָמפּיוטער פאָרשונג. גראַפן קומען צו נוץ אין כלערליי צווייגן פון וויסנשאַפט פון סטרוקטורירן די דאַטן ביז אילוסטרירן די רעזולטאַטן.
בדרך כלל ווערט אַ גראַף אָפּגעשילדערט ווי אַ גרופּע פּונקטן, וואָס באַצייכענען די אָביעקטן/שפּיצן, און גראָדע אָדער קרומע ליניעס, וואָס גייען פון איין פּונקט צום אַנדערן אָבער מאַכן ציקלען און וואָס באַצייכענען די קאַנטן. אַ ביישפּיל פון אַ גראַף איז אַ מאַפּע פון שטעט מיט וועגן, וואָס פאַרבינדן זיי.
דעפיניציעס
אַ גראַף איז אַ סכום פון שפּיצן ( , פון ענגליש vertices) און קאַנטן ( , edges): . די צאָל פון די שפּיצן איז די אָרדענונג (order) פונעם גראַף, און די צאָל קאַנטן איז זיין גרייס (size). די גראַפן זענען בדרך כלל באַגרעניצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטליכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ וועג (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ציקל (cycle).
ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן.
אַ שפּיץ:
- קען טראָגן אַן עטיקעט (label), ד.ה. אַ באַשטימטן סימן אָדער נאָמען, וואָס איז מבחין דעם שפּיץ פון אַנדערע,
- האָט תמיד אַ באַשטימטן גראַד (degree), די צאָל קאַנטן וואָס קומען צוזאַמען אין דעם שפּיץ. באַזירט אויפן גראַד דיפערענצירט מען אַן איזאָלירטן (isolated) שפּיץ וואָס האָט ניט קיין קאַנטן, אַ "בלאַט" (leaf) וואָס בינדט זיך מיט איין איינציקן קאַנט און אינעווייניגסטע שפּיצן מיט מער ווי איין קאַנט.
אַ קאַנט:
- קען האָבן אַ ריכטונג (direction) אָדער זיין אומגעצילט;
- קען טראָגן אַן עטיקעט;
- קען טראָגן אַ וואָג (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג;
- קען זיין אָדער אַ בונד (link): ווען פאַרבינדנדיק צוויי פאַרשידענע שפּיצן; אָדער אַ שלייף (loop): ווען זיינע ביידע ענדן זענען דער זעלביקער שפיץ.
מינים גראַפן
פאַר פאַרשידענע אויפגאַבן נוצט מען גראַפן מיט פאַרשידענע אייגנשאַפטן. די קלאַסיפיקאַציע פון גראַפן איז באַזירט אויף דעם, וואָס פאַראַ עלעמענטן זיי שליסן איין.
ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין זענען פאַרבונדענע גראַפן. אַ פאַרבונדענער גראַף וואָס האָט ניט קיין שלייפן איז אַ בוים (tree). להיפּוך צו דעם, אַ גראַף וואָס האָט אַ ציקל איז אַ ציקלישער (cyclic) גראַף.
ווען די קאַנטן האָבן אַ ריכטונג איז דאָס אַ געצילטער (directed) גראַף, און ווען זיי האָבן וואָגן איז ער אַ געוואָגענער (weighted).
אַ גראַף קען האָבן אַ באַשטימטע באַשרענקונג אויף די גראַדן פון זיינע שפּיצן. אַ פאַרשפּרייטער מין גראַפן לויטן דאָזיקן פּרינציפּ איז, למשל, "בינאַרער" (binary) גראַף, וואָס ביי אים האָבן אַלע אינעווייניגסטע שפּיצן דעם גראַד פון צוויי.
דאס איז נישט קיין המכלול ארטיקל, בלויז עפעס וואס ליגט דא ביז עס וועט ערזעצט ווערן מיט בעסערס. שרייבט עס איבער!