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

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

 

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

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

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

       

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

А

В С

Д

  

 

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

                                                         А

                               

                                       В                           С

                                                                

                                                                

                                                            

                                                         Д

 

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

 

 

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

 

А

 

                                                 В                                 С

 

 

 

                                                D                                  F    

 

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

 

 A

 b c

 

 

D F