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

Korobova Anastazija, učenica gr. 14-PGS-48D

Danas je važno učiti razne metode, svojstva i nestandardne primjene. Razmotrit ćemo primjenu metode „Graf“ u stvarnosti oko nas.

Riječ "graf" u matematici označava sliku na kojoj je nacrtano nekoliko točaka, od kojih su neke povezane linijama. Prije svega, vrijedi reći da grofovi, o kojima će biti riječi, nemaju nikakve veze s aristokratima prošlosti. Naši "grafovi" potječu 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 Euleru, a pojavio se 1736. godine u publikacijama Petrogradske akademije znanosti.

Sastaju se grofovi:

u fizici – u konstrukciji električnih krugova

u kemiji i biologiji – u proučavanju molekula njihovih lanaca

u povijesti - prilikom sastavljanja obiteljskih stabala (rodovnika)

u geografiji – u kartiranju

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

u ekonomiji - pri rješavanju problema odabira optimalnog puta za tokove teretnog prometa (zračne linije, metro, željeznice)

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

Sada se u bilo kojoj grani znanosti i tehnologije susrećete s grafovima.

Preuzimanje datoteka:

Pregled:

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

Naslovi slajdova:

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

Graf je lik koji se sastoji od točaka i pravaca koji povezuju te točke. Pravci se nazivaju rubovi grafa, a točke se nazivaju vrhovi. Vrhovi iz kojih izlazi paran broj bridova nazivaju se parni, a neparni se nazivaju neparni. Primjeri grafova Teorija grafova

Leonhard Euler (4. travnja 1707., Basel, Švicarska - 7. rujna 1783., Sankt Peterburg, Rusko Carstvo) je bio švicarski, njemački i ruski matematičar koji je dao značajan doprinos razvoju matematike, kao i mehanike, fizike, astronomije i niza primijenjenih znanosti. 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 glazbe itd.

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

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

Dugo se među stanovnicima Königsberga raširila takva zagonetka: kako proći kroz sve mostove (preko rijeke Pregolya), a da ne prođete ni jednim od njih dvaput? Mnogi su pokušali riješiti ovaj problem, teoretski i praktično, tijekom šetnji Problem Königsberških mostova.

Ovo je graf u kojem neki bridovi mogu biti usmjereni, a neki neusmjereni. Mješoviti broj

Ponderirani 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. Usmjereni rubovi nazivaju se i lukovi. Usmjereni graf

Sastaju se grofovi:

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

Hvala na pažnji!

upoznati učenike s pojmom „Grafa“, osnovnim načelima njegove konstrukcije;

formirati sposobnost isticanja odnosa koji povezuju objekte;

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

njegovati međusobnu pomoć, sposobnost timskog rada

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

razvoj pamćenja, pažnje;

razvoj samostalnosti;

odgoj kognitivne aktivnosti.

Oprema:

• računalna klasa opremljena suvremenom tehnologijom, video projektorom, platnom;
• računala s OS Windows XP, program Microsoft Office PowerPoint 2003;
• oprema za bijelu ploču (tema sata, novi pojmovi). Priručnik.

Plan učenja.

II. Prezentacija novog materijala. (10 min.)

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

IV. Sumiranje lekcije (2 min)

v. Domaća zadaća.

I. Organizacijski trenutak. 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 Predstavljanje novog materijala.

Prvi rad o teoriji grafova pripada Leonhardu Euleru (1736.), iako je pojam "graf" prvi uveo 1936. mađarski matematičar Denesh Koenig. Grafovi su se nazivali shemama koje se sastoje od točaka i odsječaka ravnih linija ili krivulja koje povezuju te točke (primjeri grafova prikazani su na slici 1.)

Uz pomoć grafova često je pojednostavljeno rješavanje problema formuliranih u različitim područjima znanja: u automatizaciji, elektronici, fizici, kemiji itd. Uz pomoć grafova prikazani su dijagrami cesta, plinovoda, toplinskih i elektroenergetskih mreža. . Grafovi pomažu u rješavanju matematičkih i ekonomskih problema.

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

