Graafiteooria. Graafiteooria on diskreetse matemaatika ulatuslik sõltumatu haru. Kasutatakse arvutivõrkude, torustike projekteerimisel, - esitlus. Graafikud Graafikud ja nende kasutamise esitlus

Piltide, kujunduse ja slaididega esitluse vaatamiseks laadige fail alla ja avage see PowerPointis arvutis.
Esitlusslaidide tekstisisu: Graafikud ja nende rakendamine ülesannete lahendamisel Sisu Mis on graafik Graafi omadusedGraafide tekkeluguKoenigsbergi sildade probleem Graafikute rakendamine Järeldused Mis on graaf Matemaatikas antakse graafi definitsioon järgmiselt: Graafik on mittetühi punktide kogum ja segmentide hulk, mille mõlemad otsad kuuluvad antud punktide hulka.Punkte nimetatakse graafitippudeks ja ühendussirgeteks servadeks. Graafi servad Graafi tipud Järgmine Mis on graaf Graafi ühest tipust väljuvate servade arvu nimetatakse tipu astmeks. Graafi tippu, millel on paaritu aste, nimetatakse paarituks ja paarisastme tippu nimetatakse paaristeks. Paaritu aste Paarisastme sisu Graafi omadused Graafi kõigi tippude astmete summa on paarisarv, mis võrdub kahekordse graafi servade arvuga.Iga graafi paaritute tippude arv on paaris. Graafide omadused Kui n tipuga (n>2) graafis on täpselt kaks tippu sama astmega, siis selles graafis on alati kas täpselt üks 0-astmeline tipp või täpselt üks astme n-1 tipp. täielikul graafil on n tippu, siis on servade arv n(n-1)/2. Graafi omadused Täielik graaf Mittetäielik graaf Graafi omadused Suunatud graaf Suunamata graaf Isomorfsed graafikud Graafikute ajalugu Mõiste "graaf" ilmus esmakordselt ungari matemaatiku D. Koenigi raamatus 1936. aastal, kuigi esialgsed olulisemad graafiteoreemid pärinevad L-st. Euler. Järgmine Graafide tekkelugu Graafiteooriale kui matemaatilisele teadusele pani 1736. aastal aluse Leonard Euler, pidades silmas Königsbergi sildade probleemi. Tänaseks on see ülesanne muutunud klassikaks. Sisu Königsbergi sildade probleem Endine Königsberg (praegu Kaliningrad) asub Pregeli jõe ääres. Linna sees uhub jõgi kahte saart. Rannikult loobiti sildu saartele. Vanad sillad pole säilinud, kuid linna kaart, kus need on kujutatud, on olemas. Järgmine Probleem Königsbergi sildade kohta Königsbergi elanike seas oli levinud probleem: kas iga silla juures on võimalik ületada kõik sillad ja naasta alguspunkti? Järgmine probleem Königsbergi sildade kohta Königsbergi sildadest ei saa antud tingimusi järgides läbida. Kõigi sildade läbimine eeldusel, et peate iga kord külastama ja naasta teekonna alguspunkti, näeb graafiteooria keeles välja nagu ülesanne kujutada graafikut "ühe löögiga". veel Königsbergi sildade probleem Kuna aga sellel joonisel oleval graafikul on neli paaritu tippu, ei saa sellist graafikut "ühe tõmbega" joonistada. Euleri graafik Graafikut, mida saab joonistada ilma pliiatsit paberilt tõstmata, nimetatakse Euleri graafikuks. Lahendades Königsbergi sildade ülesande, sõnastas Euler graafi omadused: Paaritute tippude arv (tipud, kuhu viib paaritu arv servi) peab olema paaris. Ei saa olla graafikut, millel oleks paaritu arv paarituid tippe.Kui kõik graafiku tipud on paaris, siis saab graafiku joonistada ilma pliiatsit paberilt tõstmata ning alustada saab graafiku mis tahes tipust ja lõpetage see samas tipus. Rohkem kui kahe paaritu tipuga graafikut ei saa ühe joonega joonistada. edasi Euleri graaf Kui kõik graafiku tipud on paaris, siis pliiatsit paberilt tõstmata (“ühe tõmbega”), tõmmates igat serva ainult ühe korra, joonista see graafik. Liikumine võib alata mis tahes tipust ja lõppeda samas tipus. edasi Euleri graafik Graafi, millel on ainult kaks paaritut tippu, saab joonistada ilma pliiatsit paberilt tõstmata ning liikumine peab algama ühest neist paaritutest tippudest ja lõppema neist teisest. Euleri graafikust kaugemale Graafi, millel on rohkem kui kaks paaritut tippu, ei saa ühe joonega joonistada. ? Graafikute kasutamine Graafikud lihtsustavad otsuste tegemist matemaatika ülesandeid, mõistatused, leidlikkuse ülesanded. rohkem Graafiku rakendamine Ülesanne:Arkady, Boris. Vladimir, Grigori ja Dmitri surusid koosolekul kätt (kumbki surus kätt ühe korra). Mitu käepigistust kokku tehti? edasi Graafikute rakendamine Lahendus: A D C B D 1 2 3 4 5 6 7 8 9 10 edasi Graafikute rakendamine Osariigis on lennufirmade süsteem korraldatud nii, et mis tahes linna ühendavad lennufirmad mitte rohkem kui kolme teisega ja alates ühestki linnast teise Saate reisida ainult ühe ümberistumisega. Kui suur on maksimaalne linnade arv, mis selles osariigis võib olla? Graafikute rakendamine Olgu mõni linn A. Sealt pääsete mitte rohkem kui kolme linna ja igaühest mitte rohkem kui kahte (A-d arvestamata). Siis pole kokku rohkem kui 1+3+6=10 linna. See tähendab, et linnu kokku ei ole rohkem kui 10. Joonisel olev näide näitab lennufirmade olemasolu. Graafikute rakendus Seal on 3x3 malelaud, kahes ülemises nurgas on kaks musta ratsu, alumises kaks valget (joonis allpool). 16 käiguga pange valged rüütlid mustade asemele ja mustad valgete asemele ning tõestage, et seda pole võimalik teha vähemate liigutustega. Graafikute rakendamine Laiendades graafikut rüütlite võimalike liikumiste kohta ringis, saame, et alguses seisid hobused nii nagu alloleval joonisel: Kokkuvõte Graafikud on imelised matemaatilised objektid, mille abil saab lahendada matemaatilisi, majanduslikke ja loogilisi probleeme. Samuti saab lahendada erinevaid mõistatusi ja lihtsustada ülesannete tingimusi füüsikas, keemias, elektroonikas, automaatikas. Graafikuid kasutatakse kaartide ja sugupuude koostamisel. Matemaatikas on isegi spetsiaalne osa, mida nimetatakse "Graafiteooriaks". sisu

