Sarcini de teoria grafurilor în Word. Teoria grafurilor

Instituție de învățământ bugetar municipal

Școala secundară Oktyabrskaya

Lucrare de cercetare în matematică

„Teoria graficelor în rezolvarea diverselor

tipuri de sarcini"

Efectuat:
elev de clasa a VII-a
Makshun Alexey

supraveghetor:

profesor de matematică

Moshkovo 2011

1. Introducere.

1. 1. Relevanța temei alese.

Într-o zi am dat peste o problemă descrisă de Lewis Carroll. „Trei oameni locuiau în trei case, nu departe de ei erau trei fântâni: una cu apă, alta cu ulei, iar cea de-a treia cu dulceață și mergeau până la ei pe cărările arătate în imagine. Într-o zi acești oameni s-au certat și au decis să tragă poteci de la casele lor până la fântâni, pentru ca aceste poteci să nu se intersecteze.”

Am încercat să rezolv această problemă, dar nimic nu a funcționat. După aceea, am apelat la profesorul meu și mi-au explicat că aș putea rezolva această problemă doar studiind teoria grafurilor. Dar înainte de a găsi răspunsul la întrebarea mea, am văzut că teoria grafurilor ajută la simplificarea soluției multor probleme. Graficele m-au interesat datorită capacității lor de a ajuta la rezolvarea diferitelor puzzle-uri, probleme matematice și logice.

Ţintă:

Arătați aplicarea teoriei grafurilor pentru rezolvarea diferitelor tipuri de probleme.

Sarcini:

· Studiază elemente de teorie a graficelor pentru a rezolva probleme care mă interesează.

· Analizați soluții la diferite tipuri de probleme.

· Îmbunătățirea culturii matematice.

1.2. Istoria apariției teoriei grafurilor.

Data nașterii teoriei grafurilor este considerată a fi 1736, când Leonhard Euler a rezolvat problema podurilor Königsberg. Ramurile râului Pregel, pe malurile cărora se află orașul Königsberg, formau două insule. În această epocă, cele patru secțiuni de pământ formate (malul drept și stânga și două insule) erau conectate prin șapte poduri, așa cum se arată în figură. Oamenii, plimbându-se prin oraș, au încercat să creeze un traseu astfel încât să treacă fiecare pod exact o dată. Ei nu au reușit să facă acest lucru, dar Euler a dovedit că acest lucru este fundamental imposibil. Termenul „graf” a fost introdus pentru prima dată în 1936 de către matematicianul maghiar Dénes König. Teoria grafurilor a fost dezvoltată pe scară largă începând cu anii 50 ai secolului XX în legătură cu apariția ciberneticii și dezvoltarea tehnologiei computerelor.

Cuvântul „graf” în matematică înseamnă o imagine cu mai multe puncte desenate, dintre care unele sunt conectate prin linii. Ele sunt legate de titlul nobiliar „conte” printr-o origine comună din cuvântul latin „graphio” - scriu eu.

Exemplele de grafice includ diagrame ale companiilor aeriene, metrourilor, drumurilor, circuitelor electrice și desenelor poligoanelor.

Schema metroului Novosibirsk.

Folosește conții și noblețe. De exemplu, într-un arbore genealogic, vârfurile sunt membri ai clanului, iar segmentele care îi leagă sunt relații de rudenie.

Arbore genealogic.

Cu ajutorul graficelor se simplifică adesea rezolvarea problemelor formulate în diverse domenii ale cunoașterii: în automatizare, electronică, fizică, chimie. Graficele ajută la rezolvarea problemelor matematice și economice.

2. Partea principală.

2.1. Concepte de bază ale teoriei grafurilor. Aplicarea sa în rezolvarea problemelor logice.

În matematică, definiția unui grafic este dată după cum urmează:

Un grafic este un set finit de puncte, dintre care unele sunt conectate prin linii. Punctele se numesc vârfuri ale graficului, iar liniile de legătură se numesc muchii.

Se numește o diagramă grafică constând din vârfuri „izolate”. graficul zero. (Fig.2)

Sunt numite grafice în care nu sunt construite toate muchiile posibile grafice incomplete. (Fig.3)

Sunt numite grafice în care sunt construite toate muchiile posibile grafice complete. (Fig.4)

Se numește numărul de muchii care părăsesc un vârf al graficului gradul de vârf. Se numește un vârf al unui grafic care are un grad impar ciudat, și chiar gradul - chiar.

Dacă gradele tuturor vârfurilor unui grafic sunt egale, atunci graficul este numit omogen. Astfel, orice grafic complet este omogen.

Figura 5 prezintă un grafic cu cinci vârfuri. Gradul vârfului A va fi notat de art. A. În imagine: Art. A = 1, St. B = 2, St. B = 3, St. G= 2, St. D= 0.

