Teoria grafurilor. Teoria grafurilor este o ramură independentă extinsă a matematicii discrete. Folosit în proiectarea rețelelor de calculatoare, conductelor, - prezentare. Grafice Grafice și prezentarea utilizării lor

Pentru a vizualiza prezentarea cu imagini, design și diapozitive, descărcați fișierul și deschideți-l în PowerPoint pe computerul dvs.
Conținutul text al diapozitivelor prezentării: Grafice și aplicarea lor în rezolvarea problemelor Cuprins Ce este un grafic Proprietățile unui grafic Istoria apariției graficelor Problema podurilor Königsberg Aplicarea graficelor Concluzii Ce este un grafic În matematică, definiția unui grafic este dată astfel: A graficul este un set nevid de puncte și un set de segmente, ambele capete aparțin unui set dat de puncte. Punctele sunt numite vârfuri ale graficului, iar liniile de legătură sunt muchii. Muchiile unui grafic Nodurile unui grafic Următorul Ce este un grafic Numărul de muchii care ies dintr-un vârf al unui grafic se numește gradul vârfului. Un vârf al unui grafic care are un grad impar se numește impar, iar un vârf care are un grad par se numește par. Gradul impar Conținutul gradului par Proprietăți ale graficelor Într-un grafic, suma gradelor tuturor nodurilor sale este un număr par, egal cu dublul numărului de muchii ale graficului grafic cu n vârfuri, unde n≥2, există întotdeauna două vârfuri cu aceleași grade. Proprietățile graficelor Dacă într-un grafic cu n vârfuri (n>2) exact două vârfuri au același grad, atunci în acest grafic există întotdeauna fie exact un vârf de grad 0, fie exact un vârf de grad n-1 graficul are n vârfuri, atunci numărul de muchii va fi egal cu n(n-1)/2. Proprietățile unui grafic Grafic complet Grafic incomplet Proprietăți ale unui grafic Grafic direcționat Grafic nedirecționat Grafice izomorfe Istoria graficelor Termenul „graf” a apărut pentru prima dată în cartea matematicianului maghiar D. Koenig în 1936, deși cele mai importante teoreme inițiale despre grafice merg înapoi la L. Euler. Istoria ulterioară a apariției grafurilor Bazele teoriei grafurilor ca știință matematică au fost puse în 1736 de Leonhard Euler, luând în considerare problema podurilor Königsberg. Astăzi, această sarcină a devenit una clasică. cuprins Problema podurilor Königsberg Fostul Königsberg (acum Kaliningrad) este situat pe râul Pregel. În interiorul orașului, râul spală două insule. Au fost construite poduri de la țărmuri la insule. Podurile vechi nu au supraviețuit, dar a rămas o hartă a orașului, unde sunt reprezentate. Următorul Problema podurilor din Königsberg Următoarea problemă a fost răspândită în rândul locuitorilor din Königsberg: este posibil să treci pe jos peste toate podurile și să te întorci la punctul de plecare, vizitând fiecare pod o singură dată? Problemă suplimentară despre podurile Königsberg Este imposibil să treci peste podurile Königsberg respectând condițiile date. Mergând peste toate podurile, cu condiția să le vizitezi pe fiecare o dată și să te întorci la punctul de plecare al călătoriei, în limbajul teoriei grafurilor arată ca problema descrierii unui grafic cu „o singură lovitură”. în continuare Problema podurilor Königsberg Dar, deoarece graficul din această figură are patru vârfuri impare, este imposibil să se deseneze un astfel de grafic „cu o singură lovitură”. cuprins Graficul Euler Un grafic care poate fi desenat fără a ridica creionul de pe hârtie se numește grafic Euler. Rezolvând problema podurilor Königsberg, Euler a formulat proprietățile graficului: Numărul de vârfuri impare (versuri la care duc un număr impar de muchii) ale graficului trebuie să fie par. Nu poate exista un grafic care are un număr impar de vârfuri impare Dacă toate vârfurile graficului sunt pare, atunci puteți desena un grafic fără a ridica creionul de pe hârtie și puteți începe de la orice vârf al graficului și puteți termina. la același vârf. Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu o singură lovitură. Graficul Euler suplimentar Dacă toate vârfurile graficului sunt pare, atunci puteți desena acest grafic fără a ridica creionul de pe hârtie („cu o singură lovitură”), trecând de-a lungul fiecărei margini o singură dată. Mișcarea poate începe de la orice vârf și se poate termina la același vârf. Graficul Euler suplimentar Un grafic cu doar două vârfuri impare poate fi desenat fără a ridica creionul de pe hârtie, iar mișcarea trebuie să înceapă de la unul dintre aceste vârfuri impare și să se termine la al doilea dintre ele. Graficul Euler suplimentar Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu „o singură lovitură”. ? Utilizarea graficelor Utilizarea graficelor pentru a simplifica soluția probleme matematice, puzzle-uri, sarcini de ingeniozitate. Aplicarea în continuare a graficelor Problemă: Arkady, Boris. Vladimir, Grigori și Dmitri și-au dat mâna când s-au întâlnit (fiecare și-au dat mâna unul cu celălalt o dată). Câte strângeri de mână s-au făcut? Aplicarea în continuare a graficelor Soluție: A D C B D 1 2 3 4 5 6 7 8 9 10 în continuare Aplicarea graficelor În stat, sistemul de transport aerian este conceput astfel încât orice oraș să fie conectat de companii aeriene de cel mult trei alte orașe, iar din orice oraș în oricare altul Puteți călători făcând nu mai mult de o schimbare. Care este numărul maxim de orașe care pot fi în acest stat? Aplicarea graficelor Să existe un anumit oraș A. Din el nu se poate ajunge la mai mult de trei orașe, iar din fiecare dintre ele nu mai mult de două (fără a număra A). Atunci numărul total de orașe nu este mai mare de 1+3+6=10. Aceasta înseamnă că nu există mai mult de 10 orașe în total. Exemplul din figură arată existența companiilor aeriene. O aplicație a graficelor Există o tablă de șah 3x3, în cele două colțuri de sus sunt doi cavaleri negri, în cei de jos sunt doi albi (poza de mai jos). În 16 mișcări, pune cavalerii albi în locul celor negri și cavalerii negri în locul celor albi și demonstrează că este imposibil să faci asta în mai puține mișcări. Aplicarea graficelor După ce am extins graficul posibilelor mișcări ale cavalerilor într-un cerc, constatăm că la început cavalerii stăteau ca în figura de mai jos: Concluzie Graficele sunt obiecte matematice minunate, cu ajutorul cărora puteți rezolva probleme matematice, economice și probleme logice. De asemenea, puteți rezolva diverse puzzle-uri și simplifica condițiile problemelor din fizică, chimie, electronică și automatizare. Graficele sunt folosite la compilarea hărților și a arborilor genealogici. Există chiar și o secțiune specială în matematică numită „Teoria graficelor”. conţinut

