Terekler grafning jeke jaǵdayı retinde

Binar (ekilik) terekler
Ekilik terek - bul hár bir túyinde ko'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:


Terekler ushın bunday matritsalarning ayriqsha qásiyetlerin aytylik ga teń bolǵan terektiń qırları sanınıń qatnası baylanısqan graf ushın minimal, sol sebepli terektiń qońsılıq matritsasi júdá kem (olardıń qatnası hám odaǵı nollar jóneltirilgen terek ushın hám jóneltirilmagan ushın ).
Terektiń insidentlik matritsasi ólshemine iye, yaǵnıy kvadratqa jaqın, hám tiykarınan, eger biz onıń artıqsha ekenligin esapqa alsaq. Haqıyqattan da, hár qanday qatardı alıp tastap, biz aldınǵı sıyaqlı grafni tolıq xarakteristikalaytuǵın kvadrat matritsani alamız.
Tómende keltirilgen insident matritsasining taǵı bir ózgesheligi tómendegishe. Qatar hám ústinlerdi qayta tártiplew arqalı hár qanday terektiń insidentlik matritsasi ústin birliklerinen biri qatarda, ekinshisi tómengi qatarlardan birinde bolǵanda tómengi trapetsiya matritsaga túsiriliwi múmkin..


Pryufer Kodı
Pryufer kodı [1, n] kesmadagi n-2 pútkil sanlar izbe-izligi járdeminde n úshleri menen belgilengen tereklerdi Birma -bir kodlaw usılı. Yaǵnıy, Pryufer kodı - bul tolıq graf hám nomerler izbe-izliginiń barlıq terekleri arasındaǵı biyeksiyasi bolıp tabıladı.
Tereklerdi kodlawdıń bul usılı nemis matematikalıqı Xaynts Pryufer tárepinen 1918-jılda usınıs etilgen. ta úshleri menen berilgen terek ushın Pryufer kodın qurıw algoritmın kórip shıǵayıq. Kirisiwde qırlardıń dizimi berilgen. Eń kishi nomerge iye bolǵan terektiń bargi saylanadı, keyin ol terekten alıp taslanadı hám bul japıraq menen baylanısqan úshlerdiń sanı Pryufer kodına qosıladı.
Bul procedura ret tákirarlanadı. Oxir-aqıbet, terekte tek 2 úsh qaladı hám algoritm bulmanda tawsıladı. Qalǵan eki uchning nomerleri kodqa jazılmaydı.
Sonday etip, málim bir terek ushın Pryufer kodı ta nomerler izbe-izligi bolıp, bul jerde hár bir nomer eń kishi japıraqmenen baylanısqan uchning sanı - bul segment degi nomer [1, n ].

Kodtı alıw algoritmı tómendegishe. Terek túyinleri 1 den n ge shekem bolǵan nomerler menen belgilengen (nomerlengen) bolsın. Biz eń kishi sanlı 1-dárejeli uchni tabamız hám kodqa oǵan qońsılas bolǵan uchning sanın kiritemiz, sonnan keyin tabılǵan uchni (qırı mene birge) óshirip taslaymiz. Alınǵan graf astı menen biz tap sol ámeldi atqaramız, onı tek bir qır qolguncha tákirarlaymız. Kodtı jaratıw procesi 34-suwretde keltirilgen. Keyingi basqıshda óshirilgen uchning sanı ramkaǵa kiritilgen. Berilgen grafda (34-súwret, a) birinshi dárejeli úshler arasında minimal san 2-uchda jaylasqan. Ol 1-uchga qońsılas.

Sol sebepli Pryufer kodınıń birinshi nomeri 1. 2-uchni alıp taslaw nátiyjesinde biz b-suwretde kórsetilgen grafni alamız. Bul grafda dárejesi birge teń bolǵan úshler arasındaǵı minimal san 3 ke teń, sonıń ushın koddıń ekinshi nomeri 4. Formada kórsetilgen graflarga uyqas keletuǵın taǵı ush tákirarlawdı atqarǵannan keyin, c, d, e-su'wretler degi bir qırdan ibarat terekti alamız {7; 6}. Process tamamlandi.
Qabıl etilgen qádemlerdiń nátiyjeleri kestede keltirilgen. Aqırǵı qatarında kerekli kod ámeldegi - 14166.






Pryufer kodı arqalı terekti qayta tiklew. Pryufer kodı menen kórsetilgen tereklerdi payda etiw algoritmı qırlardıń tiyisli dizimin alıwǵa múmkinshilik beredi.
Áyyemgiodni Pryufer kodına kiritilmegen úshler sanınıń artıp baratuǵın izbe-izligi deylik. Kórip shıǵılǵan mısal ushın áyyemgiod 2357 ge teń.
Terek izbe-iz qırlardı qosıp qurıladı. Keyingi qosılǵan shet, birinshisidan baslap, vertikal juplıq menen payda boladı, olardıń nomerleri kod qatarında hám áyyemgiod qatarında birinshi boladı. Sonnan keyin, isletilingen qatar elementleri sızıladı. Eger kod qatarınan shıǵıp ketken nomer odaǵı qalǵan elementler qatarına kiritilmegen bolsa, onıń rejimin buzmasdan áyyemgiod qatarına qosılıwı kerek. Tariyp berińan háreketler kod hám áyyemgiod qatarlarınıń " qaldıqları" menen olardıń birinshisiniń barlıq elementleri óshirilguncha tákirarlanadı.