Негізгі анықтамалары

Ағаштардың көптеген анықтамалары бар, мыналар солардың тек кейбіреулері ғана.

1. Ағаш - бұл циклсыз байланысқан граф.

2. Ағаш - бұл байланысқан граф, онда N төбе болғанда әрқашан дәл N-1 қабырға бар.

3. Ағаш – бұл граф, олардың кезкелген екі төбе арасында әрқашан тура бір жол бар.

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

 

Кесте 3.4. Ағаштар мысалы
Ағаш	Төбелер	Қабырғалар (доғалар)
Әскер	Жауынгер және офицерлер	Иерархия (командир – бағынышты адам)
Династия (еркек торабы бойынша шежіре)	Монархтар	Қатынас "әкесі - баласы"

 

3.8.сурет. Биіктігі 3 түбірлі ағаш

 

Біз бағдарланған ағаштардың тек бір жеке жағдайын оқимыз және қолданамыз - түбірлі ағаштар (3.12 сурет).

Түбірлі ағаш – бұл бағдарланған ағаш, онда үш түрлі төбені ерекшелеуге болады: түбір, жапырақ (олардың басқа атауы: терминалды төбелер) және қалған төбелер (терминалды емес); сонымен бірге екі міндетті шарт орындалуы тиіс:

1. жапырақтардан бірде бір доға шықпайды; басқа төбелерден қанша болсын сонша доға шығуы мүмкін;

2. түбірге бірде бір доға кірмейді; барлық қалған төбелерге тура бір доғадан кіреді.

Математикада және оған туыс ғылымдарда (соның ішінде теориялық бағдарламалауда) ағаштар басымен төмен «өсуі» дәстүрлі: бұл жәй қажет жағдайда жапырақтарды өсірудің ыңғайлылығы үшін жасалады. Осында түрде, суреттерде ағаш түбірі ең жоғарғы, ал жапырақтар - ең төменгі төбелер болып шығады.

v төбесінің арғы атасы – бұл төбе, одан v төбесіне кіретін доға шығады. v төбесінің ұрпағы - бұл төбе, оған v төбесінен шығатын доға кіреді. Осы терминдерде түбір және жапырақ түсініктеріне басқада анықтамалар беруге болады: түбірдің арғы атасы жоқ, жапырақта ұрпақ жоқ.

Екілік ағаш – бұл түбірлік ағаш, оның әрбір төбесінің екіден аспайтын ұрпағы бар. Осындай жағдайда кейде ағымдық төбе үшін сол жақ ұрпақ және оң жақ ұрпақ туралы айтады.

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

Қорыта келе біз, еркін графтарды ағаштармен тығызырақ байланыстыратын анықтама келтіреміз.

Граф каркасы – бұл, графтан кейбір қабырғалары алынып тасталғаннан соң алынған ағаш (3.13 сурет).

 

 

3.9. сурет. Граф қаңқасы

 

Қаңқа мысалы графтың қандайда бір ерекшеленген төбесінен (ол қаңқа түбірі болады) барлық қалған төбелеріне дейінгі ең қысқа жол (түбірлік) ағашы болып табылады.

Өз бетімен орындауға арналған тапсырмалар:

1. Бағдарланбаған граф құрыңыз және төбелердің біреуінен барлық қалғандарына дейінгі жол ұзындығын есептеңіз.

2. Бағдарланған граф құрыңыз және төбелердің біреуінен барлық қалғандарына дейінгі жол ұзындығын есептеңіз.

Лабораториялық жұмыс №4 (1 сағат)

Тақырыбы: «Компьютердің архитектурасы»

Жұмыстың мақсаты: компьютерде деректердің ұсынуын, компьютердің логикалық элементтерін оқып-меңгеру

Тапсырма:

1. Компьютерлердің архитектурасы тарихымен танысу

2. Компьютердің логикалық элементтерін қарастыру: вентильдер, триггерлер, санауыштар, регистрлер

3. Компьютердегі деректердің ұсынуын оқып-меңгеру

4. Сандық және сандық емес деректердің ұсынуларын, таңбалық ұсынуларды және қосымша кодтағы ұсынуларды меңгеру

5. Деректердің ұсынуына мысалдар келтіру

6. Есеп беруді құру