Sarcina nr. 1.

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?

Soluţie:

Fiecăruia dintre cei cinci tineri să corespundă unui anumit punct al planului, numit prin prima literă a numelui său, iar strângerea de mână produsă să fie un segment sau o parte a unei curbe care leagă anumite puncte - nume.

Sarcina nr. 2.

Patru prieteni locuiesc în aceeași curte. Vadim și șoferul sunt mai în vârstă decât Serghei, Nikolai și mecanicul fac box, electricianul este cel mai tânăr dintre prietenii săi.

Seara, Andrei și turnerul joacă domino împotriva lui Serghei și a electricianului.

Determină profesia fiecăruia dintre prietenii tăi.

Soluţie.

Să facem un grafic cu 4 prieteni și 4 profesii. Liniile punctate indică conexiuni imposibile, iar liniile continue indică corespondența dintre nume și profesie. Dacă există 3 linii punctate care provin de la fiecare vârf, atunci a patra linie ar trebui să fie solidă.

V S N A

W S T E

Sarcina nr. 3.

Cinci prieteni locuiesc într-un oraș mic: Ivanov, Petrenko, Sidorchuk, Grishin și Kapustin. Profesiile lor sunt diferite: unul dintre ei este pictor, altul este morar, al treilea este dulgher, al patrulea este poștaș, iar al cincilea este frizer.

Petrenko și Grishin nu au ținut niciodată o pensulă în mâini.

Ivanov și Grișin urmează să viziteze moara unde lucrează prietenul lor. Petrenko și Kapustin locuiesc în aceeași casă cu poștașul.

Sidorchuk a fost recent unul dintre martorii de la oficiul registrului, când Petrenko și fiica coaforului erau căsătoriți legal. Ivanov și Petrenko joacă în orășele cu un dulgher și un pictor în fiecare duminică.

Grishin și Kapustin se întâlnesc mereu sâmbăta la coaforul unde lucrează prietenul lor. Poștașul preferă să se radă singur. Cine este cine?

Soluţie.

Ivanov Petrenko Sidorchuk Grishin Kapustin

pictor morar dulgher poștaș coafor

2.2. căile lui Euler. Construirea unei figuri cu o singură lovitură.

Să formulăm unele regularități inerente anumitor grafice.

Model 1.

Gradele vârfurilor unui graf complet sunt aceleași și fiecare dintre ele este cu 1 mai mic decât numărul de vârfuri ale acestui graf.

Dovada:

Acest model este evident după ce se analizează orice grafic complet. Fiecare vârf este conectat printr-o muchie la fiecare vârf, cu excepția lui însuși, adică din fiecare vârf al unui graf care are n vârfuri emană n-1 muchii, ceea ce trebuia demonstrat.

Modelul 2.

Suma gradelor vârfurilor unui grafic este un număr par egal cu dublul numărului de muchii ale graficului.

Acest model este valabil nu numai pentru un grafic complet, ci și pentru orice grafic.

Dovada:

Într-adevăr, fiecare muchie a graficului conectează două vârfuri. Aceasta înseamnă că dacă adunăm numărul de grade ale tuturor vârfurilor graficului, vom obține de două ori numărul de muchii 2R (R este numărul de muchii ale graficului), deoarece fiecare muchie a fost numărată de două ori, ceea ce a fost necesar pentru fi dovedit.

Numărul de vârfuri impare din orice grafic este par. Dovada:

Să considerăm un graf arbitrar G. Fie numărul de vârfuri din acest graf al căror grad este 1 să fie egal cu K1; numărul de vârfuri al căror grad este 2 este egal cu K2; ...; numărul de vârfuri al căror grad este n este egal cu Kn. Apoi suma gradelor vârfurilor acestui graf poate fi scrisă ca
K1 + 2K2 + ZK3 + ...+ nKn.
Pe de altă parte: dacă numărul de muchii ale graficului este R, atunci din Legea 2 se știe că suma gradelor tuturor vârfurilor graficului este egală cu 2R. Apoi putem scrie egalitatea
K1 + 2K2 + ZK3 + ... + nKn = 2R.
Să selectăm în partea stângă a egalității o sumă egală cu numărul de vârfuri impare ale graficului (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nKn = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2K3 +4K4 + 4K5 + ...)=2R
A doua paranteză este un număr par ca suma numerelor pare. Suma rezultată (2R) este un număr par. Prin urmare (K1 + K3 + K5 +...) este un număr par.

Q.E.D.

Sarcina nr. 4.

Este posibil să conectați 25 de dispozitive cu fire, astfel încât fiecare dispozitiv să fie conectat la exact alte cinci?

Soluţie.

Imposibil. Un astfel de grafic ar avea un număr impar de vârfuri de grad impar.

