Графтар мен ағаштар. 2

Графтар мен ағаштар

Граф дегеніміз көптеген нүктелердің ж/е өзара байланысатын сызықтардың жиынтығы. Графтар төбелер мне қабырғалардан тұрады.

Графтардың бірнеше түрі болады: бағдарланған, бағдарланбаған, өлшенген.

Бағдарланған-бұл граф,оның барлық қабырғаларының бағыты бар. Осындай бағытталған қабырғалар доға деп аталады. Мысалы: Мектеп директоры,  завуч, мұғалім, оқушы.

Бағдарланбаған- бұл графтың қабырғаларының бағыты жоқ.

А

В С

Д

Өлшенген граф- бұл граф оның кейбір элементтеріне сандар теңестірілген. Өлшенген графтағы жол ұзындығы. Жолды құрайтын қабырғаларының ұзындығының қосындысы. Төбелер арасындағы қашықтық, бұл ең қысқа жол ұзындығы.                                                     

                                                         А

                                       В                           С

                                                         Д

Ағаштар- бұл бағдарламада кең қолданылатын графтын жеке жағдайы.

Эйлер – бұл граф, онда графтың барлық  қабырғаларынан тұратын цикл бар. Төбелер қайталануы мүмкін.ондағы ізденіп отырған цикл  DBACFBCD болады.

А

                                                 В                                 С

                                                D                                  F    

Галильтон – бұл граф онда барлық төбелерінен тұратын  цикл бар.

 A

 b c

D F