Fișiere atașate

Un grafic este o mulțime finită de vârfuri V și o mulțime de muchii R care conectează perechi de vârfuri, G=(V,R). Cardinalitățile mulțimilor V și R sunt egale cu N și M. Mulțimea muchiilor poate fi goală. Exemple de vârfuri sunt obiectele de orice natură (așezări, rețele de calculatoare). Exemple de margini sunt drumurile, laturile, liniile.

Vârfurile conectate printr-o muchie se numesc adiacente. Muchiile care au un vârf comun sunt numite și adiacente. O muchie și oricare dintre cele două vârfuri ale sale se numesc incidente. Gradul unui vârf este numărul de muchii incidente cu acesta. Fiecare grafic poate fi reprezentat pe un plan printr-un set de puncte corespunzătoare vârfurilor, care sunt legate prin linii corespunzătoare muchiilor.

O rută grafică este o succesiune de vârfuri și muchii. Un traseu este închis (ciclic) dacă vârfurile de început și de sfârșit coincid. Un traseu este un lanț simplu dacă toate vârfurile și marginile sunt distincte. Un grafic este conectat dacă fiecare vârf este accesibil de la oricare altul. Nodurile care nu au muchii incidente se numesc izolate.

Matricea incidentelor

Liste de comunicare

Lista de coaste

Matricea de adiacență a unui grafic nedirecționat ponderat conex

