אונטערשייד צווישן ווערסיעס פון "רוי:גראף (מאטעמאטיק)"

יעצטיגע רעוויזיע זינט 13:34, 12 נאוועמבער 2023

אַ גראַף מיט 4 שפּיצן און 5 קאַנטן

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

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

דעפיניציעס

אַ גראַף $\ G$ איז אַ סכום פון שפּיצן ( $\ V$ , פון ענגליש vertices) און קאַנטן ( $\ E$ , edges): $\ G=(V,E)$ . די צאָל פון די שפּיצן איז די אָרדענונג (order) פונעם גראַף, און די צאָל קאַנטן איז זיין גרייס (size). די גראַפן זענען בדרך כלל באַגרעניצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטליכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ וועג (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ציקל (cycle).

ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן.

אַ שפּיץ:

קען טראָגן אַן עטיקעט (label), ד.ה. אַ באַשטימטן סימן אָדער נאָמען, וואָס איז מבחין דעם שפּיץ פון אַנדערע,
האָט תמיד אַ באַשטימטן גראַד (degree), די צאָל קאַנטן וואָס קומען צוזאַמען אין דעם שפּיץ. באַזירט אויפן גראַד דיפערענצירט מען אַן איזאָלירטן (isolated) שפּיץ וואָס האָט ניט קיין קאַנטן, אַ "בלאַט" (leaf) וואָס בינדט זיך מיט איין איינציקן קאַנט און אינעווייניגסטע שפּיצן מיט מער ווי איין קאַנט.

אַ קאַנט:

קען האָבן אַ ריכטונג (direction) אָדער זיין אומגעצילט;
קען טראָגן אַן עטיקעט;
קען טראָגן אַ וואָג (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג;
קען זיין אָדער אַ בונד (link): ווען פאַרבינדנדיק צוויי פאַרשידענע שפּיצן; אָדער אַ שלייף (loop): ווען זיינע ביידע ענדן זענען דער זעלביקער שפיץ.

מינים גראַפן

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

אַ בוים

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

אַ געצילטער ציקלישער גראַף מיט עטיקעטן פאַר אַלע זיינע שפּיצן

ווען די קאַנטן האָבן אַ ריכטונג איז דאָס אַ געצילטער (directed) גראַף, און ווען זיי האָבן וואָגן איז ער אַ געוואָגענער (weighted).

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

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

דער בלאט קומט פון יידיש-וויקיפעדיע.
אריגינעלער בלאט • ערלויבעניש cc-by-sa 3.0.

דאס איז נישט קיין המכלול ארטיקל, בלויז עפעס וואס ליגט דא ביז עס וועט ערזעצט ווערן מיט בעסערס. שרייבט עס איבער!

@@ שורה 1: / שורה 1: @@
+{{דעסקריפציע||ענגליש = nodes and edges connecting pairs of them (mathematical object)|דייטש=Repräsentation einer Folge von Objekten|}}[[טעקע:Directed graph.svg|קליין|אַ גראַף מיט 4 שפּיצן און 5 קאַנטן]]
-[[טעקע:Directed graph.svg|קליין|אַ גראַף מיט 4 שפּיצן און 5 קאַנטן]]
 אין [[גראַפן־טעאָריע]] איז אַ '''גראַף''' אַ [[סכום (מאטעמאטיק)|סכום]] פון אָביעקטן (שפּיצן) מיט בונדן (קאַנטן), וואָס קניפּן זיי צונויף. די אייגנשאַפטן פון גראַפן ווערן געפאָרשט אין ראַמען פון דער טעאָריע פון גראַפן, ווי אויך אין [[אינפאָרמאַטיק]] און [[קאָמפּיוטער פאָרשונג]]. גראַפן קומען צו נוץ אין כלערליי צווייגן פון [[וויסנשאַפט]] פון סטרוקטורירן די דאַטן ביז אילוסטרירן די רעזולטאַטן.
@@ שורה 7: / שורה 6: @@
 == דעפיניציעס ==
-אַ ''גראַף'' <math>\ G</math> איז אַ סכום פון שפּיצן (<math>\ V</math>, פון ענגליש vertices) און קאַנטן (<math>\ E</math>, edges): <math>\ G=(V,E)</math>. די צאָל פון די שפּיצן איז די ''אָרדענונג'' (order) פונעם גראַף, און די צאָל קאַנטן איז זיין ''גרייס'' (size). די גראַפן זיינען בדרך כלל באַגרענעצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטלעכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ ''וועג'' (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ''ציקל'' (cycle).
+אַ ''גראַף'' <math>\ G</math> איז אַ סכום פון שפּיצן (<math>\ V</math>, פון ענגליש vertices) און קאַנטן (<math>\ E</math>, edges): <math>\ G=(V,E)</math>. די צאָל פון די שפּיצן איז די ''אָרדענונג'' (order) פונעם גראַף, און די צאָל קאַנטן איז זיין ''גרייס'' (size). די גראַפן זענען בדרך כלל באַגרעניצט, ד.ה. האָבן אַ באַשטימטע צאָל שפּיצן און קאַנטן. אין עטליכע טיפּן גראַפן קען מען פאַר יעדער אָדער אייניקער פּאָר שפּיצן געפינען אַ ''וועג'' (path): אַ גרופּע קאַנטן וואָס ליגן צווישן זיי. אַ וועג, וואָס גייט אַרויס פון איין שפּיץ און ענדיקט זיך אין דעם זעלביקן שפּיץ הייסט אַ ''ציקל'' (cycle).
 ביידע: אַ שפּיץ און אַ קאַנט, קענען כאַראַקטעריזירט ווערן מיט אַ ריי אייגנשאַפטן.
@@ שורה 13: / שורה 12: @@
 אַ שפּיץ:
 * קען טראָגן אַן ''עטיקעט'' (label), ד.ה. אַ באַשטימטן סימן אָדער נאָמען, וואָס איז מבחין דעם שפּיץ פון אַנדערע,
-* האָט תמיד אַ באַשטימטן ''גראַד'' (degree), די צאָל קאַנטן וואָס קומען צוזאַמען אין דעם שפּיץ. באַזירט אויפן גראַד דיפערענצירט מען אַן איזאָלירטן (isolated) שפּיץ וואָס האָט ניט קיין קאַנטן, אַ "בלאַט" (leaf) וואָס בינדט זיך מיט איין איינציקן קאַנט און אינעווייניקסטע שפּיצן מיט מער ווי איין קאַנט.
+* האָט תמיד אַ באַשטימטן ''גראַד'' (degree), די צאָל קאַנטן וואָס קומען צוזאַמען אין דעם שפּיץ. באַזירט אויפן גראַד דיפערענצירט מען אַן איזאָלירטן (isolated) שפּיץ וואָס האָט ניט קיין קאַנטן, אַ "בלאַט" (leaf) וואָס בינדט זיך מיט איין איינציקן קאַנט און אינעווייניגסטע שפּיצן מיט מער ווי איין קאַנט.
 אַ קאַנט:
@@ שורה 19: / שורה 18: @@
 * קען טראָגן אַן ''עטיקעט'';
 * קען טראָגן אַ ''וואָג'' (weight), ד.ה. אַ באַשטימטע צאָליקע ווערט, ווי למשל לענג;
-* קען זיין אָדער אַ ''בונד'' (link): ווען פאַרבינדנדיק צוויי פאַרשיידענע שפּיצן; אָדער אַ ''שלייף'' (loop): ווען זיינע ביידע ענדן זיינען דער זעלביקער שפיץ.
+* קען זיין אָדער אַ ''בונד'' (link): ווען פאַרבינדנדיק צוויי פאַרשידענע שפּיצן; אָדער אַ ''שלייף'' (loop): ווען זיינע ביידע ענדן זענען דער זעלביקער שפיץ.
 == מינים גראַפן ==
-פאַר פאַרשיידענע אויפגאַבן נוצט מען גראַפן מיט פאַרשיידענע אייגנשאַפטן. די קלאַסיפיקאַציע פון גראַפן איז באַזירט אויף דעם, וואָס פאַראַ עלעמענטן זיי שליסן איין.
+פאַר פאַרשידענע אויפגאַבן נוצט מען גראַפן מיט פאַרשידענע אייגנשאַפטן. די קלאַסיפיקאַציע פון גראַפן איז באַזירט אויף דעם, וואָס פאַראַ עלעמענטן זיי שליסן איין.
 [[טעקע:TreeNetwork.svg|קליין|אַ בוים]]
-ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין זיינען פאַרבונדענע גראַפן. אַ פאַרבונדענער גראַף וואָס האָט ניט קיין שלייפן איז אַ בוים (tree). להיפּוך צו דעם, אַ גראַף וואָס האָט אַ ציקל איז אַ ציקלישער (cyclic) גראַף.
+ווען פאַר יעדער פּאָר שפּיצן איז דאָ אַ וועג, איז דאָס אַ פאַרבונדענער (connected) גראַף, ווען ניט — שליסט ער איין צוויי אָדער מער קאָמפּאָנענטן, וואָס אַליין זענען פאַרבונדענע גראַפן. אַ פאַרבונדענער גראַף וואָס האָט ניט קיין שלייפן איז אַ בוים (tree). להיפּוך צו דעם, אַ גראַף וואָס האָט אַ ציקל איז אַ ציקלישער (cyclic) גראַף.
 [[טעקע:Directed_graph,_cyclic.svg|קליין|אַ געצילטער ציקלישער גראַף מיט עטיקעטן פאַר אַלע זיינע שפּיצן]]
 ווען די קאַנטן האָבן אַ ריכטונג איז דאָס אַ געצילטער (directed) גראַף, און ווען זיי האָבן וואָגן איז ער אַ געוואָגענער (weighted).
-אַ גראַף קען האָבן אַ באַשטימטע באַשרענקונג אויף די גראַדן פון זיינע שפּיצן. אַ פאַרשפּרייטער מין גראַפן לויטן דאָזיקן פּרינציפּ איז, למשל, "בינאַרער" (binary) גראַף, וואָס ביי אים האָבן אַלע אינעווייניקסטע שפּיצן דעם גראַד פון צוויי.
+אַ גראַף קען האָבן אַ באַשטימטע באַשרענקונג אויף די גראַדן פון זיינע שפּיצן. אַ פאַרשפּרייטער מין גראַפן לויטן דאָזיקן פּרינציפּ איז, למשל, "בינאַרער" (binary) גראַף, וואָס ביי אים האָבן אַלע אינעווייניגסטע שפּיצן דעם גראַד פון צוויי.
 {{שטומף|מאטעמאטיק}}
 [[קאטעגאריע:מאטעמאטיק]]
-[[קאטעגאריע:אומבאקוקט]]
+[[קאטעגאריע:אויף יידיש]]
-[[קאטעגאריע:אויף יידיש]]
+[[קאַטעגאָריע:וויכטיגע ארטיקלען]]
 {{קרד/ויקי/יידיש}}
+[[he:גרף (תורת הגרפים)]]

אונטערשייד צווישן ווערסיעס פון "רוי:גראף (מאטעמאטיק)"

יעצטיגע רעוויזיע זינט 13:34, 12 נאוועמבער 2023

דעפיניציעס

מינים גראַפן

נאוויגאציע מעניו

זוכן