Lisatud failid

Graaf on lõplik hulk tippe V ja servi R, mis ühendavad tipupaare, G=(V,R). Hulkade V ja R kardinaalsused on võrdsed N ja M. Servade hulk võib olla tühi. Tipud on näiteks mis tahes laadi objektid (asulad, arvutivõrgud). Servad on näiteks teed, küljed, jooned.

Servaga ühendatud tippe nimetatakse külgnevateks. Servad, millel on ühine tipp, nimetatakse ka külgnevateks. Serva ja mis tahes selle kahest tipust nimetatakse vahejuhtumiks. Tipu aste on sellele langevate servade arv. Iga graafi saab tasapinnal kujutada tippudele vastavate punktide hulgaga, mis on ühendatud servadele vastavate joontega.

Graafi tee on tippude ja servade jada. Marsruut on suletud (tsükliline), kui algus- ja lõpptipud on samad. Marsruut on lihtne tee, kui kõik tipud ja servad on erinevad. Graaf on ühendatud, kui iga tipp on muudest punktidest kättesaadav. Tipusid, millel ei ole langevaid servi, nimetatakse isoleeritud.

Juhtumimaatriks

Suhtlusnimekirjad

Ribide nimekiri

Graafi ühendatud kaalutud suunamata graafiku külgnemismaatriks

Minimaalse massiga ühenduspuu ehitamine. Kruskali algoritm Graafilt eemaldatakse kõik servad ja saadakse ulatuv alamgraaf, kus kõik tipud on isoleeritud. Iga tipp paigutatakse üksikusse alamhulka. Servad on sorteeritud kaalude kasvavas järjekorras. Servad on järjestikku, nende raskuse kasvavas järjekorras, kaasatud ulatuvasse puusse.

Juhtumeid on 4: 1) kaasatud serva mõlemad tipud kuuluvad üheelemendilistesse alamhulkadesse, seejärel ühendatakse need uueks, ühendatud alamhulgaks; 2) üks tippudest kuulub ühendatud alamhulka, teine ​​aga mitte, siis lülitame teise sellesse alamhulka, kuhu esimene kuulub; 3) mõlemad tipud kuuluvad erinevatesse ühendatud alamhulkadesse, siis ühendame alamhulgad; 4) Mõlemad tipud kuuluvad samasse ühendatud alamhulka, siis jätame selle serva välja.

Näide minimaalse kaaluga ulatuva puu ehitamisest graafile GG Teostatud toimingud Tipude komplekt Graafik 1 Isoleeritud ja tippudega ulatuva alamgraafiku koostamine Saame 5 üksikut alamhulka: (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2Leidke miinimumkaalu serv (R 15) ja lisage see ulatuvale alamgraafile Moodustage ühendatud tippude alamhulk: (V 1,V 5 ). Salvesta alamhulgad (V 2 ), (V 3 ), (V 4 )

Teostatud toimingud Tipude komplektGraaf 3 Ülejäänute hulgast leia miinimumkaalu serv (R 45) ja lisa see ulatuvale alamgraafile Lisa ühendatud alamhulka tipp: (V 1,V 5, V 4 ). Salvestame alamhulgad (V 2 ), (V 3 ) 4Ülejäänute hulgast leiame miinimumkaalu serv (R 23) ja lisame selle ulatuvasse alamgraafi Moodustame uue ühendatud tippude alamhulga: (V 2,V 3 ) . Jätame esimese ühendatud alamhulga (V 1,V 5, V 4 ).

Teostatud toimingud Tipude komplektGraaf 5Ülejäänute hulgast leia miinimumkaalu serv (R 25) ja lisa see ulatuvale alamgraafile Ühenda alamhulgad üheks ühendatud alamhulgaks (V 1,V 5, V 4,V 2, V 3 ). 6Ülejäänud servad ei ole graafikusse kaasatud, sest kõik nende tipud kuuluvad juba samasse ühendatud hulka.

Teostatud toimingud Tipude komplektGraaf 7Saadud on graaf, mis: on ulatuv graaf (kõik tipud on kaasatud); ühendatud (kõiki tippe saab marsruutide abil ühendada); puu (tsükleid pole); on minimaalne kaal. 8Saadud ulatuva puu minimaalne kaal: R 12 +R 25 +R 15 +R 45 = =80 9 Graafi G tsükliline arv on γ=m-n+1=8-5+1=4, mis vastab servade arv mitte puusse.

Muutujate deklareerimine Kaks viieelemendilist täisarvu massiivi X ja Y graafi tipukoordinaatide salvestamiseks Täisarvuline kahemõõtmeline massiiv R graafi servade kaalude salvestamiseks Täisarvulised muutujad i, n ja k tsükliloendurite jaoks Täisarvuline muutuja S puu servade kaalude summa salvestamiseks minimaalse kaaluga

5 graafitipu juhuslike koordinaatide genereerimine (tsükkel üle i). Servakaalude arvutamine. Kaalutud digraafi naabrusmaatriksi väljastamine (pesastatud tsüklid n-s ja k-s) Kaalutud suunamata graafi naabrusmaatriksi väljastamine – pool algmaatriksi elementidest (algväärtus k=n+1) Programmi keha

Tippude arvu nimetatakse
graafiku järjekord.
Servade arvu nimetatakse
graafiku suurus.

Mõned terminid-1

- Olgu R=(a,b) üks graafiku servadest. Siis
tippe a ja b nimetatakse terminalideks
servatipud;
- Sama serva lõpptipud
kutsutakse naabriks;
- Kaht serva nimetatakse külgnevaks, kui neil on
ühine lõpptipp;
- Kaht serva nimetatakse mitmekordseks, kui
nende otsatippude hulgad langevad kokku;
- Serva nimetatakse silmuseks, kui see lõpeb
vaste.

Mõned terminid-2

- tipu V astet tähistatakse kraadiga (V)
nimetatakse servade arvuks, for
mille lõpp on see tipp;
- Tipu nimetatakse isoleeritud, kui
ta pole kellegi jaoks lõpp
ribid;
- Tipu nimetatakse leheks, kui see
on terminal täpselt ühe jaoks
ribid. Lehe q puhul on ilmne, et deg(q)=1.

Näide:

deg(C)=4
H1,…H4 – lehed

Veel üks näide:

Linnad B ja D on isoleeritud
topid; Linnad G ja E on lehed.

Täielik graafik

Graafikut nimetatakse täielikuks, kui see on olemas
kaks tippu on ühendatud servaga.
Mitu serva on täisgraafikul
tellida n?
Täielikul n-järku graafikul on servade arv
võrdub Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Tõestame seda...

Kahe tipuga täielik graaf
sisaldab ühte serva - see on ilmne.
Asendage n=2 valemis n*(n-1)/2
Saame:
n*(n-1)/2=1
Valem on õige, kui n=2

Induktsiooni eeldus

Oletame, et valem on tõene
k tipuga graafik.
Tõestame, et see tähendab
graafiku valemi kehtivus
(k+1) tipuga.

Lisame tervele K tipuga graafile veel ühe tipu.

Ja ühendage see esimese K-ga
tipud...

Saame:

Loeme, mitu ribi meil on...

K*(K-1)/2 + K
=
K*(K+1)/2
Saadakse viimane avaldis,
kui valemis n*(n-1)/2 asemel n
asendus K+1.

Õigluse eeldusest
järgneb lause n=k kohta
avalduse kehtivus kl
n=k+1.
Teoreem on tõestatud.

Täielike graafikute näited

Oluline selgitus

Suunatamata graafi servi määravad paarid on järjestamata (st.
paarid (a,b) ja (b,a) ei erine)

Suunatud graafik

Kui graafiku servad on hulk
järjestatud paarid (st (a,b) ≠ (b,a)),
Väidetavalt on graafik suunatud.
(või digraaf)
Kuidas kontseptsioonile orienteeruda
visuaalne tähendus?
Väga lihtne – ribid on kaasas
nooled (algusest lõpuni)!

Digraafi näide

Segaarv

Segagraaf on kolmik (V, E, A).
V on tippude hulk;
E on suunamata hulk
ribid;
A on suunatud servade hulk.
Muide, suunatud servad
nimetatakse kaaredeks.

Graafiline isomorfism

Olgu kaks graafikut G1 ja G2
Kui on üks-ühele kirjavahetus F
graafikute G1 ja G2 tippude vahel, nii et:
- kui graafis G1 on serv (a,b), siis graafis G2
seal on serv (F(a), F(b))
- kui graafis G2 on serv (p,q), siis graafis G1
seal on serv (F-1 (p), F-1 (q))
siis graafikuid G1 ja G2 nimetatakse isomorfseteks ja
vastavus F on isomorfism.

Selgitamine

Digraafide ja segagraafikute jaoks
kirjavahetus F peab säilitama
kaare orientatsioon.

Isomorfismi vajalik tingimus

Millistel tingimustel elementide vahel
kaks lõplikku hulka
määrata üks-ühele
vastavus?
Siis ja ainult siis arv
elemendid on samad.
Isomorfismi vajalik tingimus
graafikud on sama arv
tipud.

Kas see tingimus on piisav?

Ei, sest tipud võivad olla
ühendatud erineval viisil.

Kas need graafikud on isomorfsed?

Tippude arv on sama -
vajalik tingimus on täidetud...

Püüame luua kirjavahetust F…

See ei ole isomorfism: G1-l on serv (A, D),
ja nende servade kujutised G2-s ei ole ühendatud.

Veel üks katse...

Ja see on isomorfism!

Kas need graafikud on isomorfsed?

Kahjuks ei…

Teoreetilisest vaatenurgast kaks
isomorfne graaf on üks ja seesama
sama objekt (ainult võib-olla erinevalt kujutatud ...)

Teed (ahelad):

Tee (ahel) on jada
tipud:
a1, a2, … , an
kus naabertipud ai ja ai+1
ühendatud ribidega.
Tee pikkus on selle komponentide arv
ribid

Teekonna näited:

(A, D, C) ja (A, B, D) on teed. (A, B, C) ei ole õige tee.

Digraafi tee mõiste säilib
tugevus, kuid vajab täiendamist -
naabruses asuvad tipud
järjestused
a1, a2, … , an
peavad olema ühendatud kaaredega.

Tsüklid

Jalgratas on tee, mille algus- ja
lõputipu vaste.
Tsükli pikkus on selle koostisosade arv
ribid.
Tsüklit nimetatakse lihtsaks, kui selles on servad
ei kordu.
Tsüklit nimetatakse elementaarseks, kui see
lihtne ja selles olevad tipud ei kordu.

Ühenduvuskomponendid

Suvalise graafi tipud võivad olla
jagatud klassidesse nii, et jaoks
sama klassi mis tahes kaks tippu v1
ja v2 on tee v1-st v2-ni
Neid klasse nimetatakse komponentideks
ühenduvus.
Kui graafikul on täpselt üks komponent
ühendus, siis kutsutakse graafik
ühendatud.

Graafikute masinesitus.

Külgnevusmaatriks

- Loendame graafi G tipud
järjestikused täisarvud 1 kuni n;
- Ehitage ruudukujuline laud n×n ja
täitke see nullidega;
- Kui serv on ühenduses
tipud i ja j, siis positsioonides (i,j) ja (j,i)
pane ühikud;
- Saadud tabelit nimetatakse
Graafi G naabrusmaatriks.

Näide

Mõned naabrusmaatriksi ilmsed omadused

- Kui tipp on isoleeritud, siis selle rida ja
veerg on täiesti null;
- ühikute arv reas (veerg)
võrdne vastava astmega
topid;
- Suunamata graafi puhul maatriks
külgnevus on sümmeetriline
põhidiagonaal;
- Silmus vastab seisvale seadmele
põhidiagonaal.

Digraafi üldistus

Digraafi külgnemismaatriks
saab ehitada sarnaselt
viisil, vaid järjekorda arvesse võtma
tipud, saate seda teha:
Kui kaar pärineb tipust j ja
siseneb tippu k, seejärel positsioonis (j,k)
seadke naabrusmaatriksid väärtusele 1 ja sisse
positsioon (k, j) seatud -1.

Esinemismaatriks

- Loendame graafi G tipud
järjestikused täisarvud 1 kuni
n;
- Ehitage ristkülikukujuline laud
n rida ja m veergu (veeru
vastavad graafiku servadele);
- Kui j-ndal serval on klemm
tipp k, siis positsioonis
(k,j) on seatud ühele. Kõik
muudel juhtudel on see nulliks.

Digraafi esinemismaatriks

- Kui j-s kaar pärineb tipust k,
siis on asend (k,j) seatud väärtusele 1;
- Kui j-s kaar siseneb tippu k, siis
asendisse (k,j) pane -1.
- muudel juhtudel asendis (k, j)
jääb nulliks.

Kuna maatriksi veerud
esinemissagedused kirjeldavad servi, siis
iga veerg ei tohi sisaldada
rohkem kui kaks nullist erinevat elementi

Esinemismaatriksi näide

Ribide nimekiri

Teine viis graafiku esitamiseks
– kahemõõtmeline massiiv (paaride loend).
Paaride arv võrdub servade arvuga
(või kaared).

Serva loendi näide

Erinevate esitlusviiside võrdlus

- servade loend on kõige kompaktsem ja
vähima esinemissageduse maatriks
kompaktne;
- Esinemismaatriks on mugav, kui
tsiklite otsimine;
- Lihtsam külgnemismaatriks
ülejäänud on kasutusel.

Graafiku läbimine

Graafi läbimine on selle loendamine.
tipud nii, et iga tipp
korra vaadatud.

Kokkulepe-1

Enne graafiku otsimist
n tipuga looge massiiv Chk
n elemendist ja täitke see
nullid.
Kui Chk[i] = 0, siis on i-s tipp paigal
pole vaadatud.

Kokkulepe-2

Vaatame andmete struktuuri
(hoidla), kus me seda teeme
tippude meeldejätmine protsessi käigus
möödasõit. Salvestusliides
peaks pakkuma kolme funktsiooni:
- tooge top;
- Väljatõmmake top;
- Kontrollige, kas panipaik on tühi;

Kokkulepe-3

Kui tipp j on paigutatud
hoidla, on see märgitud kui
vaadatud (st installitud
Chk[j]=1)

Möödasõidualgoritm-1

1) Võtame suvalise algtipu,
printige see välja ja pange hoiule;

3) võtta laost tipp Z;
4) Kui Z-ga on seotud tipp Q ja mitte
kontrollitud, siis tagastame Z salvestusruumi,
kauplus Q, print Q;
5) Minge 2. sammu juurde

Möödasõidualgoritm-2

1) Võtame suvalise algtipu ja
paneme selle lattu;
2) Kas panipaik on tühi? Kui JAH - lõpp;
3) Võtke laost tipp Z, printige ja
kustutada laost;
4) Panime lattu kõik tipud,
seotud Z-ga ja pole veel märgistatud;
5) Minge 2. sammu juurde

Millised andmestruktuurid sobivad salvestusruumiks?

- virna (PUSH - too; POP - eemalda)
- Järjekord (ENQUE - sisestage; DEQUE -
väljavõte)
Mõlemad struktuurid võimaldavad kontrollida
andmete kättesaadavus.

Algoritm-1 kombineerituna virnaga
nimetatakse sügavuse läbimiseks
Algoritm-2 kombineerituna järjekorraga
nimetatakse laius-esiteks

1 slaid

2 slaidi

Graafiteooria alused ilmusid esimest korda Leonhard Euleri (1707-1783; Šveitsi, Saksa ja Vene matemaatik) töödes, milles ta kirjeldas mõistatuste lahendamist ja matemaatilisi meelelahutusülesandeid. Graafiteooria sai alguse Euleri lahendusest Königsbergi seitsme silla probleemile.

3 slaidi

Juba pikka aega on Königsbergi elanike seas levinud selline mõistatus: kuidas läbida kõik sillad (üle Pregolya jõe), ilma et ükski neist kaks korda läbi tuleks? Paljud püüdsid seda probleemi lahendada nii teoreetiliselt kui ka praktiliselt jalutuskäikude ajal. Kuid keegi pole seda suutnud, kuid keegi pole suutnud tõestada, et see on isegi teoreetiliselt võimatu. Lihtsustatud diagrammil vastavad linnaosad (graafik) joontega sildadele (graafiku kaared) ja linnaosadele joonte ühenduspunktid (graafiku tipud). Arutlemise käigus jõudis Euler järgmistele järeldustele: Kõikidest sildadest on võimatu läbida, ilma et neist ühtegi kaks korda läbi tuleks.

4 slaidi

On 4 veregruppi. Kui vereülekanne toimub ühelt inimeselt teisele, ei sobi kõik rühmad kokku. Aga on teada, et samu gruppe saab inimeselt inimesele üle kanda, s.t. 1-1, 2-2 jne. Ja ka 1. rühma saab üle kanda kõikidesse teistesse rühmadesse, rühmad 2 ja 3 ainult 4. rühma. Ülesanne.

5 slaidi

6 slaidi

