Echipament:
- clasa de calculatoare dotata cu tehnologie moderna, videoproiector, ecran;
- calculatoare cu sistem de operare Windows XP, Microsoft Office 2003 PowerPoint;
- echipament de bord (tema lecției, termeni noi). Înmânează.
Planul lecției.
II. Prezentarea noului material. (10 minute.)
III. Fixarea materialului. Munca practica. (15-20 min.)
IV. Rezumatul lecției (2 min.)
V. Tema pentru acasă.
I. 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.
Un grafic este un fel de model informațional
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), |
|
III. Materiale de întărire: Elevii sunt rugați să se împartă în grupuri și să finalizeze teme. Lucrând într-un 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 întins conectat 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 subset singleton. Marginile sunt sortate după ponderi crescătoare. 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 conexă: (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). Calculul greutăților muchiilor. 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
Pentru a vizualiza prezentarea cu imagini, design și diapozitive, descărcați fișierul și deschideți-l în PowerPoint pe calculatorul tau.
Conținutul text al slide-urilor prezentării: Grafice și aplicarea lor în rezolvarea problemelor Cuprins Ce este un grafic Proprietățile unui grafic Istoria apariției graficelor Problema podurilor Königsberg Aplicarea graficelor Concluzii Ce este un grafic În matematică, definiția unui grafic este dată astfel: A graficul este un set nevid de puncte și un set de segmente, ambele capete aparțin unui set dat de puncte. Punctele sunt numite vârfuri ale graficului, iar liniile de legătură sunt muchii. Muchiile unui grafic Nodurile unui grafic Următorul Ce este un grafic Numărul de muchii care ies dintr-un vârf al unui grafic se numește gradul vârfului. Un vârf al unui grafic care are un grad impar se numește impar, iar un vârf care are un grad par se numește par. Gradul impar Conținutul gradului par Proprietăți ale graficelor Într-un grafic, suma gradelor tuturor nodurilor sale este un număr par, egal cu dublul numărului de muchii ale graficului grafic cu n vârfuri, unde n≥2, există întotdeauna două vârfuri cu aceleași grade. Proprietățile graficelor Dacă într-un grafic cu n vârfuri (n>2) exact două vârfuri au același grad, atunci în acest grafic există întotdeauna fie exact un vârf de grad 0, fie exact un vârf de grad n-1 graficul are n vârfuri, atunci numărul de muchii va fi egal cu n(n-1)/2. Proprietățile unui grafic Grafic complet Grafic incomplet Proprietăți ale unui grafic Grafic direcționat Grafic nedirecționat Grafice izomorfe Istoria graficelor Termenul „graf” a apărut pentru prima dată în cartea matematicianului maghiar D. Koenig în 1936, deși cele mai importante teoreme inițiale despre grafice merg înapoi la L. Euler. Istoria ulterioară a apariției grafurilor Bazele teoriei grafurilor ca știință matematică au fost puse în 1736 de Leonhard Euler, luând în considerare problema podurilor Königsberg. Astăzi, această sarcină a devenit una clasică. cuprins Problemă despre podurile Königsberg Fostul Königsberg (acum Kaliningrad) este situat pe râul Pregel. În interiorul orașului, râul spală două insule. Au fost construite poduri de la țărmuri la insule. Podurile vechi nu au supraviețuit, dar a rămas o hartă a orașului, unde sunt reprezentate. Următorul Problema podurilor din Königsberg Următoarea problemă a fost răspândită în rândul locuitorilor din Königsberg: este posibil să treci pe jos peste toate podurile și să te întorci la punctul de plecare, vizitând fiecare pod o singură dată? Problemă suplimentară despre podurile Königsberg Este imposibil să treceți peste podurile Königsberg respectând condițiile date. Mersul peste toate podurile, cu condiția să le vizitezi pe fiecare o dată și să te întorci la punctul de plecare al călătoriei, în limbajul teoriei grafurilor pare sarcina de a reprezenta un grafic cu „o singură lovitură”. în continuare Problema podurilor Königsberg Dar, deoarece graficul din această figură are patru vârfuri impare, este imposibil să se deseneze un astfel de grafic „cu o singură lovitură”. cuprins Graficul Euler Un grafic care poate fi desenat fără a ridica creionul de pe hârtie se numește grafic Euler. Rezolvând problema podurilor Königsberg, Euler a formulat proprietățile graficului: Numărul de vârfuri impare (versuri la care duc un număr impar de muchii) ale graficului trebuie să fie par. Nu poate exista un grafic care are un număr impar de vârfuri impare Dacă toate vârfurile graficului sunt pare, atunci puteți desena un grafic fără a ridica creionul de pe hârtie și puteți începe de la orice vârf al graficului și puteți termina. la același vârf. Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu o singură lovitură. Graficul Euler suplimentar Dacă toate vârfurile graficului sunt pare, atunci puteți desena acest grafic fără a ridica creionul de pe hârtie („cu o singură lovitură”), trecând 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. Graficul Euler suplimentar 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. Graficul Euler suplimentar Un grafic cu mai mult de două vârfuri impare nu poate fi desenat cu „o singură lovitură”. ? Utilizarea graficelor Utilizarea graficelor, rezolvarea de probleme matematice, puzzle-uri și probleme de ingeniozitate este simplificată. Aplicarea în continuare a graficelor Problemă: 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? Aplicarea în continuare a graficelor Soluție: A D C B D 1 2 3 4 5 6 7 8 9 10 în continuare Aplicarea graficelor În stat, sistemul de transport aerian este conceput astfel încât orice oraș să fie conectat de companii aeriene de cel mult trei alte orașe, iar din orice oraș în oricare altul Puteți călători făcând nu mai mult de o schimbare. Care este numărul maxim de orașe care pot fi în acest stat? Aplicarea graficelor Să existe un anumit oraș A. Din el nu se poate ajunge la mai mult de trei orașe, iar din fiecare dintre ele nu mai mult de două (fără a număra A). Atunci numărul total de orașe nu este mai mare de 1+3+6=10. Aceasta înseamnă că nu există mai mult de 10 orașe în total. Exemplul din figură arată existența companiilor aeriene. O aplicație a graficelor Există o tablă de șah 3x3, în cele două colțuri de sus sunt doi cavaleri negri, în cei de jos sunt doi albi (poza de mai jos). În 16 mișcări, pune cavalerii albi în locul celor negri și cavalerii negri în locul celor albi și demonstrează că este imposibil să faci asta în mai puține mișcări. Aplicarea graficelor După ce am extins graficul posibilelor mișcări ale cavalerilor într-un cerc, constatăm că la început cavalerii stăteau ca în figura de mai jos: Concluzie Graficele sunt obiecte matematice minunate, cu ajutorul cărora puteți rezolva probleme matematice, economice și probleme logice. 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. Există chiar și o secțiune specială în matematică numită „Teoria graficelor”. conţinut
Fișiere atașate
Slide 2
Un graf este o colecție finită de vârfuri, dintre care unele sunt conectate prin muchii, de exemplu. aceasta este o colecție de puncte numite vârfuri și linii care leagă unele dintre vârfuri, numite muchii sau arce în funcție de tipul de grafic (de exemplu, o hartă de metrou, un arbore genealogic, un arbore de foldere și directoare etc.)
Slide 3
Tipuri (exemple) de grafice:
Într-un grafic obișnuit (nedirecționat), 2 vârfuri pot fi conectate printr-o singură muchie. Liniile de legătură se numesc muchii. (vârfurile adiacente sunt 2 vârfuri conectate printr-o muchie)
Slide 4
Un grafic direcționat (digraf) este un grafic în care direcția este indicată pe liniile care leagă vârfurile (liniile de legătură se numesc arce)
Slide 5
Un grafic încărcat este un grafic care are un număr lângă fiecare muchie care caracterizează legătura dintre vârfurile corespunzătoare (un grafic cu muchii etichetate).
Slide 6
O rețea este un digraf cu un număr lângă fiecare muchie care caracterizează legătura dintre vârfurile corespunzătoare (un digraf cu muchii etichetate).
Slide 7
Rezolvarea unei probleme modelate printr-un grafic sau o rețea încărcată se reduce de obicei la găsirea unei rute optime într-un sens sau altul care duce de la un vârf la altul
Slide 8
Un graf semantic este un graf sau digraf în care fiecare muchie nu are un număr, ci alte informații care caracterizează legătura dintre vârfurile corespunzătoare.
Slide 9
Multigraf 2 vârfuri conectate prin 2 sau mai multe muchii (mai multe muchii)
Slide 10
Buclă într-un grafic (o muchie conectează un vârf la sine)
Slide 11
Conceptul de grad al unui vârf într-un grafic este numărul de muchii care ies dintr-un vârf
Slide 12
PROPRIETĂȚI GRAFULUI:
1) Pentru orice graf, suma gradelor vârfurilor este egală cu dublul numărului de muchii 2) Pentru orice graf, numărul de vârfuri de grad impar este întotdeauna par (analog cu problema: la un moment dat numărul de persoane care au făcut un număr impar de strângeri de mână este par) 3) În orice grafic există cel puțin 2 vârfuri având același grad.
Slide 13
1) Un traseu pe un grafic este o succesiune de muchii în care capătul unei muchii servește ca începutul următorului (traseu ciclic - dacă sfârșitul ultimei muchii a secvenței coincide cu începutul primei muchii) 2 ) Un lanț este un traseu în care fiecare muchie conține de cel mult o dată3) Un ciclu este un lanț care este o rută ciclică4) Un lanț simplu este un lanț care trece prin fiecare dintre vârfurile sale exact 1 dată5) Un ciclu simplu este un ciclu adică un lanț simplu6) Vârfurile conectate sunt vârfuri (de exemplu, A și B), pentru care există un lanț care începe la A și se termină la B7) Un graf conex este un graf în care sunt conectate oricare 2 vârfuri. Dacă graficul este deconectat, atunci este posibil să se identifice așa-numitele componente conectate (adică, seturi de vârfuri conectate prin marginile graficului original, fiecare dintre acestea fiind un grafic conectat). moduri.
Slide 14
Exemplul 1
V=(1,2,3,4,5,6,7,8,9,10) este mulțimea de vârfuri ale graficului. Pentru fiecare dintre cazurile enumerate mai jos, desenați un grafic și determinați toate gradele vârfurilor a) vârfurile x y sunt conectate printr-o muchie dacă și numai dacă (x-y)/3 întreg b) vârfurile x y sunt conectate printr-o muchie dacă și numai dacă x+y=9 c ) vârfurile x y sunt legate printr-o muchie dacă și numai dacă x+y este conținut în mulțimea V=(1,2,3,4,5,6,7,8,9,10) d ) vârfurile x y sunt legate printr-o muchie dacă și numai dacă , când |x-y|