Construcția unui arbore întins conectat de greutate minimă. Algoritmul lui Kruskal Toate muchiile sunt eliminate din grafic, rezultând un subgraf care se întinde în care toate vârfurile sunt izolate. Fiecare vârf este plasat într-un subset singleton. Marginile sunt sortate după ponderi crescătoare. Muchiile sunt incluse secvenţial, în ordinea crescătoare a greutăţilor lor, în arborele de întindere.

Există 4 cazuri: 1) ambele vârfuri ale muchiei incluse aparțin unor submulțimi singleton, apoi sunt combinate într-o nouă submulțime conectată; 2) unul dintre vârfuri aparține unei submulțimi conexe, dar celălalt nu, atunci îl includem pe al doilea în submulțimea căreia îi aparține primul; 3) ambele vârfuri aparțin unor submulțimi conectate diferite, apoi combinăm submulțimile; 4) Ambele vârfuri aparțin aceleiași submulțimi conectate, atunci excludem această muchie.

Un exemplu de construire a unui arbore de întindere de greutate minimă pentru un grafic GG Acțiuni de efectuat Set de vârfuri Graficul 1 Să construim un subgraf de întindere cu izolate și vârfuri Vom obține 5 submulțimi cu un singur element: (V 1 ), (V 2 ) ), (V 3 ), (V 4 ), (V 5 ) 2Găsiți o muchie de greutate minimă (R 15) și adăugați-o la subgraful de întindere Formăm o submulțime conexă de vârfuri: (V 1,V 5). Salvăm submulțimile (V 2), (V 3), (V 4)

Acțiuni de efectuat Set de vârfuri Graficul 3 Dintre cele rămase, găsiți muchia greutății minime (R 45) și adăugați-o la subgraful de întindere Adăugați un vârf la submulțimea conexă: (V 1, V 5, V 4 ). Salvăm submulțimile (V 2), (V 3) 4 Dintre cele rămase, găsim muchia greutății minime (R 23) și o adăugăm la subgraful de întindere Formăm o nouă submulțime conexă de vârfuri: (V 2,. V 3). Salvăm primul subset conectat (V 1,V 5, V 4).

Acțiuni de efectuat Mulțimea nodurilor Graficul 5 Dintre cele rămase, găsim muchia greutății minime (R 25) și o adăugăm la subgraful de întindere. Combinăm submulțimile într-o singură submulțime conectată (V 1,V 5, V 4, V 2, V 3). 6Muchiile rămase nu sunt incluse în grafic, deoarece toate vârfurile lor aparțin deja unui set conectat.

Acțiuni de efectuat Set de vârfuri Graficul 7 Se obține un grafic care este: spanning (toate nodurile sunt incluse); conectat (toate vârfurile pot fi conectate prin rute); arbore (fără bucle); are greutate minimă. 8Arborele de întindere rezultat are o greutate minimă: R 12 +R 25 +R 15 +R 45 = =80 9 Numărul ciclic al graficului G este γ=m-n+1=8-5+1=4, ceea ce corespunde la numărul de muchii neincluse într-un arbore.

Declarația variabilelor Două matrice întregi de cinci elemente X și Y pentru a stoca coordonatele vârfurilor graficului O matrice întregă bidimensională R pentru a stoca greutățile muchiilor graficului Variabile întregi i, n și k pentru contoare de bucle O variabilă întreagă S la stocați suma greutăților marginilor arborelui cu greutate minimă

Generarea de coordonate aleatorii a 5 vârfuri ale unui grafic (buclă prin i). Calculul greutăților muchiilor. Ieșirea matricei de adiacență a unui digraf ponderat (bucle imbricate cu n și cu k) Ieșirea matricei de adiacență a unui graf nedirecționat ponderat - jumătate din elementele matricei inițiale (valoarea inițială k=n+1) Corpul programului

Numărul de vârfuri este numit
ordinea graficului.
Numărul de muchii este numit
dimensiunea graficului.

Unii termeni-1

- Fie R=(a,b) una dintre muchiile graficului. Apoi
vârfurile a și b se numesc vârfuri de capăt
vârfurile coastei;
- Vârfurile de capăt ale aceleiași muchii
numiti vecini;
- Două muchii se numesc adiacente dacă au
vârf comun de capăt;
- Două muchii se numesc multiple dacă
seturile vârfurilor lor de capăt coincid;
- O muchie se numește buclă dacă se termină
meci.

Unii termeni-2

