Tema: Izbe-izlikler, oplamlar, terekler, grafikalar hám basqalardı kórsetiw Jobası

Tema: Izbe-izlikler, oplamlar, terekler, grafikalar hám basqalardı kórsetiw
Jobası:
I.Kirisiw
1. Terekler haqqında ulıwma túsinik
2. Binar (ekilik) terekler
3. Pryufer Kodı
4.Grafikalar haqqında túsinik
II.Juwmaqlaw
III.Paydalanılǵan ádebiyatlar
Kirisiw
Terek - bul baylanısqan sheriklik graf, yaǵnıy cikller joq hám úshler juplıǵı arasında bir jol bar. Kirisiwdiń nol dárejesine iye bolǵan úsh terektiń túbiri, shıǵıw nol dárejege iye túyinler bolsa japıraqlar dep ataladı. Jalǵanıw hár qanday úshler juplıǵı ortasında marshrut bar ekenligin ańlatadı, aylanıwshılıq cikller joq ekenligin ańlatadı. Sonday eken, atap aytqanda, sonnan kelip shıǵadıki, terektegi qırlardıń sanı úshler sanınan bir kemrek hám hár qanday úshler jupi arasında bir hám tek bir jol bar.
Orman - júdá kóp terekler bolıp tabıladı. Baǵıtlanǵan (oriyentirlangan) terek - bul tek bir vertikal kirisiw nol dárejesine iye bolǵan (basqa ayqulaqlar oǵan alıp kelmaytuǵın ), basqa úshlerdiń kirisiw dárejesi 1 bolǵan siklik orgraf (cikllerdi óz ishine almaytuǵın jóneltirilgen graf).

1-súwret. Baǵıtlanǵan terek
Terektiń tiykarǵı túsinikleri
Túbir túyini - terektiń eń joqarı túyini (18-suwretdegi 8-túyin ).
Túbir - qálegen tańlap alınǵan úshlerden biri. Japıraq yamasa terminal túyini - áwladı ámeldegi bolmaǵan túyin (18- suwretdegi 1, 4, 7, 13 túyinleri).
Ishki túyin - bul terekke áwladı ámeldegi bolǵan hár qanday túyin hám sol sebepli japıraq túyini emes (18-suwretde 3, 6, 10, 14).
Ushınıń dárejesi - oǵan túsken qırlardıń sanı.
Sentroid - úsh, ol alıp taslanǵanında payda bolǵan jalǵanıw komponentleriniń ólshemleri den aspaydı (túp terektiń yarımı úlkenligi)
Túyin - bul birpara qatań tábiyaat obiektine sáykes keletuǵın eki túrdegi graf elementlerinen birewiniń nusqası. Túyin málim bir maǵlıwmat strukturasınıń yamasa terektiń ózi ma`nisin, jaǵdayın yamasa kórinisin óz ishine alıwı múmkin. Terektiń hár bir túyininde terek astında jaylasqan nol yamasa odan kóp áwlad túyinleri ámeldegi (ádetde, terekler haqıyqıy terekler sıyaqlı joqarıǵa emes, tómenge qaray " ósedi").
Áwladqa iye bolǵan túyin óz áwladına salıstırǵanda ájdad túyin dep ataladı (aldınǵı túyin yamasa úlkenlew túyin). Hár bir túyindiń kópi menen bir ájdadi bar.
Túyindiń biyikligi - bul túyinnen eń tómengi túyinge (shet túyinge) japıraq dep atalatuǵın tómenge túsetuǵın joldıń maksimal uzınlıǵı. Túbir túyininiń biyikligi pútkil terektiń biyikligine teń. Túbir túyinleri. Ájdadları bolmaǵan túyin (eń joqarısı ) túbir túyini dep ataladı. Bul terektegi kóplegen ámeller baslanatuǵın túyin (eger birpara algoritmlar " japıraqlar" den baslanıp, olar túbirge yetguncha dawam etedi). Basqa barlıq túyinlerge túbir túyininen qırlar (yamasa baylanısıwlar ) boylap háreketleniw arqalı erisiw múmkin (rásmiy tariypga kóre, hár bir bunday jol kem ushraytuǵın bolıwı kerek). Diagrammalarda ol ádetde eń joqarı bóleginde suwretlengen. Birpara tereklerde, mısalı, úyinlerde, túbir túyini arnawlı ayrıqshalıqlarǵa iye. Terektegi hár bir túyindi sol túyinnen " ósip atırǵan" kishi terektiń túbir túyini dep esaplaw múmkin.
Terek astı - bul bólek terek retinde kórsetiw etiliwi múmkin bolǵan terekke uqsas maǵlıwmatlar strukturasınıń bir bólegi bolıp tabıladı. T terekiniń hár qanday túyini jáne onıń barlıq násil túyinleri menen birge T terekiniń tómengi tereki esaplanadı. Terek astı hár qanday túyini ushın, yamasa bul kishi terektiń túbir túyinine jol bolıwı kerek, yamasa túyindiń ózi túbir bolıwı kerek. Yaǵnıy, kishi terek túbir túyinine pútkil terek menen baylanısadı hám basqa barlıq túyinler menen terek astı baylanısı tiyisli terek astı túsinigi arqalı anıqlanadı (―toplam astı" termini menen uqsawlıq boyınsha ).
Terek strukturası arasında tártiplengen terekler eń keń tarqalǵan. Binar (Ekilik) qıdırıw tereki - tártiplengen terek turi bolıp tabıladı. Terekler ústinde atqarılatuǵın ulıwma ámeller:
1) jańa elementti málim bir jayǵa kirgiziw;
2) terek astı kirgiziw;
3) terktiń shasın qosıw (sabıw dep ataladı );
4) hár qanday túyin ushın túbir elementin tabıw ;
5) eki ushınıń eń kishi ulıwma ájdadini tabıw ;
6 ) terektiń barlıq elementlerin sanap shıǵıw ;
7) terek putaqsı elementlerin sanap shıǵıw ;
8) izomorfik terek astı qıdırıw ;
9 ) elementti qıdırıw ;
10 ) terektiń shasın alıp taslaw ;
11) terek astın alıp taslaw ;
12) elementti óshiriw.
Tereklerdiń qollanıw tarawları :
1) maǵlıwmatlar iyerarxiyasini basqarıw ;
2) informaciya alıwdı ápiwayılastırıw
3) maǵlıwmatlardıń saralanǵan dizimlerin basqarıw ;
4) arifmetik ańlatpalardı analiz qılıw (anglichan parsing), programmanı optimallastırıw ;
5) hár qıylı vizual effektlerdi alıw ushın cifrlı súwretlerdi jaratıw texnologiyası retinde;
6 ) kóp basqıshlı qarar qabıllaw formalarında (shaxmat).
Binar (ekilik) terekler
Ekilik terek - bul hár bir túyinde kópi menen eki áwlad (bala ) bolǵan maǵlıwmatlardıń iyerarxik dúzilisi. Ádetde, birinshisi ájdad túyini, áwladlar bolsa shep hám oń miyrasxorlar dep ataladı.
Tereklerdi mashinada súwretlew usılları Matritsali kórinis.
Terek, basqa hár qanday graf sıyaqlı, matritsalar járdeminde suwretleniwi múmkin. Mısal jol menende tómende 32- suwretde kórsetilgen tártiplengen terek ushın A - qońsılıq hám B - insidentlik matritsalarini keltirilgen: