Зертханалық жұмыс №3

Тақырыбы: Граф типті мәліметтер құрылымдарын ұйымдастыру.

Жалпы мәлімет

Граф дегеніміз – G=<V,E> жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

1250 900

450

Егер е жұптары реттелмеген болса, яғни жолдардағы қозғалыс екі бағытта да жүретін болса, онда граф бағдарланбаған әйтпесе бағдарланған деп аталады. Егер қабырғалардың бір бөлігі бағытталған немесе бағдарланған болса, мұндай графтар аралас графтар деп аталады.

V_1, V_{2, ...,} V_n төбелерінің тізімі жол деп аталады. Мұндағы барлық i үшін 1<=i<=n, V_i,V_i+1 қабырғалары болады.

Бағдарланған графта V_1, V_{2, ...,} V_n төбелердің тізімі.

V₁V₂, V₂ V₃,...,V_n-1 V_n бағытталған доға түрінде болады. Графтардағы жол қарапайым деп аталады, егер графтардың төбелері әртүрлі болса. Жолдың ұзындығы осы жолды құрайтын қабырғалардың санына тең болса.

V_i және V_j төбелері байланған деп аталады егер, осы төбелер үшін V_i+1,V_i+2,.., V_j жолы бар болса. Граф байланысшы граф деп аталады егер, оның кез келген төбелер жұптары үшін оларды қосатын қарапайым жол болса.

Цикл дегеніміз - ұзындығы бірден кем болмайтын бір төбеден басталып сол төбеден аяқталатын қарапайым жол.

Графтардағы тармақ дегеніміз – бұл циклсыз графтар. Графтар өлшенген деп аталады егер, графтың әрбір қабырғасына мәні немесе салмағы жазылса.

Мысалға, салмақ ретінде қалалардың арасындағы арақашықтық немесе қандай да бір жұмыстың жүргізілу уақыты алынады.

Графтарды берудің келесідей әдістері бар:

6. Инцидиенттік матрицасы.

7. Көршілестік матрицасы.

8. Салмақтық матрицасы.

9. Қабырғалар тізімі.

10. Көршілестік тізімі.

Қандай да бір нақтылы есепті шығару үшін қолдану қолайлылығына қарай осы әдістердің кез келгенін пайдалануға болады.

Инцидиенттік матрицасы дегеніміз – размері nm болатын матрица. Мұндағы n-төбелер саны, m-қабырғалар саны. Бағытталған граф үшін х,у қабырғаларына сәйкес келетін баған, у төбесіне сәйкес келетін жолда 1 болады. Ал х төбесіне сәйкес келетін жолда -1 болады, қалған жолдарда 0 болады. Тұзақ жағдайында басқа сан берілуі мүмкін. Яғни, хх болғанда 2 деген сан беріледі. Мысалы,

1 2 4 5

3 6

граф берілген, оның инцидиентті матрицасын жазамыз:

(1,2) (1,3) (3,2) (3,4) (5,4) (5,6) (6,5)

Бағытталған граф үшін х,у қабырғасына сәйкес келетін баған х,у төбесіне сәйкес келетін жолда 1 болады да, қалған жолдарда 0 болады.

2 4

1 6

3. 5

(1,2)(1,3)(1,5)(2,3)(2,5)(3,4)(4,5)(4,6)(5,6)

Графты инцидиентті матрица арқылы беру үшін nМ элемент қажет болады және олардың көбі 0 болады. Инцидиентті матрица ЭЕМ-ға енгізу мен өңдеуге қиын. Сондай-ақ ол қабырғалар туралы тура ақпарат бермейді. Х,у қабырғасы бар ма деген сұраққа жауап беру үшін барлық бағандарды қарап шығу қажет.

Көршілестік матрицасы

Көршілестік матрицасы дегеніміз - өлшемі nМ болатын және егер i-ші төбесі j-ші төбесімен көршілес болса мәні бірге тең болатын, әйтпесе 0-ге тең болатын матрица.

Бағытталмаған графтар үшін х, у қабырғасы у,х қабырғасына тең болады. Сондықтан олар үшін көршілестік матрицасы әрқашан симметриялы. Оларда алдыңғы граф үшін матрица мынадай:

1 2 4 5

3 6

Бағытталмаған граф үшін көршілестік матрица:

2 4

1 6

5

3 5

Көршілес матрица симметриялы болып табылады, сондықтан ЭЕМ-ға енгізіп, өңдеуге қолайлы.

Тапсырмалар: Инцидиенттік матрицасы, көршілестік матрицасы, салмақтық матрицасы, қабырғалар тізімі, көршілестік тізімі әдістерінің кез-келген біреуін қолдана отырып есеп шығару мысалын көрсет.