- Gradul unui vârf V se notează cu deg(V)
se numeste numarul de muchii pt
dintre care acest vârf este cel terminal;
- Un vârf se numește izolat dacă
nu este punctul final pentru niciunul
coaste;
- Un vârf se numește frunză dacă este
este sfârșitul exact al unuia
coaste Pentru foaia q evident deg(q)=1.

Exemplu:

grade(C)=4
H1,…H4 - Frunze

Un alt exemplu:

Orașele B și D – izolate
blaturi; Orașele G și E sunt frunze.

Graficul complet

Un grafic se numește complet dacă există
două vârfuri sunt conectate printr-o muchie.
Câte muchii are un grafic complet?
comanda n?
Un grafic complet de ordin n are numărul de muchii
este egal cu Cn2=n!/(2*(n-2)!) =n*(n-1)/2

Să demonstrăm...

Grafic complet cu două vârfuri
conține o margine - acest lucru este evident.
Înlocuiți n=2 în formula n*(n-1)/2
Primim:
n*(n-1)/2=1
Formula este corectă când n=2

Ipoteza inducției

Să presupunem că formula este adevărată pentru
grafic cu k vârfuri.
Să demonstrăm că asta implică
validitatea formulei pentru grafic
cu (k+1) vârf.

Să mai adăugăm un vârf la graficul complet cu K vârfuri.

Și conectează-l cu primul K
culmi...

Primim:

Numărăm câte coaste avem...

K*(K-1)/2 + K
=
K*(K+1)/2
Ultima expresie se dovedește a fi
dacă în formula n*(n-1)/2 în loc de n
înlocuiește K+1.

Din asumarea corectitudinii
Urmează afirmațiile pentru n=k
valabilitatea declaraţiei când
n=k+1.
Teorema a fost demonstrată.

Exemple de grafice complete

Lămurire importantă

Perechile care definesc muchiile într-un grafic nedirecționat sunt neordonate (de ex.
perechile (a,b) și (b,a) nu diferă)

Graficul dirijat

Dacă există multe muchii ale graficului
perechi ordonate (adică (a,b) ≠ (b,a)),
Atunci graficul se numește direcționat
(sau digraf)
Cum să dai orientare conceptului
sens vizual?
Foarte simplu - coastele sunt furnizate
săgeți (de la început până la sfârșit)!

Exemplu de digraf

Grafic mixt

Un grafic mixt este un triplu (V, E, A).
V – mulţime de vârfuri;
E – set de neorientate
coaste;
A este un set de muchii orientate.
Apropo, marginile orientate
se numesc arce.

Izomorfismul grafic

Să fie două grafice G1 și G2
Dacă există o corespondență unu-la-unu F
între vârfurile graficelor G1 și G2, astfel încât:
- dacă există o muchie (a,b) în graficul G1, atunci există și o muchie în graficul G2
este o muchie (F(a),F(b))
- dacă există o muchie (p,q) în graficul G2, atunci există și o muchie în graficul G1
există o margine (F-1(p),F-1(q))
atunci graficele G1 și G2 se numesc izomorfe și
corespondența F este un izomorfism.

Clarificare

Pentru digrafe și grafice mixte
conformitatea F trebuie să păstreze
orientarea arcurilor.

Condiții necesare pentru izomorfism

În ce condiții între elemente
două mulţimi finite
stabiliți unu-la-unu
corespondenţă?
Atunci și numai atunci, numărul lor
elementele sunt aceleași.
O condiție necesară pentru izomorfism
numărul de grafice este același
culmi

Este suficientă această condiție?

Nu, pentru că vârfurile pot fi
conectat diferit.

Sunt aceste grafice izomorfe?

Numărul de vârfuri este același -
este indeplinita conditia necesara...

Încercăm să construim o corespondență F...

Acesta nu este un izomorfism: G1 are o muchie (A,D),
iar imaginile acestor margini din G2 nu sunt conectate.

Inca o incercare...

Și acesta este izomorfismul!

Sunt aceste grafice izomorfe?

Vai, nu...

Din punct de vedere teoretic, doi
graficele izomorfe sunt unul și același
același obiect (numai poate reprezentat diferit...)

Căi (lanțuri):

O cale (lanț) este o secvență
vârfuri:
a1, a2, … , an
în care vârfurile învecinate ai şi ai+1
legate prin coaste.
Lungimea unei căi este numărul componentelor sale
coaste