Rețineți că dacă un grafic complet are n vârfuri, atunci numărul de muchii va fi egal cu n(n-1)/2. Într-adevăr, numărul de muchii dintr-un grafic complet cu n vârfurile este definită ca numărul de perechi neordonate formate din toate n puncte-margini ale graficului, adică ca numărul de combinații ale n elemente din 2:
Un grafic care nu este complet poate fi completat pentru a fi complet cu aceleași vârfuri prin adăugarea muchiilor lipsă. De exemplu, Figura 3 prezintă un grafic incomplet cu cinci vârfuri. În Figura 4, muchiile care transformă graficul într-un grafic complet sunt reprezentate într-o culoare diferită; colecția de vârfuri ale graficului cu aceste muchii se numește complement al graficului.

Sarcina nr. 5.

La campionatul de tenis de masă sunt 6 participanți: Andrey, Boris Victor, Galina, Dmitry și Elena. Campionatul se desfășoară într-un sistem round robin - fiecare participant joacă o dată cu fiecare dintre ceilalți. Până în prezent, s-au jucat deja câteva jocuri: Andrey a jucat cu Boris, Galina, Elena; Boris - cu Andrey, Galina; Victor - cu Galina, Dmitri, Elena; Galina - cu Andrey, Victor și Boris. Câte jocuri s-au jucat până acum și câte au mai rămas?

Soluţie:

Să construim un grafic. Marcăm jocurile jucate cu linii albastre și adăugăm linii roșii pentru a completa graficul. Observăm că s-au jucat 7 jocuri și au mai rămas 8. Puteți verifica: în grafic sunt 6 vârfuri, apoi sunt în total 6*5/2=15 muchii (7+8).

Grafice Euler.

O cale Euler este o cale într-un grafic care trece prin fiecare muchie exact o dată.

Se numește un grafic care poate fi desenat fără a ridica creionul de pe hârtie Eulerian.(Fig. 6) Aceste grafice sunt numite după omul de știință Leonhard Euler.

Fig.6 (grafice euleriene)

Regularitatea 3 (reduce din teorema considerată).
Este imposibil să desenezi un grafic cu un număr impar de vârfuri impare.
Modelul 4.

Dacă toate vârfurile graficului sunt egale, atunci puteți desena acest grafic fără a ridica creionul de pe hârtie („cu o singură lovitură”), deplasându-vă 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.
Modelul 5.

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ă la unul dintre aceste vârfuri impare și să se termine la al doilea dintre ele.
Modelul 6.

Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu „o singură lovitură”.

Se numește o figură (grafic) care poate fi desenată fără a ridica creionul de pe hârtie unicursal.

Sarcină № 6 despre podurile Königsberg.

Ramurile râului Pregel, pe malurile cărora se află orașul Königsberg, formau două insule. În această epocă, cele patru secțiuni de pământ formate (malul drept și stânga și două insule) erau conectate prin șapte poduri, așa cum se arată în figură. Oamenii, plimbându-se prin oraș, au încercat să creeze un traseu astfel încât să treacă fiecare pod exact o dată.

Soluţie.

Această problemă a fost rezolvată de Leonhard Euler. El a construit următorul grafic și a descoperit că toate cele patru vârfuri sunt impare, adică este imposibil să traversezi toate podurile o dată și să închei calea de unde a început.

Sarcina nr. 7.

Cele patru insule sunt legate între ele și de malurile râului prin 14 poduri, așa cum se arată în figură. Este posibil să ocolești toate aceste poduri într-o singură plimbare, vizitându-le pe fiecare o dată?

Soluţie. Să construim un grafic. Există două vârfuri ciudate B și C. Prin urmare, într-o singură plimbare puteți parcurge toate podurile, vizitând fiecare dintre ele o dată. În acest caz, plimbarea trebuie să înceapă de pe insula B și să se termine pe insula C sau invers.

Sarcina nr. 8.

Este posibil să desenați graficele prezentate în imagini fără să ridicați creionul de pe hârtie și să desenați fiecare margine exact o dată?

Soluţie:

1) Este posibil, deoarece există doar 2 vârfuri impare.

2) Este imposibil, deoarece sunt 4 vârfuri impare.

Sarcina nr. 9.

Se spune că Mohammed, în loc să semneze (era analfabet), a descris dintr-o singură lovitură semnul format din două coarne ale lunii, arătat în desen. Este posibil?

Soluţie. Da, pentru că în acest caz avem de-a face cu vârfuri de ordin par.

Sarcina nr. 10. Zboară într-un borcan.

O muscă a intrat într-un borcan de zahăr. Borcanul are forma unui cub. Poate o muscă să ocolească secvențial toate cele 12 muchii ale unui cub fără a trece de două ori peste aceeași muchie? Săritul și zborul dintr-un loc în altul nu este permis.

Soluţie.

Muchiile și vârfurile formează un grafic, toate cele 8 vârfuri fiind de gradul 3 și, prin urmare, parcurgerea necesară nu este posibilă.

Sarcina nr. 11.

Încercați să construiți aceste figuri dintr-o singură lovitură.

2.3. Grafice plane.

Problema „trei case și trei fântâni” care m-a interesat a determinat dezvoltarea teoriei grafurilor. Un grafic care poate fi desenat pe un plan astfel încât muchiile sale să nu se intersecteze nicăieri decât la vârfuri se numește apartament sau plană.

Euler a demonstrat o teoremă care dă un răspuns negativ la întrebarea acestei probleme.

teorema lui Euler.

Dacă un grafic cu n vârfuri și m muchii este plat, atunci egalitatea n-m+p=2 este adevărată, unde p este numărul de părți disjunse (se numesc fețe) în care acest grafic împarte planul.

Dovada.

Graficul „trei case și trei puțuri” are șase vârfuri și nouă muchii. Dacă este plată, numărul muchiilor p trebuie să fie egal cu p = n – m + 2 = 9 - 6 + 2 = 5. Dar, deoarece nu există două case sau două puțuri legate între ele, fiecare față are cel puțin patru margini . Obținem inegalitatea 2n ≥ 4p (fiecare muchie se numără de două ori), din care obținem inegalitatea falsă 18 ≥ 20. În mod similar, se demonstrează că un graf complet cu cinci vârfuri, de asemenea, nu poate fi plan.

Teorema Pontryagin–Kuratowski.

Un grafic este plat dacă și numai dacă nu conține un grafic casă-puț cu șase vârfuri și un grafic complet cu cinci vârfuri.

3. Concluzie.

Pentru a găsi răspunsul la problema care m-a interesat, a trebuit să fac cunoștință cu o nouă ramură a matematicii, „Teoria graficelor”, care nu este studiată la cursul școlii, dar ușurează rezolvarea multor probleme. Am învățat multe de lucruri noi și a realizat că matematica este interesantă, dar și dificilă.

Graficele sunt obiecte matematice minunate care pot fi folosite pentru a rezolva probleme matematice, logice și economice. Rezolvarea multor probleme matematice devine mai ușoară dacă puteți folosi grafice. Prezentarea datelor sub forma unui grafic le face mai clare și mai simple. Multe dovezi matematice sunt, de asemenea, simplificate și devin mai convingătoare dacă sunt folosite grafice. 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.

4. Literatură.

3. Ignatiev ingeniozitate. - M.: „Omega”, 1994.

5. „Matematică” - supliment la ziarul „Primul septembrie” nr. 7, 2005

6. Dicţionar enciclopedic al unui tânăr matematician / Comp. A.P. Savin.- M.: Pedagogie, 1989.

De asemenea, am folosit date de pe următoarele site-uri:

Dicţionar enciclopedic al unui tânăr matematician / Comp. A.P. Savin.- M.: Pedagogie, 1989.

Pantofi în buzunarul cangur. - M.: Dropia, 2010.

Http:infometronovosibirsk_metro_map. htm

http://www. /index. php? cnt=4

Revista de fizică și matematică „Kvant”, nr. 6, 1994.

Pregătirea școlarilor pentru olimpiadele de matematică. 5-6 clase/comp. – M.: „Globul”, 2009.

Lucrarea lui Makeeva la matematică. – Saratov: „Liceul”, 2002

„Matematică” - supliment la ziarul „Primul septembrie” nr. 7, 2005

Revista de fizică și matematică „Kvant”, nr. 6, 1994.

Pantofi în buzunarul cangur. - M.: Dropia, 2010.

Revista de fizică și matematică „Kvant”, nr. 6, 1994.

Pregătirea școlarilor pentru olimpiadele de matematică. 5-6 clase/comp. – M.: „Globul”, 2009.

Revista de fizică și matematică „Kvant”, nr. 6, 1994.

Pantofi în buzunarul cangur. - M.: Dropia, 2010.

Lucrarea lui Makeeva la matematică. – Saratov: „Liceul”, 2002

Lucrarea lui Makeeva la matematică. – Saratov: „Liceul”, 2002

Ingeniozitatea lui Ignatiev. - M.: „Omega”, 1994.

Lucrarea lui Makeeva la matematică. – Saratov: „Liceul”, 2002

Pregătirea școlarilor pentru olimpiadele de matematică. 5-6 clase/comp. – M.: „Globul”, 2009.

Pantofi în buzunarul cangur. - M.: Dropia, 2010.

Înainte de a începe să studiați algoritmii înșiși, trebuie să aveți cunoștințe de bază despre graficele în sine și să înțelegeți cum sunt reprezentate pe computer. Toate aspectele teoriei grafurilor nu vor fi descrise în detaliu aici (acest lucru nu este necesar), ci numai acelea, a căror ignorare va complica în mod semnificativ asimilarea acestei zone de programare.

Câteva exemple vor oferi o mică schiță a graficului. Deci, un grafic tipic este o hartă de metrou sau o altă rută. În special, programatorul este familiarizat cu o rețea de calculatoare, care este și un grafic. Lucrul comun aici este prezența punctelor conectate prin linii. Deci, într-o rețea de calculatoare, punctele sunt servere individuale, iar liniile sunt diferite tipuri de semnale electrice. În metrou, primul sunt stațiile, al doilea sunt tunelurile așezate între ele. În teoria grafurilor, punctele sunt numite culmi (noduri), iar liniile sunt coaste (arcuri). Prin urmare, grafic este o colecție de vârfuri conectate prin muchii.

Matematica operează nu cu conținutul lucrurilor, ci cu structura lor, făcând abstracție de tot ceea ce este dat ca întreg. Folosind tocmai această tehnică, putem concluziona că unele obiecte sunt grafice. Și din moment ce teoria grafurilor este o parte a matematicii, nu are absolut nicio diferență în ceea ce este un obiect în principiu; singurul lucru important este dacă este un grafic, adică dacă are proprietățile necesare pentru grafice. Prin urmare, înainte de a da exemple, evidențiem în obiectul luat în considerare doar ceea ce credem că ne va permite să arătăm o analogie, căutăm ceea ce este comun.

Să revenim la rețeaua de calculatoare. Are o anumită topologie și poate fi descris în mod convențional sub forma unui anumit număr de computere și căi care le conectează. Figura de mai jos prezintă ca exemplu o topologie complet conectată.

Este în esență un grafic. Cele cinci calculatoare sunt vârfurile, iar conexiunile (căile semnalului) dintre ele sunt marginile. Înlocuind computerele cu vârfuri, obținem un obiect matematic - un grafic, care are 10 muchii și 5 vârfuri. Vârfurile pot fi numerotate în orice fel și nu neapărat așa cum se arată în figură. Este de remarcat faptul că acest exemplu nu folosește o singură buclă, adică o margine care părăsește un vârf și intră imediat în el, dar bucle pot apărea în probleme.

Iată câteva notații importante folosite în teoria grafurilor:

• G=(V, E), aici G este graficul, V sunt vârfurile sale, iar E sunt muchiile sale;
• |V| – ordine (număr de vârfuri);
• |E| – dimensiunea graficului (numărul de muchii).

În cazul nostru (Fig. 1) |V|=5, |E|=10;

Când orice alt vârf este accesibil din orice vârf, atunci se numește un astfel de grafic neorientat graficul conectat (Fig. 1). Dacă graficul este conectat, dar această condiție nu este îndeplinită, atunci se numește un astfel de grafic orientat sau digraf (fig. 2).

Graficele direcționate și nedirecționate au conceptul de grad de vârf. Gradul superior este numărul de muchii care îl conectează la alte vârfuri. Suma tuturor gradelor unui grafic este egală cu dublul numărului tuturor muchiilor acestuia. Pentru Figura 2, suma tuturor puterilor este 20.

Într-un digraf, spre deosebire de un graf nedirecționat, se poate trece de la vârful h la vârful s fără vârfuri intermediare, doar când o muchie iese din h și intră în s, dar nu și invers.

Graficele direcționate au următoarea notație:

G=(V, A), unde V sunt vârfuri, A sunt muchii direcționate.

Al treilea tip de grafice este amestecat grafice (Fig. 3). Au margini atât direcționate, cât și nedirecționale. Formal, un grafic mixt este scris astfel: G=(V, E, A), unde fiecare dintre literele dintre paranteze înseamnă același lucru care i-a fost atribuit mai devreme.

În graficul din Figura 3, unele arce sunt direcționate [(e, a), (e, c), (a, b), (c, a), (d, b)], altele sunt nedirecționate [(e, d), (e, b), (d, c)…].

La prima vedere, două sau mai multe grafice pot părea diferite ca structură, ceea ce apare din cauza reprezentării lor diferite. Dar nu este întotdeauna cazul. Să luăm două grafice (Fig. 4).

Sunt echivalente între ele, deoarece fără a modifica structura unui grafic, puteți construi altul. Se numesc astfel de grafice izomorfă, adică având proprietatea că orice vârf cu un anumit număr de muchii dintr-un graf are un vârf identic în altul. Figura 4 prezintă două grafice izomorfe.

Când fiecare muchie a graficului este asociată cu o anumită valoare numită greutatea muchiei, atunci un astfel de grafic suspendat. În diferite sarcini, diferite tipuri de măsurători pot acționa ca greutăți, de exemplu, lungimi, prețuri, rute etc. În reprezentarea grafică a unui grafic, valorile greutății sunt indicate, de regulă, lângă margini.

