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

                                     

ⓘ גראף (מאטעמאטיק)

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

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

                                     

1. דעפיניציעס

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

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

אַ שפּיץ:

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

אַ קאַנט:

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

2. מינים גראַפן

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

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

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

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