Exemple de căi:

(A, D, C) și (A, B, D) sunt căi. (A, B, C) nu este calea.

Conceptul de cale pentru un digraf păstrează
putere, dar are nevoie de suplimente -
culmi vecine in
secvente
a1, a2, … , an
trebuie conectate prin arce.

Cicluri

Un ciclu este o cale care are o inițială și
vârful final coincide.
Lungimea unui ciclu este numărul componentelor sale
coaste
Un ciclu se numește simplu dacă marginile din el
nu se repetă.
Un ciclu se numește elementar dacă acesta
simplu și vârfurile nu se repetă în el.

Componente de conectivitate

Vârfurile unui graf arbitrar pot fi
împărțit în clase astfel încât pt
oricare două vârfuri ale aceleiași clase v1
și v2 există o cale de la v1 la v2
Aceste clase sunt numite componente
conectivitate.
Dacă graficul are exact o componentă
conexiunea, atunci graficul este numit
coerent.

Reprezentarea automată a graficelor.

Matricea adiacentei

- Să numerotăm vârfurile graficului G
numere întregi consecutive de la 1 la n;
- Să construim un tabel pătrat n×n și
umple-l cu zerouri;
- Dacă există o margine de legătură
vârfurile i și j, apoi în pozițiile (i,j) și (j,i)
vom furniza unitati;
- Tabelul rezultat este numit
matricea de adiacență a graficului G.

Exemplu

Câteva proprietăți evidente ale matricei de adiacență

- Dacă un vârf este izolat, atunci rândul său și
coloana va fi complet zero;
- Numărul de unități pe rând (coloană)
egal cu gradul corespunzător
blaturi;
- Pentru o matrice grafică nedirecționată
adiacența este simetrică în raport cu
diagonala principală;
- O buclă corespunde unei unități pe care se află
diagonala principală.

Generalizare pentru digraf

Matricea de adiacență pentru un digraf
poate fi construit într-un mod similar
fel, dar să ținem cont de ordine
vârfuri, puteți face acest lucru:
Dacă arcul începe de la vârful j și
intră vârful k, apoi în poziția (j,k)
Matricele de adiacență ar trebui să fie setate la 1 și în
poziţia (k,j) set -1.

Matricea de incidenta

- Să numerotăm vârfurile graficului G
numere întregi consecutive de la 1 la
n;
- Să construim o masă dreptunghiulară cu
n rânduri și m coloane (coloane
corespund marginilor graficului);
- Dacă muchia j are un terminal
vârful este vârful k, apoi în poziție
(k,j) este setat la unu. În toate
în alte cazuri este setat la zero.

Matricea de incidență pentru un digraf

- Dacă arcul j-lea provine de la vârful k,
atunci 1 este plasat în poziţia (k,j);
- Dacă arcul j intră pe vârful k, atunci
-1 este plasat în poziţia (k,j).
- In alte cazuri in pozitia (k,j)
rămâne zero.

Deoarece coloanele matricei
incidenta descrie coastele, atunci
fiecare coloană poate să nu conţină
mai mult de două elemente diferite de zero

Exemplu de matrice de incidență

Lista marginilor

Un alt mod de a reprezenta un grafic
– matrice bidimensională (lista de perechi).
Numărul de perechi este egal cu numărul de muchii
(sau arcuri).

Exemplu de listă de margini

Compararea diferitelor metode de prezentare

- Lista de margini este cea mai compactă și
matricea de incidență cel puțin
compact;
- Matricea de incidență este convenabilă când
căutarea ciclurilor;
- Matricea de adiacență este mai simplă
restul în uz.

Traversarea graficului

Parcurgerea unui grafic se numește enumerarea acestuia
vârfuri, astfel încât fiecare vârf
vazut o data.

Acord-1

Înainte de a efectua o căutare pe un grafic
cu n vârfuri vom crea un tablou Chk
de n elemente și umple-l
zerouri.
Dacă Chk[i] = 0, atunci al-lea vârf este încă
nevizuite.

Acordul-2

Să creăm o structură de date
(depozitare) în care vom
amintiți-vă vârfurile din proces
ocolire. Interfață de stocare
ar trebui să ofere trei funcții:
- Aduceți în partea de sus;
- Extrageți vârful;
- Verificați dacă depozitul este gol;