În oricare dintre graficele pe care le-am luat în considerare, este posibil să selectați o cale și, în plus, mai mult de una. cale este o succesiune de vârfuri, fiecare dintre acestea fiind conectat la următorul printr-o muchie. Dacă primul și ultimul vârf coincid, atunci o astfel de cale se numește ciclu. Lungimea unei căi este determinată de numărul de muchii care o alcătuiesc. De exemplu, în Figura 4.a calea este secvența [(e), (a), (b), (c)]. Această cale este un subgraf, deoarece definiția acestuia din urmă i se aplică și anume: graficul G'=(V', E') este un subgraf al graficului G=(V, E) numai dacă V' și E' aparțin lui V, E .

O relație de incidență este definită între elementele mulțimii de vârfuri și mulțimii de muchii. Se spune că o muchie e este incidentă cu vârfurile v1, v2 dacă conectează aceste vârfuri și invers, fiecare dintre vârfurile v1, v2 este incident cu muchia e.

Să ne uităm la reprezentarea grafică a graficelor din tabelul 1.

Tabelul 1. Reprezentarea grafică a graficelor

Multe rezultate obținute pentru grafice simple pot fi ușor transferate la obiecte mai generale în care două vârfuri pot fi conectate prin mai multe muchii. În plus, este adesea convenabil să se elimine constrângerea conform căreia o muchie trebuie să conecteze două vârfuri diferite și să permită existența buclelor. Obiectul rezultat, care poate avea mai multe margini și bucle, se numește grafic (pseudograf). Un pseudograf fără bucle se numește multigraf

Să ne uităm la câteva tipuri importante de grafice.

Definiție. Un grafic ale cărui multe muchii sunt goale se numește grafic complet deconectat (sau gol). Un grafic complet deconectat este notat cu N

Rețineți că într-un graf complet deconectat toate vârfurile sunt izolate

Definiție. Un grafic simplu în care oricare două vârfuri sunt adiacente se numește complet. Graficul complet este notat cu K

Rețineți că graficul complet satisface egalitatea

unde m este numărul de muchii, n este numărul de vârfuri ale graficului.

Definiție. Un grafic în care toate vârfurile au același grad local n se numește regulat (sau omogen) de gradul n.

Graficele regulate de gradul 3 se numesc cubice (sau trivalente).

Un exemplu celebru de grafic cubic este graficul Peterson

Dintre grafurile obișnuite sunt deosebit de interesante așa-numitele grafuri platonice - grafuri formate din vârfurile și muchiile a cinci poliedre regulate - Solide platonice: tetraedru, cub, octaedru, dodecaedru și icosaedru.Figura 6 prezintă un grafic corespunzător unui cub.

Definiție. Să presupunem că mulțimea de vârfuri a unui graf G poate fi împărțită în două submulțimi disjunse V1 și V2, astfel încât fiecare muchie din G să conecteze un vârf de la V1 cu un vârf de la V2, atunci acest graf se numește bipartit.

Un graf bipartit poate fi definit și în alt mod - în ceea ce privește colorarea vârfurilor sale cu două culori, să spunem roșu și albastru. Un grafic se numește bipartit dacă fiecare dintre vârfurile sale poate fi colorat în roșu sau albastru, astfel încât fiecare muchie să aibă un capăt roșu și celălalt albastru.

Definiție. Dacă într-un graf bipartit fiecare vârf din V1 este conectat la fiecare vârf din V2, atunci graficul se numește bipartit complet.

Rețineți că graficul Km. n are exact m + n vârfuri și mn muchii.

Definiție. Unirea graficelor

numit grafic

Definiție. Prin intersectia graficelor

numit grafic

Definiție. Legătura graficelor G1 și G2 este un nou grafic al cărui

iar setul de muchii sunt toate muchiile primului și celui de-al doilea grafic și muchiile care leagă fiecare vârf al primului grafic cu primul vârf al celui de-al doilea grafic.

Definiție. Un graf se numește conectat dacă nu poate fi reprezentat ca o uniune a două grafuri și deconectat în caz contrar.

Evident, orice graf deconectat poate fi reprezentat ca o uniune a unui număr finit de grafuri conectate - fiecare dintre astfel de grafuri conectate este numit o componentă conexă a graficului.

Definiție. Un graf regulat conex de gradul 2 se numește graf ciclic. Notat cu Cn.

Definiție. Legătura dintre graficele N1 și Cn-1 (n3) se numește roată cu n vârfuri. Notat cu Wn (Figura 10)

Definiție. Complementul unui graf simplu G este un graf simplu cu o mulțime de vârfuri V(G) în care două vârfuri sunt adiacente dacă și numai dacă nu sunt adiacente în graficul original.

