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

introducerea elevilor în conceptul de „Grafic”, principiile de bază ale construcției acestuia;

dezvoltarea capacității de a identifica relații care leagă obiecte;

dezvoltă atenția și capacitatea de raționament logic;

dezvolta asistenta reciproca si capacitatea de a lucra in echipa

consolidarea cunoştinţelor dobândite în practică

dezvoltarea memoriei, a atenției;

dezvoltarea independenței;

educarea activităţii cognitive.

Echipament:

• clasa de calculatoare dotata cu tehnologie moderna, videoproiector, ecran;
• computere cu sistem de operare Windows XP, programul Microsoft Office 2003 PowerPoint;
• echipament de bord (tema lecției, termeni noi).

Material pentru fișe.

Planul de lecție.

II. Prezentarea de material nou. (10 min.)

III. Fixarea materialului. Lucrări practice. (15-20 min.)

IV. Rezumatul lecției (2 min.) V..

Teme pentru acasă eu. Moment organizatoric

. Actualizarea cunoștințelor.

Buna ziua! Lecția noastră se numește „Grafe”. Ne vom familiariza cu conceptul de „Grafe”, vom învăța cum să le descriem și să rezolvăm probleme pe această temă.

II Prezentarea de material nou.

Prima lucrare despre teoria grafurilor îi aparține lui Leonhard Euler (1736), deși termenul „graf” a fost introdus pentru prima dată în 1936 de matematicianul maghiar Dénes König. Graficele erau denumirile date schemelor formate din puncte și segmente de linie sau curbe care leagă aceste puncte (exemple de grafice sunt prezentate în Figura 1)

Cu ajutorul graficelor s-a simplificat adesea rezolvarea problemelor formulate în diverse domenii de cunoaștere: în automatizare, electronică, fizică, chimie etc. Cu ajutorul graficelor sunt reprezentate diagrame de drumuri, conducte de gaz, rețele de căldură și electricitate. . Graficele ajută la rezolvarea problemelor matematice și economice.

Graficul – (din grecescul grapho – scriu) este un mijloc de reprezentare vizuală a elementelor unui obiect și a conexiunilor dintre ele. Acestea sunt obiecte matematice minunate, cu ajutorul lor, puteți rezolva o mulțime de probleme diferite, în exterior.

Graficul este format din vârfuri sau noduri conectate prin arce sau segmente - muchii. O linie poate fi direcționată, adică are o săgeată (arc) dacă nu este direcționată, are o margine; Două vârfuri conectate printr-un arc sau muchie sunt numite adiacente.

Exemple de grafice (Diapozitivul 4, 5, 6)

Sarcina 1 (Diapozitivul 7):

Comunicarea spațială a fost stabilită între cele nouă planete ale sistemului solar. Rachetele programate zboară pe următoarele rute:

Pământ - Mercur; Pluto - Venus; Pământ - Pluto; Pluto - Mercur; Mercur - Venus; Uranus - Neptun; Neptun - Saturn; Saturn – Jupiter; Jupiter - Marte; Marte - Uranus.

Este posibil să zbori cu rachete obișnuite de pe Pământ pe Marte?

Soluție: Să desenăm o diagramă a stării: vom reprezenta planetele ca puncte, iar rutele rachetei ca linii.

Acum este imediat clar că este imposibil să zbori de pe Pământ pe Marte.

Două vârfuri conectate printr-un arc sau muchie sunt numite adiacente. Fiecare muchie sau arc este asociat cu un număr. Numărul poate indica distanța dintre așezări, timpul de trecere de la un vârf la altul etc.

Sarcina 2 (9 diapozitive) – soluție la tablă. Masha a venit la grădina zoologică și vrea să vadă cât mai multe animale. Pe ce cale ar trebui să o ia? Galben, rosu, verde?

Sarcina 3 (11 diapozitive) – soluție la tablă. Cinci echipe de fotbal A, B, C, D, D trebuie să joace meciuri una împotriva celeilalte. A jucat deja A cu B, C, D; B cu A, C, D. cate meciuri s-au jucat deja? Cât timp a mai rămas de jucat?

Prezentarea graficelor (Diapozitivul 12)

Graficul poate fi prezentat ca o listă de arce (AB; 7), grafic sau folosind un tabel.

Liste de arc	Forma grafică	Forma tabelară
(AB; 7),		O ÎN CU O 3 ÎN 4 CU 3 4

III. Materiale de întărire: Elevii sunt rugați să se împartă în grupuri și să finalizeze temele. Lucrând în grup mic, elevii discută modele bazate pe cunoștințele teoretice dobândite la începutul lecției. Acest lucru asigură repetarea și consolidarea materialului.

Sarcina 2 (Diapozitivul 13)

IV. Rezumatul lecției

Băieți, ce cuvinte noi ați învățat astăzi? (Grafic, vârful graficului, marginile graficului.)

Ce pot reprezenta vârfurile graficului? (Orașe; obiecte care sunt; conectate.)