Acord-3

Când vârful j este plasat în
depozitare, este marcat ca
vizualizat (adică instalat
Chk[j]=1)

Bypass algoritm-1

1) Luați un vârf inițial arbitrar,
il tiparim si il punem in depozit;

3) Luați vârful Z din depozit;
4) Dacă există un vârf Q conectat la Z și nu
marcat, apoi returnați Z la stocare,
pune Q în depozit, imprimă Q;
5) Treceți la pasul 2

Bypass algoritm-2

1) Luați un vârf inițial arbitrar și
îl punem în depozit;
2) Depozitul este gol? Dacă DA - sfârșitul;
3) Luați vârful Z din stocare, imprimați și
ștergeți din stocare;
4) Am plasat toate vârfurile în depozit,
Legat de Z și încă nenotat;
5) Treceți la pasul 2

Ce structuri de date sunt potrivite ca stocare?

- Stivă (PUSH – adăugați; POP – eliminați)
- Coadă (ENQUE – enter; DEQUE –
extrage)
Ambele structuri vă permit să verificați
disponibilitatea datelor.

Algoritmul-1 în combinație cu o stivă
numită adâncimea prima traversare
Algoritmul-2 în combinație cu o coadă
numită lățime prima traversare

1 tobogan

2 tobogan

Bazele teoriei grafurilor au apărut pentru prima dată în lucrările lui Leonhard Euler (1707-1783; matematician elvețian, german și rus), în care a descris rezolvarea puzzle-urilor și a problemelor de divertisment matematic. Teoria grafurilor a început cu soluția lui Euler la problema celor șapte poduri din Königsberg.

3 slide

Următoarea ghicitoare a fost de mult obișnuită printre locuitorii din Königsberg: cum să traversați toate podurile (de peste râul Pregolya) fără să treceți de două ori peste niciunul dintre ele? Mulți au încercat să rezolve această problemă atât teoretic, cât și practic în timpul plimbărilor. Dar nimeni nu a reușit, dar nici nu au reușit să demonstreze că era chiar imposibil teoretic. Într-o diagramă simplificată a părților unui oraș (graf), podurile corespund liniilor (arce ale graficului), iar părțile orașului corespund punctelor care leagă liniile (vârfurile graficului). În cursul raționamentului său, Euler a ajuns la următoarele concluzii: Este imposibil să traversezi toate podurile fără a trece de două ori peste oricare dintre ele.

4 slide

Există 4 grupe de sânge. Când sângele este transfuzat de la o persoană la alta, nu toate grupurile sunt compatibile. Dar se știe că grupuri identice pot fi transferate de la persoană la persoană, adică. 1 – 1, 2 – 2 etc. Și, de asemenea, grupul 1 poate fi transfuzat în toate celelalte grupuri, grupurile 2 și 3 numai în grupul 4. Sarcină.

5 slide

6 diapozitiv

Grafice Un grafic este un model informativ prezentat sub formă grafică. Un graf este un set de vârfuri (noduri) conectate prin muchii. Un grafic cu șase vârfuri și șapte muchii. Vârfurile sunt numite adiacente dacă sunt legate printr-o muchie.

7 slide

Grafice direcționate - digrafe Fiecare muchie are o direcție. Astfel de muchii se numesc arce. Graficul dirijat

8 slide

Graficul ponderat Acesta este un grafic căruia îi sunt atribuite muchii sau arce valori numerice (pot indica, de exemplu, distanța dintre orașe sau costul transportului). Greutatea unui grafic este egală cu suma greutăților muchiilor acestuia. Tabelul (numit matrice de greutate) are un grafic corespunzător. 1 2 4 2 3 A B C D E

Slide 9

Problemă între aşezări Au fost construite drumuri A, B, C, D, E, F, a căror lungime este prezentată în tabel. (Lipsa unui număr în tabel înseamnă că nu există un drum direct între puncte). Determinați lungimea celei mai scurte căi dintre punctele A și F (presupunând că călătoria se poate face numai pe drumuri construite). 1) 9 2) 10 3) 11 4) 12

10 diapozitive

1. 2. 3. 4. 5. Lungimea celui mai scurt traseul A-B-C-E-F este egal cu 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2