Desemnare. Cu alte cuvinte, complementul unui grafic este un grafic care conține toate vârfurile graficului original și doar acele muchii care îi lipsesc graficului original pentru a-l completa.

Definiție. Un subgraf al unui grafic G este un grafic ale cărui vârfuri și muchii sunt cuprinse între vârfurile și muchiile graficului G. Un subgraf este numit propriu dacă este diferit de graficul însuși.

Graficele sunt un subiect distractiv, plin de satisfacții și înfricoșător. Teoria grafurilor - „Oroarea elevului”. Algoritmii grafici sunt mințile uimitoare ale oamenilor care i-au descoperit.

Ce este un grafic? Pentru a răspunde la această întrebare pentru cititorii mei, voi descrie subiectul puțin diferit.
Un grafic este un set de obiecte.
În majoritatea problemelor acestea sunt obiecte de același tip. (Multe orașe, sau multe case, sau mulți oameni, sau multe alte lucruri de același tip)

Pentru a rezolva problemele cu un astfel de set, trebuie să desemnați fiecare obiect din acest set ca ceva. Este în general acceptat să numim chiar acest lucru vârfurile graficului.

Este convenabil să descrii grafice și definiții de bază cu imagini, așa că imaginile trebuie incluse pentru a citi această pagină.

După cum am scris mai devreme, un grafic este un set de obiecte. Aceste obiecte sunt de obicei de același tip. Cel mai simplu mod de a da un exemplu este în orașe. Fiecare dintre noi știe ce este un oraș și ce este un drum. Fiecare dintre noi știe că pot fi sau nu drumuri către oraș. În general, orice set de obiecte poate fi caracterizat ca un grafic.

Dacă vorbim despre grafic ca despre orașe, atunci se pot construi drumuri între orașe, sau poate fi distrus undeva, nu construit, sau orașul este în general situat pe o insulă, nu există pod și doar drumurile asfaltate sunt de interes . În ciuda faptului că nu există drum spre un astfel de oraș, acest oraș poate fi inclus în multe obiecte analizate, iar toate obiectele luate împreună alcătuiesc o colecție de obiecte sau, mai simplu spus, un grafic.

Cu siguranță ați citit manuale și ați văzut această notație G(V,E) sau ceva asemănător. Deci, V este un singur obiect din întregul set de obiecte. În cazul nostru, mulțimea de obiecte sunt orașe, prin urmare, V este un oraș specific. Deoarece obiectele nu sunt neapărat orașe, iar cuvântul obiect poate fi confuz, un astfel de obiect din mulțime poate fi numit punct, punct sau altceva, dar cel mai adesea este numit vârful graficului și este notat cu litera. V.
În programare, aceasta este de obicei fie o coloană, fie o linie a unei matrice bidimensionale, unde matricea este numită fie o matrice de adiacență, fie o matrice de incidență.

În literatură, pe Internet și, în general, oriunde se scrie ceva despre grafice, veți întâlni concepte precum arce și muchii. Această figură arată marginile graficului. Acestea. acestea sunt trei muchii E1, E2 și E3.

Un arc și o muchie diferă prin aceea că o muchie este o conexiune bidirecțională. A vrut, s-a dus la vecin, a vrut, s-a întors de la vecin. Dacă nu este foarte clar, atunci vă puteți imagina o casă, un aerodrom, un avion zburător și un parașutist. Un parașutist poate merge de acasă la aerodrom, dar când ajunge pe aerodrom, își amintește că și-a uitat parașuta norocoasă acasă, apoi se întoarce acasă și ia parașuta. — Un drum de-a lungul căruia poți merge înainte și înapoi se numește margine.
Dacă un parașutist se află într-un avion și sare din avion, dar parașutătorul a uitat să-și pună parașuta norocoasă în avion, va putea parașutismul să ridice ceea ce a uitat? O cale care merge doar într-o singură direcție se numește arc. De obicei spunem că o muchie conectează două vârfuri, iar un arc trece de la un vârf la altul.

În această figură, graficul are doar arce. Arcurile de pe grafic sunt indicate prin săgeți, deoarece direcția accesibilă este atât de clară. Dacă un grafic constă numai din astfel de arce, atunci un astfel de grafic se numește direcționat.

Veți întâlni adesea conceptele de contiguitate și incidență. În figură, două margini care merg la un punct sunt marcate cu roșu. Astfel de muchii, ca și vârfurile descrise mai sus, sunt numite și adiacente.

Nu sunt descrise multe, dar această informație poate ajuta pe cineva.

„O altă modalitate incitantă de a rezolva probleme” (metoda grafică) Autor: Maria Pyrkova, elevă în clasa a VII-a la internatul Nr. 9 al Căilor Ferate Ruse, Kinel, Regiunea Samara Conducător: Olga Alekseevna Stepanova, profesoară de matematică de cea mai înaltă categorie. Kinel, 2015