Graafikud Graafik on graafilisel kujul esitatud teabemudel. Graaf on servadega ühendatud tippude (sõlmede) kogum. Kuue tipu ja seitsme servaga graaf. Tipusid nimetatakse külgnevateks, kui need on servaga ühendatud.

7 slaidi

Suunatud graafikud – digraafid Igal serval on üks suund. Selliseid servi nimetatakse kaarteks. Suunatud graafik

8 slaidi

Kaalutud graafik See on graafik, mille servadele või kaaredele on määratud arvväärtused (need võivad näidata näiteks linnadevahelist kaugust või transpordikulusid). Graafi kaal võrdub selle servade kaalude summaga. Tabel (seda nimetatakse kaalumaatriksiks) vastab graafikule. 1 2 4 2 3 A B C D E

9 slaidi

Ülesanne vahel asulad Ehitatakse A, B, C, D, E, F teed, mille pikkus on toodud tabelis. (Numbri puudumine tabelis tähendab, et punktide vahel pole otsest teed). Määrake punktide A ja F vahelise lühima tee pikkus (eeldusel, et saate liikuda ainult mööda ehitatud teid). 1) 9 2) 10 3) 11 4) 12

10 slaidi

1. 2. 3. 4. 5. Lühima pikkus marsruut A-B-C-E-F võrdub 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