Graf je neki informacijski model

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

Primjeri grafikona (slajd 4, 5, 6)

Zadatak 1 (Slajd 7):

Uspostavljena je svemirska komunikacija između devet planeta Sunčevog sustava. 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.

Je li moguće letjeti na običnim raketama od Zemlje do Marsa?

Rješenje: Nacrtajmo dijagram uvjeta: planete ćemo prikazati točkama, a rute raketa linijama.

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

Dva vrha povezana lukom ili bridom nazivaju se susjednima. Svaki rub ili luk povezan je 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 ploči. Maša je došla u zoološki vrt i želi vidjeti što više životinja. Kojim putem bi trebala krenuti? Žuta, crvena, zelena?

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

Grafički prikaz (Slajd 12)

Graf se može prikazati kao popis lukova (AB; 7), grafički ili pomoću tablice.

Popisi luka	Grafički oblik	tabelarni oblik
(AB; 7),		A V S A 3 V 4 S 3 4

III. Objedinjavanje gradiva: učenici se pozivaju da se podijele u grupe i završe zadatke. Radeći u maloj skupini učenici raspravljaju o modelima na temelju teorijskih znanja stečenih na početku sata. Time se postiže ponavljanje i učvršćivanje gradiva.

Zadatak 2 (Slajd 13)

IV. Sažetak lekcije

Dečki, koje ste nove riječi danas naučili? (Broj, vrh grafa, rubovi grafa.)

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

Što znače rubovi grafa (putovi, pokreti, smjerovi)

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 bridova se zove
veličina grafikona.

Neki pojmovi-1

- Neka je R=(a,b) jedan od bridova grafa. Zatim
vrhovi a i b nazivaju se terminalni
rubni vrhovi;
- Krajnji vrhovi istog ruba
zove susjedni;
- Dva brida se nazivaju susjednima ako imaju
zajednički krajnji vrh;
- Dva brida nazivaju se višestrukim ako
skupovi njihovih krajnjih vrhova poklapaju se;
- Rub se naziva petljom ako su njegovi krajevi
podudarati se.

Neki pojmovi-2

- Stupanj vrha V označen je s deg(V)
naziva se broj bridova, za
kojemu je ovaj vrh kraj;
- Vrh se naziva izoliranim ako
ona nikome nije kraj
rebra;
- Vrh se naziva listom ako je
je terminalna za točno jednu
rebra. Za list q, očito je da je deg(q)=1.

Primjer:

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

Još jedan primjer:

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

Potpuni graf

Graf se naziva potpunim ako postoji
dva vrha povezana su bridom.
Koliko bridova ima cijeli graf
red n?
Potpuni graf reda n ima broj bridova
jednako Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Dokažimo to...

Potpuni graf s dva vrha
sadrži jedan rub - to je očito.
Zamijenite n=2 u formulu n*(n-1)/2
dobivamo:
n*(n-1)/2=1
Formula je točna za n=2

Pretpostavka indukcije

Pretpostavimo da je formula istinita za
graf s k vrhova.
Dokažimo da to implicira
valjanost formule za graf
s (k+1) vrhom.

Dodajmo još jedan vrh cijelom grafu s K vrhova.

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

dobivamo:

Brojimo koliko smo rebara dobili...

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

Iz pretpostavke pravednosti
slijedi izjava za n=k
valjanost izjave kod
n=k+1.
Teorem je dokazan.

Primjeri potpunih grafikona

Važno pojašnjenje

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

Usmjereni graf

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

Primjer digrafa

Mješoviti broj

Mješoviti graf je trojka (V, E, A).
V je skup vrhova;
E je skup neusmjerenih
rebra;
A je skup usmjerenih bridova.
Usput, usmjereni rubovi
nazivaju se 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 u grafu G1 postoji brid (a,b), onda u grafu G2
postoji rub (F(a),F(b))
- ako u grafu G2 postoji brid (p,q), onda u grafu G1
postoji rub (F-1(p),F-1(q))
tada se grafovi G1 i G2 nazivaju izomorfni, i
korespondencija F je izomorfizam.

Pojašnjenje

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

Neophodan uvjet za izomorfizam

Pod kojim uvjetima između elemenata
dva konačna skupa
postaviti jedan na jedan
sukladnosti?
Tada i samo tada, broj
elementi su isti.
Neophodan uvjet za izomorfizam
grafikoni su isti broj
vrhovima.

Je li ovo stanje dovoljno?

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

Jesu li ovi grafovi izomorfni?

Broj vrhova je isti -
nužni uvjet je ispunjen...

Pokušavamo izgraditi korespondenciju F…

Ovo nije izomorfizam: G1 ima rub (A, D),
a slike tih bridova u G2 nisu povezane.

Još jedan pokušaj...

A ovo je izomorfizam!

Jesu li ovi grafovi izomorfni?

Nažalost ne…

S teoretskog stajališta, dva
izomorfni graf je jedan te isti
isti predmet (samo, možda, drugačije prikazan...)

Putovi (lanci):

Put (lanac) je niz
vrhovi:
a1, a2, … , an
gdje su susjedni vrhovi ai i ai+1
spojena rebrima.
Duljina puta je broj njegovih komponenti
rebra

Primjeri staza:

(A, D, C) i (A, B, D) su putevi. (A, B, C) nije put.

Pojam puta za digraf čuva
snagu, ali treba se nadopuniti -
susjedni vrhovi u
sekvence
a1, a2, … , an
moraju biti povezani lukovima.

Ciklusi

Ciklus je put čiji početni i
podudaranje krajnjeg vrha.
Duljina ciklusa je broj njegovih sastavnica
rebra.
Ciklus se naziva jednostavnim ako su u njemu rubovi
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
Te se klase nazivaju komponentama
povezanosti.
Ako graf ima točno jednu komponentu
vezu, tada se graf zove
povezani.

Strojni prikaz grafova.

Matrica susjedstva

- Nabrajamo vrhove grafa G
uzastopni cijeli brojevi od 1 do n;
- Napravi kvadratni stol n×n i
ispunite ga nulama;
- Ako postoji spojni rub
vrhove i i j, zatim u položaje (i,j) i (j,i)
staviti jedinice;
- Rezultirajuća tablica se zove
matrica susjednosti grafa G.

Primjer

Neka očita svojstva matrice susjedstva

- Ako je vrh izoliran, onda njegov red i
stupac će biti potpuno null;
- Broj jedinica u redu (stupcu)
jednak stupnju odgovarajućeg
vrhovi;
- Za neusmjereni graf, matrica
susjedstvo je simetrično oko
glavna dijagonala;
- Petlja odgovara jedinici na kojoj stoji
glavna dijagonala.

Generalizacija za digraf

Matrica susjednosti za digraf
može se izgraditi slično
način, ali uzeti u obzir redoslijed
vrhova, možete učiniti ovo:
Ako luk dolazi iz vrha j i
ulazi u vrh k, zatim na poziciju (j,k)
postaviti matrice susjednosti na 1, i in
položaj (k, j) skup -1.

Matrica incidencije

- Nabrajamo vrhove grafa G
uzastopni cijeli brojevi od 1 do
n;
- Izgradite pravokutni stol s
n redaka i m stupaca (stupaca
odgovaraju rubovima grafa);
- Ako j-ti rub ima terminal
vrh k, zatim u poziciji
(k,j) postavljeno je na jedan. U svemu
u drugim slučajevima postavlja se na nulu.

Matrica incidencije za digraf

- Ako j-ti luk dolazi iz vrha k,
tada je položaj (k,j) postavljen na 1;
- Ako j-ti luk ulazi u vrh k, tada
u poziciju (k,j) staviti -1.
- U ostalim slučajevima, u položaju (k, j)
ostaje nula.

Budući da su stupci matrice
incidenci opisuju rubove, dakle
svaki stupac ne smije sadržavati
više od dva elementa različita od nule

Primjer matrice incidencije

Popis rebara

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

Primjer popisa rubova

Usporedba različitih metoda prezentacije

- Popis rubova je najkompaktniji, 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
s n vrhova, kreirajte niz Chk
od n elemenata i ispunite ga
nule.
Ako je Chk[i] = 0, onda i-ti vrh više
nije gledano.

Sporazum-2

Uzmimo strukturu podataka
(repozitorijum), u kojem ćemo
zapamtite vrhove u procesu
zaobići. Sučelje za pohranu
treba imati tri funkcije:
- Donesite vrh;
- Ekstrakt vrh;
- Provjerite je li 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,
ispišite ga i stavite u skladište;

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

Algoritam zaobilaženja-2

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

Koje su strukture podataka prikladne za pohranu?

- Slagati (PUSH - donijeti; POP - ukloniti)
- Red čekanja (ENQUE - unesite; DEQUE -
ekstrakt)
Obje strukture omogućuju provjeru
dostupnost podataka.

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

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

Vrhovi povezani bridom nazivaju se susjedni. Rubovi koji imaju zajednički vrh nazivaju se i susjedni. Brid i bilo koji od njegova dva vrha nazivaju se incidentni. Stupanj vrha je broj bridova koji su mu incidentni. Svaki graf može biti predstavljen u ravnini skupom točaka koje odgovaraju vrhovima, a koje su povezane linijama koje odgovaraju bridovima.

Put grafa je niz vrhova i bridova. Ruta je zatvorena (ciklička) ako su početni i završni vrh isti. Ruta je jednostavan put ako su svi vrhovi i bridovi različiti. Graf je povezan ako je svaki vrh dostupan iz bilo kojeg drugog. Vrhovi koji nemaju upadne bridove nazivaju se izolirani.

Matrica incidenata

Popisi za komunikaciju

Popis rebara

Matrica susjednosti povezanog ponderiranog neusmjerenog grafa grafa

Konstrukcija spojnog stabla minimalne težine. Kruskalov algoritam Iz grafa se uklanjaju svi bridovi i dobiva se razmjenjivi podgraf gdje su svi vrhovi izolirani. Svaki vrh je smješten u singleton podskup. Rubovi su poredani uzlaznim redoslijedom težine. Rubovi su uzastopno, uzlaznim redoslijedom njihove težine, uključeni u razmjetno stablo.

Postoje 4 slučaja: 1) oba vrha uključenog brida pripadaju jednoelementnim podskupovima, zatim se kombiniraju u novi, povezani podskup; 2) jedan od vrhova pripada povezanom podskupu, a drugi ne, tada uvrštavamo drugi u podskup kojemu pripada prvi; 3) oba vrha pripadaju različitim povezanim podskupovima, tada kombiniramo podskupove; 4) Oba vrha pripadaju istom povezanom podskupu, tada ovaj brid isključujemo.

Primjer izgradnje razapinjućeg stabla minimalne težine za graf GG Izvršene radnje Skup vrhova Graf 1 Izgradnja razdvojnog podgrafa s izoliranim i vrhovima Dobivamo 5 singleton podskupova: (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2Pronađi rub minimalne težine (R 15) i dodaj ga razapinjućem podgrafu Oblikuj povezani podskup vrhova: (V 1,V 5 ). Spremi podskupove (V 2), (V 3), (V 4)

Izvršene radnje Skup vrhovaGrafikon 3 Među preostalima pronađite rub minimalne težine (R 45) i dodajte ga u rasponski podgraf. Dodajte vrh povezanom podskupu: (V 1,V 5, V 4 ). Spremamo podskupove (V 2 ), (V 3 ) 4Među preostalima pronalazimo rub minimalne težine (R 23) i dodajemo ga rasponskom podgrafu. Formiramo 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 rub minimalne težine (R 25) i dodajte ga 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 dobiven 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 bridova ne u stablo.

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

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