Relevanța rolului decisiv al problemelor în predarea matematicii; introducerea în cursul școlar al secțiunilor „Combinatorică”, „Logică”, „Probabilitate”; găsirea unor modalități de rezolvare a problemelor non-standard.

Scopul studiului: studierea conceptului de „graf” și a elementelor sale; se aplică la rezolvarea diferitelor tipuri de probleme.

Obiectul de studiu: grafic SUBIECTUL CERCETĂRII istoria matematicii, tipuri de probleme, metode de rezolvare a problemelor.

Principalele metode de cercetare: cercetare; utilizarea în practică. prelucrare informatică a datelor; clasificarea și analiza materialului colectat; selecția matematică.

Conceptul matematic de „graf”. În matematică, un grafic este un set finit de puncte, dintre care unele sunt conectate prin linii. Punctele se numesc vârfuri ale graficului, iar liniile de legătură se numesc muchii. un grafic zero este un grafic incomplet. grafic complet.

Domeniul de aplicare al graficelor

Partea practică

Algoritm pentru compilarea unui grafic Discutați despre ce proces vorbim? Ce cantități caracterizează acest proces? Cum sunt legate aceste cantități? Câte procese sunt descrise în problemă? Există o legătură între elemente? Dacă răspunsurile la aceste întrebări sunt scrise schematic, atunci această diagramă va fi un grafic de rețea.

„Câte capete de vite ai în turmă?” La întrebarea călătorului: ciobanul a răspuns: „Dacă aș adăuga o vacă la turma mea, atunci o treime din întreaga turmă ar fi formată din oi și capre. Dacă ar fi să adăugăm o oaie la oile și caprele existente, atunci a șaptea parte dintre ele ar fi capre, dintre care a treia parte este doar un ied mic.” Câte capete de vite erau în turmă? Soluție: Să creăm un grafic pe baza condițiilor problemei. Să decidem înapoi. Răspuns: în turmă sunt 59 de capete de vite.

Sarcini de mișcare. Mașina a parcurs primul tronson de traseu în 3 ore, iar al doilea tronson în 2 ore. Lungimea ambelor secțiuni împreună este de 267 km. Cu ce ​​viteză mergea mașina în fiecare secțiune, dacă viteza în a doua secțiune era cu 8,5 km/h mai mare decât în ​​prima? Să construim un grafic de rețea. Fie V 1 = x km/h, apoi V 2 = x+ 8,5 km/h, S 1 = 3x km, S 2 = 2(x+8,5) km Să creăm ecuația: 3x + 2(x+8.5 ) = 267 Raspuns: 50 km/h

Probleme combinatorii. Sarcina „Care este mai mare?” Pe terenul școlii cresc 8 copaci: măr, plop, mesteacăn, rowan, stejar, arțar, zada și pin. Rowan este mai înalt decât zada, mărul este mai înalt decât arțarul, stejarul este mai jos decât mesteacănul, dar mai sus decât pinul, pinul este mai mare decât șorbalul, mesteacănul este mai jos decât plopul și zada este mai mare decât mărul. Aranjați copacii de la cel mai scurt la cel mai înalt. Răspuns: arțarul este cel mai scurt copac.

Sondaj colegilor de clasă

Concluzie „Mai devreme sau mai târziu, fiecare idee matematică corectă își găsește aplicare într-un lucru sau altul.” (A.N. Krylov) Graficele sunt obiecte matematice minunate cu ajutorul cărora poți rezolva probleme matematice, economice și logice. Graficele vă permit să reprezentați vizual condițiile unei probleme, să păstrați numeroase fapte în memorie și, prin urmare, să simplificați în mod semnificativ soluția acesteia. Generează interes pentru învățarea matematicii și obținerea de rezultate bune.

Referințe Dicționar enciclopedic al unui tânăr matematician. \Comp. A.P.Savin.- M.: Pedagogie, 1989 Quantum No. 6 1994 M. Gardner „Mathematical leisure” M.: Mir, 1972 Berge K. Teoria grafurilor și aplicarea ei. IL, 1962. Matematică, manual pentru clasa a V-a. / N.Ya.Vilenkin, V.I.Zhokhov și alții - M: Educație, 2011 Matematică, manual pentru clasa a VI-a. / N.Ya.Vilenkin, V.I.Zhokhov și alții - M: Educație, 2011 Algebră: manual pentru clasa a VII-a. / Yu.N. Makarychev și colab., editat de S.A. Telyakovsky.-M.: Educație, 2011 Cursuri opționale „Rezolvarea problemelor folosind grafice” / autor - L.N. Kharlamov. - Volgograd: Profesor, 2007.

Vă mulțumim pentru atenție!