Teorija grafova. Teorija grafova je opsežna nezavisna grana diskretne matematike

Korobova Anastasija, student gr. 14-PGS-48D

Danas je važno učiti razne metode, svojstva i nestandardne aplikacije. Razmotrićemo primenu metode "Graf" u stvarnosti oko nas.

Riječ "graf" u matematici označava sliku na kojoj je nacrtano nekoliko tačaka, od kojih su neke povezane linijama. Prije svega, vrijedi reći da grofovi, o kojima će biti riječi, nemaju nikakve veze s aristokratama iz prošlosti. Naši "grafovi" su izvedeni od grčke riječi "grapho", što znači "pišem". Isti korijen u riječima "graf", "biografija".

Prvi rad o teoriji grafova pripada Leonhardu Ojleru, a pojavio se 1736. godine u publikacijama Sankt Peterburške akademije nauka.

Grofovi se sastaju:

u fizici - u izgradnji električnih kola

u hemiji i biologiji - u proučavanju molekula njihovih lanaca

u istoriji - prilikom sastavljanja porodičnog stabla (rodoslova)

u geografiji - u kartiranju

u geometriji - crteži poligona, poliedara, prostornih figura

u ekonomiji - pri rješavanju problema izbora optimalnog puta za tokove teretnog transporta (aviokompanije, metro, željeznice)

Teorija grafova se koristi u rješavanju zadataka matematičkih olimpijada. Grafovi daju vidljivost uslova problema, pojednostavljuju rješenje i otkrivaju sličnost problema.

Sada se u bilo kojoj grani nauke i tehnologije susrećete sa grafovima.

Skinuti:

Pregled:

Za korištenje pregleda prezentacija, kreirajte Google račun (nalog) i prijavite se: https://accounts.google.com

Naslovi slajdova:

Prezentacija iz matematike Tema: "Grafovi" Uradila učenica grupe 14-PGS-48D Korobova Anastasia

Graf je figura koja se sastoji od tačaka i linija koje povezuju ove tačke. Prave se nazivaju ivicama grafa, a tačke se nazivaju vrhovima. Vrhovi iz kojih izlazi paran broj ivica nazivaju se parni, a neparni neparni. Primjeri grafova Teorija grafova

Leonhard Euler (4. april 1707, Bazel, Švajcarska - 7. septembar 1783, Sankt Peterburg, Rusko carstvo) je bio švajcarski, nemački i ruski matematičar koji je dao značajan doprinos razvoju matematike, kao i mehanike, fizike, astronomije i niza primijenjenih nauka. Euler je autor više od 800 radova o matematičkoj analizi, diferencijalnoj geometriji, teoriji brojeva, približnim proračunima, nebeskoj mehanici, matematičkoj fizici, optici, balistici, brodogradnji, teoriji muzike itd.

Figura (graf) koja se može nacrtati bez podizanja olovke sa papira naziva se unikursalna. Obrazac 1. Graf koji ima samo dva neparna vrha može se nacrtati bez podizanja olovke sa papira, a kretanje mora početi od jednog od ovih neparnih vrhova i završiti na drugom od njih. (Sl. A) Uzorak 2 . Graf sa više od dva neparna vrha ne može se nacrtati "jednom potezom" (slika B) Ojlerovi grafovi B A

Pravilnost 3. Ako su svi vrhovi grafa parni, onda ne dižući olovku sa papira, crtajući duž svake ivice samo jednom, nacrtajte ovaj graf. Kretanje može početi iz bilo kojeg vrha i završiti ga na istom vrhu.

Odavno je među stanovnicima Kenigsberga rasprostranjena takva zagonetka: kako proći kroz sve mostove (preko rijeke Pregolya), a da ni jedan od njih ne prođete dvaput? Mnogi su pokušavali da riješe ovaj problem, teoretski i praktično, tokom šetnji Problem Königsberg mostova.

Ovo je graf u kojem neke ivice mogu biti usmjerene, a neke neusmjerene. Mixed Count

Ponderisani grafikon 1 2 4 2 3 A B C D E

Stablo je svaki povezani graf koji nema cikluse. Drveće Drveće

Ovo je (multi)graf čijim rubovima je dodijeljen smjer. Usmjerene ivice se također nazivaju lukovi. Usmjereni graf

Grofovi se sastaju:

Teorija grafova se koristi u rješavanju zadataka matematičkih olimpijada. Grafovi daju vidljivost uslova problema, pojednostavljuju rješenje i otkrivaju sličnost problema. Sada se u bilo kojoj grani nauke i tehnologije susrećete sa grafovima.

Hvala na pažnji!

upoznati studente sa pojmom „Grafa“, osnovnim principima njegove konstrukcije;

formirati sposobnost isticanja odnosa koji povezuju objekte;

razviti pažnju, sposobnost logičkog zaključivanja;

negovati međusobnu pomoć, sposobnost timskog rada

učvršćivanje stečenog znanja u praksi

razvoj pamćenja, pažnje;

razvoj nezavisnosti;

obrazovanje kognitivne aktivnosti.

Oprema:

• kompjuterska klasa opremljena savremenom tehnologijom, video projektor, platno;
• računari sa Windows XP OS, program microsoft office PowerPoint 2003;
• oprema za belu tablu (tema časa, novi pojmovi). Handout.

Plan lekcije.

II. Prezentacija novog materijala. (10 min.)

III. Učvršćivanje materijala. Praktičan rad. (15-20 min.)

IV. Sumiranje lekcije (2 min)

v. Zadaća.

I. Organizacioni momenat. Ažuriranje znanja.

Zdravo! Naša lekcija se zove "Grafovi". Upoznat ćemo se s konceptom „Grafova“, naučiti kako ih prikazati i riješiti probleme na ovu temu.

II Prezentacija novog materijala.

Prvi rad o teoriji grafova pripada Leonhardu Ojleru (1736), iako je termin „graf“ prvi uveo mađarski matematičar Deneš Koenig 1936. godine. Grafovi su se nazivali šemama koje se sastoje od tačaka i segmenata pravih linija ili krivulja koje povezuju ove tačke (primjeri grafova prikazani su na slici 1)

Uz pomoć grafova često je pojednostavljeno rješavanje problema formuliranih u različitim oblastima znanja: u automatizaciji, elektronici, fizici, hemiji itd. Uz pomoć grafova prikazani su dijagrami puteva, gasovoda, toplotnih i elektroenergetskih mreža. . Grafikoni pomažu u rješavanju matematičkih i ekonomskih problema.

Grafikon - (od grčkog grapho - pišem) je sredstvo vizuelnog predstavljanja elemenata objekta veza između njih. Ovo su divni matematički objekti, uz njihovu pomoć možete riješiti mnogo različitih, izvana različitih problema.

Grafikon je neki informacioni model

Graf se sastoji od vrhova ili čvorova povezanih lukovima ili segmentima - ivicama. Linija može biti usmjerena, odnosno imati strelicu (luk), ako nije usmjerena - rub. Dva vrha povezana lukom ili ivicom nazivaju se susjednim.

Primjeri grafikona (Slajd 4, 5, 6)

Zadatak 1 (Slajd 7):

Uspostavljena je svemirska komunikacija između devet planeta Sunčevog sistema. Redovne rakete lete na sljedećim rutama:

Zemlja - Merkur; Pluton - Venera; Zemlja - Pluton; Pluton - Merkur; Merkur - Venera; Uran - Neptun; Neptun - Saturn; Saturn - Jupiter; Jupiter - Mars; Mars - Uran.

Da li je moguće letjeti redovnim raketama od Zemlje do Marsa?

Rješenje: Nacrtajmo dijagram stanja: planete ćemo prikazati tačkama, a putanje raketa linijama.

Sada je odmah jasno da je nemoguće letjeti sa Zemlje na Mars.

Dva vrha povezana lukom ili ivicom nazivaju se susjednim. Svaki rub ili luk je povezan s brojem. Broj može označavati udaljenost između naselja, vrijeme prijelaza s jednog vrha na drugi, itd.

Zadatak 2 (slajd 9) - rješenje je na tabli. Maša je došla u zoološki vrt i želi vidjeti što više životinja. Kojim putem treba da krene? Žuta, crvena, zelena?

