אונטערשייד צווישן ווערסיעס פון "רוי:גראף (מאטעמאטיק)"
ק (החלפת טקסט – "{{מאטעמאטיק-שטומף}}" ב־"{{שטומף|מאטעמאטיק}}") |
ק (החלפת טקסט – " זיינען" ב־" זענען") |
||
| שורה 7: | שורה 7: | ||
== דעפיניציעס == | == דעפיניציעס == | ||
אַ ''גראַף'' <math>\ G</math> איז אַ סכום פון שפּיצן (<math>\ V</math>, פון ענגליש vertices) און קאַנטן (<math>\ E</math>, edges): <math>\ G=(V,E)</math>. די צאָל פון די שפּיצן איז די ''אָרדענונג'' (order) פונעם גראַף, און די צאָל קאַנטן איז זיין ''גרייס'' (size). די גראַפן | אַ ''גראַף'' <math>\ G</math> איז אַ סכום פון שפּיצן (<math>\ V</math>, פון ענגליש vertices) און קאַנטן (<math>\ E</math>, edges): <math>\ G=(V,E)</math>. די צאָל פון די שפּיצן איז די ''אָרדענונג'' (order) פונעם גראַף, און די צאָל קאַנטן איז זיין ''גרייס'' (size). די גראַפן זענען בדרך כלל באַגרענעצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטלעכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ ''וועג'' (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ''ציקל'' (cycle). | ||
ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן. | ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן. | ||
| שורה 19: | שורה 19: | ||
* קען טראָגן אַן ''עטיקעט''; | * קען טראָגן אַן ''עטיקעט''; | ||
* קען טראָגן אַ ''וואָג'' (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג; | * קען טראָגן אַ ''וואָג'' (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג; | ||
* קען זיין אָדער אַ ''בונד'' (link): ווען פאַרבינדנדיק צוויי פאַרשיידענע שפּיצן; אָדער אַ ''שלייף'' (loop): ווען זיינע ביידע ענדן | * קען זיין אָדער אַ ''בונד'' (link): ווען פאַרבינדנדיק צוויי פאַרשיידענע שפּיצן; אָדער אַ ''שלייף'' (loop): ווען זיינע ביידע ענדן זענען דער זעלביקער שפיץ. | ||
== מינים גראַפן == | == מינים גראַפן == | ||
| שורה 25: | שורה 25: | ||
[[טעקע:TreeNetwork.svg|קליין|אַ בוים]] | [[טעקע:TreeNetwork.svg|קליין|אַ בוים]] | ||
ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין | ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין זענען פאַרבונדענע גראַפן. אַ פאַרבונדענער גראַף וואָס האָט ניט קיין שלייפן איז אַ בוים (tree). להיפּוך צו דעם, אַ גראַף וואָס האָט אַ ציקל איז אַ ציקלישער (cyclic) גראַף. | ||
[[טעקע:Directed_graph,_cyclic.svg|קליין|אַ געצילטער ציקלישער גראַף מיט עטיקעטן פאַר אַלע זיינע שפּיצן]] | [[טעקע:Directed_graph,_cyclic.svg|קליין|אַ געצילטער ציקלישער גראַף מיט עטיקעטן פאַר אַלע זיינע שפּיצן]] | ||
רעוויזיע פון 18:29, 7 דעצעמבער 2022
אין גראַפן־טעאָריע איז אַ גראַף אַ סכום פון אָביעקטן (שפּיצן) מיט בונדן (קאַנטן), וואָס קניפּן זיי צונויף. די אייגנשאַפטן פון גראַפן ווערן געפאָרשט אין ראַמען פון דער טעאָריע פון גראַפן, ווי אויך אין אינפאָרמאַטיק און קאָמפּיוטער פאָרשונג. גראַפן קומען צו נוץ אין כלערליי צווייגן פון וויסנשאַפט פון סטרוקטורירן די דאַטן ביז אילוסטרירן די רעזולטאַטן.
בדרך כלל ווערט אַ גראַף אָפּגעשילדערט ווי אַ גרופּע פּונקטן, וואָס באַצייכענען די אָביעקטן/שפּיצן, און גראָדע אָדער קרומע ליניעס, וואָס גייען פון איין פּונקט צום אַנדערן אָבער מאַכן ציקלען און וואָס באַצייכענען די קאַנטן. אַ ביישפּיל פון אַ גראַף איז אַ מאַפּע פון שטעט מיט וועגן, וואָס פאַרבינדן זיי.
דעפיניציעס
אַ גראַף איז אַ סכום פון שפּיצן (, פון ענגליש vertices) און קאַנטן (, edges): . די צאָל פון די שפּיצן איז די אָרדענונג (order) פונעם גראַף, און די צאָל קאַנטן איז זיין גרייס (size). די גראַפן זענען בדרך כלל באַגרענעצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטלעכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ וועג (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ציקל (cycle).
ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן.
אַ שפּיץ:
- קען טראָגן אַן עטיקעט (label), ד.ה. אַ באַשטימטן סימן אָדער נאָמען, וואָס איז מבחין דעם שפּיץ פון אַנדערע,
- האָט תמיד אַ באַשטימטן גראַד (degree), די צאָל קאַנטן וואָס קומען צוזאַמען אין דעם שפּיץ. באַזירט אויפן גראַד דיפערענצירט מען אַן איזאָלירטן (isolated) שפּיץ וואָס האָט ניט קיין קאַנטן, אַ "בלאַט" (leaf) וואָס בינדט זיך מיט איין איינציקן קאַנט און אינעווייניקסטע שפּיצן מיט מער ווי איין קאַנט.
אַ קאַנט:
- קען האָבן אַ ריכטונג (direction) אָדער זיין אומגעצילט;
- קען טראָגן אַן עטיקעט;
- קען טראָגן אַ וואָג (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג;
- קען זיין אָדער אַ בונד (link): ווען פאַרבינדנדיק צוויי פאַרשיידענע שפּיצן; אָדער אַ שלייף (loop): ווען זיינע ביידע ענדן זענען דער זעלביקער שפיץ.
מינים גראַפן
פאַר פאַרשיידענע אויפגאַבן נוצט מען גראַפן מיט פאַרשיידענע אייגנשאַפטן. די קלאַסיפיקאַציע פון גראַפן איז באַזירט אויף דעם, וואָס פאַראַ עלעמענטן זיי שליסן איין.
ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין זענען פאַרבונדענע גראַפן. אַ פאַרבונדענער גראַף וואָס האָט ניט קיין שלייפן איז אַ בוים (tree). להיפּוך צו דעם, אַ גראַף וואָס האָט אַ ציקל איז אַ ציקלישער (cyclic) גראַף.
ווען די קאַנטן האָבן אַ ריכטונג איז דאָס אַ געצילטער (directed) גראַף, און ווען זיי האָבן וואָגן איז ער אַ געוואָגענער (weighted).
אַ גראַף קען האָבן אַ באַשטימטע באַשרענקונג אויף די גראַדן פון זיינע שפּיצן. אַ פאַרשפּרייטער מין גראַפן לויטן דאָזיקן פּרינציפּ איז, למשל, "בינאַרער" (binary) גראַף, וואָס ביי אים האָבן אַלע אינעווייניקסטע שפּיצן דעם גראַד פון צוויי.
דאס איז נישט קיין המכלול ארטיקל, בלויז עפעס וואס ליגט דא ביז עס וועט ערזעצט ווערן מיט בעסערס. שרייבט עס איבער!