Ce înseamnă marginile graficului (căi, mișcări, direcții)

Dați un exemplu unde în viață îi putem întâlni?

Cum sunt reprezentate graficele?

V. Tema pentru acasă. (Diapozitivul 15)

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

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

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

Matricea incidentelor

Liste de comunicare

Lista de coaste

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

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

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

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

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

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

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

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

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

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

În zilele noastre este important să studiezi diverse metode, proprietăți și aplicații non-standard. Vom lua în considerare aplicarea metodei Graph în realitatea din jurul nostru.

Cuvântul „graf” în matematică înseamnă o imagine cu mai multe puncte desenate, dintre care unele sunt conectate prin linii. În primul rând, merită să spunem că conții despre care vor fi discutate nu au nicio legătură cu aristocrații vremurilor trecute. „Grafele” noastre sunt înrădăcinate în cuvântul grecesc „grapho”, care înseamnă „eu scriu”. Aceeași rădăcină este în cuvintele „graf”, „biografie”.

Prima lucrare despre teoria grafurilor îi aparține lui Leonhard Euler și a apărut în 1736 în publicațiile Academiei de Științe din Sankt Petersburg.

Numărări întâlnite:

în fizică – la construirea circuitelor electrice

în chimie și biologie – când studiază moleculele lanțurilor lor

în istorie - la compilarea arborilor genealogici (genealogii)

în geografie – la desenarea hărților

în geometrie - desene de poligoane, poliedre, figuri spațiale

în economie – la rezolvarea problemelor privind alegerea căii optime pentru fluxuri transport de marfa(scheme de linii aeriene, metrou, căi ferate)

Teoria grafurilor este folosită pentru a rezolva probleme la olimpiadele matematice. Graficele clarifică condițiile problemei, simplifică soluția și dezvăluie asemănarea problemelor.

În zilele noastre în orice ramură a științei și tehnologiei întâlniți grafice.

Descărcați:

Previzualizare:

Pentru a folosi previzualizare prezentări creați-vă un cont ( cont) Google și conectați-vă: https://accounts.google.com

Subtitrările diapozitivelor:

Prezentare pe tema matematică: „Grafe” Completată de elevul grupei 14-PGS-48D Anastasia Korobova

Un grafic este o figură formată din puncte și linii care leagă aceste puncte. Liniile sunt numite muchii ale graficului, iar punctele sunt numite vârfuri. Vârfurile din care iese un număr par de muchii se numesc pare, iar un număr impar se numesc impar. Exemple de grafice Teoria graficelor

Leonhard Euler (4 aprilie 1707, Basel, Elveția - 7 septembrie 1783, Sankt Petersburg, Imperiul Rus) - Matematician elvețian, german și rus care a adus o contribuție semnificativă la dezvoltarea matematicii, precum și a mecanicii, fizicii, astronomiei și a unui număr de științe aplicate. Euler este autorul a peste 800 de lucrări de analiză matematică, geometrie diferențială, teoria numerelor, calcule aproximative, mecanică cerească, fizică matematică, optică, balistică, construcții navale, teoria muzicii etc.

O figură (grafic) care poate fi desenată fără a ridica creionul de pe hârtie se numește unicursal. Model 1. Un grafic cu doar două vârfuri impare poate fi desenat fără a ridica creionul de pe hârtie, iar mișcarea trebuie să înceapă de la unul dintre aceste vârfuri impare și să se termine la al doilea dintre ele. (Fig. A) Model 2. Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu „o singură lovitură” (Fig. B) Grafice Euler B A

Model 3. Dacă toate vârfurile unui grafic sunt pare, atunci puteți desena acest grafic fără a ridica creionul de pe hârtie, trasând fiecare margine o singură dată. Mișcarea poate începe de la orice vârf și se poate termina la același vârf.

Următoarea ghicitoare a fost de mult obișnuită printre locuitorii din Königsberg: cum să traversați toate podurile (de peste râul Pregolya) fără să treceți de două ori peste niciunul dintre ele? Mulți au încercat să rezolve această problemă atât teoretic, cât și practic, în timpul plimbărilor Problema podurilor Königsberg.

Acesta este un grafic în care unele muchii pot fi direcționate, iar unele muchii pot fi nedirecționate. Grafic mixt

Graficul ponderat 1 2 4 2 3 A B C D E

Un arbore este orice grafic conectat care nu are cicluri. Copaci Copaci

Acesta este un grafic (multi) căruia îi este atribuită o direcție pentru muchii. Marginile direcționate sunt numite și arce. Graficul dirijat

Numărări întâlnite:

Teoria grafurilor este folosită pentru a rezolva probleme la olimpiadele matematice. Graficele clarifică condițiile problemei, simplifică soluția și dezvăluie asemănarea problemelor. În zilele noastre în orice ramură a științei și tehnologiei întâlniți grafice.

Vă mulțumim pentru atenție!