Zadatak 3 (11 slajdova) - rješenje je na tabli. Pet fudbalskih timova A, B, C, D, E moraju igrati utakmice međusobno. Već igrao A sa B, C, D; B c A, C, D. koliko je utakmica do sada odigrano? Koliko je ostalo za igru?

Grafički prikaz (Slajd 12)

Graf se može predstaviti kao lista lukova (AB; 7), grafički ili pomoću tabele.

Arc Lists	Grafička forma	tabelarni oblik
(AB; 7),		ALI IN OD ALI 3 IN 4 OD 3 4

III. Objedinjavanje gradiva: učenici se pozivaju da se podijele u grupe i završe zadatke. Radeći u maloj grupi, učenici diskutuju o modelima na osnovu teorijskih znanja stečenih na početku časa. Time se postiže ponavljanje i konsolidacija gradiva.

Zadatak 2 (Slajd 13)

IV. Sažetak lekcije

Ljudi, koje ste nove riječi danas naučili? (Broj, vrh grafa, ivice grafa.)

Šta mogu predstavljati vrhovi grafa? (Gradovi; objekti koji su; povezani.)

Šta znače rubovi grafa (putanja, kretanja, pravci)

Navedite primjer gdje ih u životu možemo sresti?

Kako se prikazuju grafikoni?

V. Domaća zadaća. (Slajd 15)

Broj vrhova se zove
red grafa.
Broj ivica se zove
veličina grafikona.

Neki pojmovi-1

- Neka je R=(a,b) jedna od ivica grafa. Onda
vrhovi a i b nazivaju se terminalni
rubni vrhovi;
- Krajnji vrhovi iste ivice
zove se susjedni;
- Dvije ivice se nazivaju susjednim ako imaju
zajednički krajnji vrh;
- Dvije ivice se nazivaju višestrukim if
skupovi njihovih krajnjih vrhova se poklapaju;
- Rub se zove petlja ako su njegovi krajevi
match.

Neki pojmovi-2

- Stepen vrha V je označen sa deg(V)
se zove broj ivica, za
čiji je vrh ovaj vrh;
- Vrh se naziva izolovanim ako
ona nikome nije kraj
rebra;
- Vrh se zove list ako je
je terminalna za tačno jednu
rebra. Za list q, očigledno je da je deg(q)=1.

primjer:

stepen(C)=4
H1,…H4 - Listovi

Drugi primjer:

Gradovi B i D su izolovani
vrhovi; Gradovi G i E su listovi.

Kompletan graf

Graf se naziva kompletnim ako postoji
dva vrha su povezana ivicom.
Koliko ivica ima kompletan graf
red n?
Potpuni graf reda n ima broj ivica
jednako Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Dokažimo to...

Kompletan graf sa dva vrha
sadrži jednu ivicu - to je očigledno.
Zamijenite n=2 u formulu n*(n-1)/2
Dobijamo:
n*(n-1)/2=1
Formula je tačna za n=2

Pretpostavka indukcije

Pretpostavimo da je formula tačna za
graf sa k vrhova.
Hajde da dokažemo da to implicira
valjanost formule za graf
sa (k+1) vrhom.

Dodajmo još jedan vrh kompletnom grafu sa K vrhova.

I povežite ga sa prvim K
vrhovi...

Dobijamo:

Brojimo koliko smo rebara dobili...

K*(K-1)/2 + K
=
K*(K+1)/2
Dobije se posljednji izraz,
ako je u formuli n*(n-1)/2 umjesto n
zamena K+1.

Iz pretpostavke pravičnosti
slijedi izjava za n=k
valjanost izjave kod
n=k+1.
Teorema je dokazana.

Primjeri potpunih grafikona

Važno pojašnjenje

Parovi koji definiraju rubove u neusmjerenom grafu su neuređeni (tj.
parovi (a,b) i (b,a) se ne razlikuju)

Usmjereni graf

Ako su ivice grafa skup
uređeni parovi (tj. (a,b) ≠ (b,a)),
Za graf se kaže da je usmjeren.
(ili digraf)
Kako dati orijentaciju konceptu
vizuelno značenje?
Vrlo jednostavno - rebra su isporučena
strelice (od početka do kraja)!

Primjer digrafa

Mixed Count

Mješoviti graf je trojka (V, E, A).
V je skup vrhova;
E je skup neusmjerenih
rebra;
A je skup usmjerenih ivica.
Usput, usmjerene ivice
se nazivaju lukovi.

Izomorfizam grafa

Neka postoje dva grafa G1 i G2
Ako postoji korespondencija jedan na jedan F
između vrhova grafova G1 i G2, tako da:
- ako postoji ivica (a,b) u grafu G1, onda u grafu G2
postoji ivica (F(a),F(b))
- ako postoji ivica (p,q) u grafu G2, onda u grafu G1
postoji ivica (F-1(p),F-1(q))
tada se grafovi G1 i G2 nazivaju izomorfnim, i
korespondencija F je izomorfizam.

Pojašnjenje

Za digrafe i mješovite grafove
korespondencija F mora sačuvati
orijentacija luka.

Neophodan uslov za izomorfizam

Pod kojim uslovima između elemenata
dva konačna skupa
postaviti jedan na jedan
udobnost?
Tada i samo tada, broj
elementi su isti.
Neophodan uslov za izomorfizam
grafikoni su isti broj
vrhovi.

Da li je ovaj uslov dovoljan?

Ne, jer vrhovi mogu biti
povezani na različite načine.

Da li su ovi grafovi izomorfni?

Broj vrhova je isti -
ispunjen uslov...

Pokušavamo da izgradimo prepisku F…

Ovo nije izomorfizam: G1 ima ivicu (A, D),
a slike ovih ivica u G2 nisu povezane.

Još jedan pokušaj...

A ovo je izomorfizam!

Da li su ovi grafovi izomorfni?

Nažalost nema…

Sa teorijskog stanovišta, dva
izomorfni graf je jedan te isti
isti predmet (samo, možda, drugačije prikazan...)

Putevi (lanci):

Put (lanac) je niz
vrhovi:
a1, a2, … , an
gdje su susjedni vrhovi ai i ai+1
povezani rebrima.
Dužina putanje je broj njegovih komponenti
rebra

Primjeri staza:

(A, D, C) i (A, B, D) su putevi. (A, B, C) nije način.

Sačuva se pojam putanje za digraf
snagu, ali treba se dopuniti -
susjedni vrhovi u
sekvence
a1, a2, … , an
moraju biti povezani lukovima.

Ciklusi

Ciklus je put čiji početni i
kraj podudaranja vrhova.
Dužina ciklusa je broj njegovih sastojaka
rebra.
Ciklus se naziva jednostavnim ako su u njemu ivice
se ne ponavljaju.
Ciklus se naziva elementarnim ako je
jednostavan i vrhovi u njemu se ne ponavljaju.

Komponente povezivanja

Vrhovi proizvoljnog grafa mogu biti
podijeljen u klase tako da za
bilo koja dva vrha iste klase v1
i v2 postoji put od v1 do v2
Ove klase se nazivaju komponente
povezanost.
Ako graf ima tačno jednu komponentu
vezu, tada se graf poziva
povezan.

Mašinsko predstavljanje grafova.

Matrica susjedstva

- Nabrajamo vrhove grafa G
uzastopni cijeli brojevi od 1 do n;
- Napravi kvadratni sto n×n i
ispunite ga nulama;
- Ako postoji ivica koja se spaja
vrhove i i j, zatim na pozicijama (i,j) i (j,i)
stavite jedinice;
- Rezultirajuća tabela se poziva
matrica susjedstva grafa G.

Primjer

Neka očigledna svojstva matrice susjedstva

- Ako je vrh izolovan, onda njegov red i
stupac će biti potpuno nula;
- Broj jedinica u redu (kolona)
jednak stepenu odgovarajućeg
vrhovi;
- Za neusmjereni graf, matrica
susjedstvo je simetrično
glavna dijagonala;
- Petlja odgovara jedinici koja stoji na njoj
glavna dijagonala.

Generalizacija za digraf

Matrica susjedstva za digraf
može se izgraditi slično
način, ali da se uzme u obzir redosled
vrhova, možete uraditi ovo:
Ako luk dolazi iz vrha j i
ulazi u vrh k, zatim na poziciju (j,k)
postaviti matrice susjedstva na 1, i in
pozicija (k, j) postavljena -1.

Matrica incidencije

- Nabrajamo vrhove grafa G
uzastopni cijeli brojevi od 1 do
n;
- Napravite pravougaoni sto sa
n redova i m kolona (kolona
odgovaraju ivicama grafa);
- Ako j-ti rub ima terminal
vrh k, zatim u poziciji
(k,j) je postavljeno na jedan. U svemu
u drugim slučajevima, postavlja se na nulu.

Matrica incidencije za digraf

- Ako j-ti luk dolazi iz temena k,
tada se pozicija (k,j) postavlja na 1;
- Ako j-ti luk ulazi u vrh k, onda
u poziciju (k,j) staviti -1.
- U ostalim slučajevima, na poziciji (k, j)
ostaje nula.

Budući da su stupci matrice
onda incidenci opisuju ivice
svaka kolona ne smije sadržavati
više od dva elementa različita od nule

Primjer matrice incidencije

Spisak rebara

Drugi način predstavljanja grafa
– dvodimenzionalni niz (lista parova).
Broj parova jednak je broju ivica
(ili lukovi).

Primjer liste rubova

Poređenje različitih metoda prezentacije

- Lista ivica je najkompaktnija, i
matrica najmanje incidencije
kompaktan;
- Matrica incidencije je zgodna kada
traženje ciklusa;
- Lakša matrica susjedstva
ostali su u upotrebi.

Prelazak grafom

Prelazak grafa je njegovo nabrajanje.
vrhova tako da svaki vrh
pogledano jednom.

Sporazum-1

Prije izvođenja pretraživanja grafa
sa n vrhova, kreirajte niz Chk
od n elemenata i popuniti ga
nule.
Ako je Chk[i] = 0, onda i-ti vrh još
nije gledano.

Sporazum-2

Hajde da uzmemo strukturu podataka
(repozitorijum), u kojem ćemo
zapamtite vrhove u procesu
zaobići. Interfejs za pohranu
treba da ima tri funkcije:
- Ponesi vrh;
- Ekstrakt vrh;
- Provjerite da li je skladište prazan;

Sporazum-3

Kada se vrh j stavi u
spremište, označeno je kao
pregledan (tj. instaliran
Chk[j]=1)

Algoritam zaobilaženja-1

1) Uzimamo proizvoljan početni vrh,
odštampajte ga i stavite u skladište;

3) Uzmite vrh Z iz memorije;
4) Ako postoji vrh Q povezan sa Z, a ne
označeno, onda vraćamo Z u skladište,
skladište Q, ispis Q;
5) Idite na korak 2

Algoritam zaobilaženja-2

1) Uzimamo proizvoljan početni vrh i
stavljamo u skladište;
2) Da li je skladište prazan? Ako DA - kraj;
3) Uzmite vrh Z iz skladišta, odštampajte i
izbrisati iz skladišta;
4) Stavljamo u skladište sve vrhove,
povezan sa Z i još nije označen;
5) Idite na korak 2

Koje su strukture podataka prikladne za skladištenje?

- Stack (PUSH - donesi; POP - ukloni)
- Red čekanja (ENQUE - unesite; DEQUE -
ekstrakt)
Obje strukture omogućavaju provjeru
dostupnost podataka.

Algoritam-1 u kombinaciji sa stekom
naziva se prelazak dubine
Algoritam-2 u kombinaciji sa redom čekanja
naziva se u širinu

Graf je konačan skup vrhova V i skup ivica R koji povezuju parove vrhova, G=(V,R). Kardinalnosti skupova V i R jednake su N i M. Skup ivica može biti prazan. Primjeri vrhova su objekti bilo koje prirode (naselja, računarske mreže). Primjeri ivica su putevi, strane, linije.

Vrhovi povezani rubom nazivaju se susjedni. Ivice koje imaju zajednički vrh nazivaju se i susjedne. Ivica i bilo koji od njegova dva vrha nazivaju se incidentni. Stepen vrha je broj ivica koje su mu incidentne. Svaki graf može biti predstavljen u ravni skupom tačaka koje odgovaraju vrhovima, a koje su povezane linijama koje odgovaraju ivicama.

Putanja grafa je niz vrhova i ivica. Ruta je zatvorena (ciklična) ako su početni i krajnji vrh isti. Ruta je jednostavna staza ako su svi vrhovi i rubovi različiti. Graf je povezan ako je svaki vrh dostupan iz bilo kojeg drugog. Vrhovi koji nemaju incidentne ivice nazivaju se izolirani.

Incident Matrix

Komunikacijske liste

Spisak rebara

Matrica susjedstva povezanog ponderiranog neusmjerenog grafa grafa

Konstrukcija rasponskog spojnog stabla minimalne težine. Kruskalov algoritam Sve ivice su uklonjene iz grafa i dobijen je razdvojeni podgraf, gde su svi vrhovi izolovani. Svaki vrh je smješten u singleton podskup. Rubovi su sortirani uzlaznim redoslijedom po težini. Rubovi su sekvencijalno, uzlaznim redoslijedom njihove težine, uključeni u razapinjuće stablo.

Postoje 4 slučaja: 1) oba vrha uključene ivice pripadaju jednoelementnim podskupovima, zatim se kombinuju u novi, povezani podskup; 2) jedan od vrhova pripada povezanom podskupu, a drugi ne, onda uvrštavamo drugi u podskup kome pripada prvi; 3) oba vrha pripadaju različitim povezanim podskupovima, tada kombinujemo podskupove; 4) Oba vrha pripadaju istom povezanom podskupu, tada isključujemo ovu ivicu.

Primjer izgradnje razapinjućeg stabla minimalne težine za graf GG Izvedene radnje Skup vrhova Graf 1 Izgradnja razapinjućeg podgrafa sa izolovanim i vrhovima Dobijamo 5 singleton podskupova: (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2 Pronađi ivicu minimalne težine (R 15) i dodaj je u rasponski podgraf. Formiraj povezan podskup vrhova: (V 1,V 5 ). Sačuvaj podskupove (V 2 ), (V 3 ), (V 4 )

Izvršene radnje Skup vrhovaGrafikon 3 Među preostalima pronađite ivicu minimalne težine (R 45) i dodajte je u rasponski podgraf. Dodajte vrh povezanom podskupu: (V 1,V 5, V 4 ). Sačuvamo podskupove (V 2 ), (V 3 ) 4Među preostalima pronađite ivicu minimalne težine (R 23) i dodajte je u rasponski podgraf Formirajte novi povezani podskup vrhova: (V 2,V 3 ) . Zadržavamo prvi povezani podskup (V 1,V 5, V 4 ).

Izvršene radnje Skup vrhovaGrafikon 5 Među preostalima pronađite ivicu minimalne težine (R 25) i dodajte je rasponskom podgrafu. Kombinirajte podskupove u jedan povezani podskup (V 1,V 5, V 4,V 2,V 3 ). 6Ostali rubovi nisu uključeni u graf, jer svi njihovi vrhovi već pripadaju istom povezanom skupu.

Izvršene radnje Skup vrhovaGraf 7A dobijen je graf koji: je razmjenjivi graf (svi vrhovi su uključeni); povezani (svi vrhovi mogu biti povezani rutama); stablo (bez ciklusa); ima minimalnu težinu. 8Rezultirajuće razapinjuće stablo ima minimalnu težinu: R 12 +R 25 +R 15 +R 45 = =80 9 Ciklični broj grafa G je γ=m-n+1=8-5+1=4, što odgovara broj ivica koje nisu u stablu.

Deklarisanje varijabli Dva niza cjelobrojnih pet elemenata X i Y za pohranjivanje koordinata vrhova grafa Cjelobrojni dvodimenzionalni niz R za pohranjivanje težina rubova grafa Cjelobrojne varijable i, n i k za brojače ciklusa Cjelobrojna varijabla S za pohranjivanje zbroja težina ivica stabla minimalne težine

Generisanje slučajnih koordinata 5 vrhova grafa (petlja preko i). Izračunavanje težine rubova. Izlaz matrice susjedstva ponderiranog digrafa (ugniježđene petlje u n i k) Izlaz matrice susjedstva ponderiranog neusmjerenog grafa – polovina elemenata početne matrice (početna vrijednost k=n+1) Tijelo programa