Prezentare pe tema „grafice”. Teoria grafurilor. Teoria grafurilor este o ramură independentă extinsă a matematicii discrete. Folosit în proiectarea rețelelor de calculatoare, conductelor, - prezentare Condiții necesare pentru izomorfism

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). Același grafic poate fi reprezentat în diferite 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|

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

În zilele noastre, este important să studiem diferite 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 de alegere a căii optime pentru fluxurile de transport de mărfuri (linie aeriană, metrou, scheme feroviare)

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.

Descarca:

Previzualizare:

Pentru a utiliza previzualizările prezentării, creați un cont Google și conectați-vă la el: 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) a fost un matematician elvețian, german și rus care a adus contribuții semnificative la dezvoltarea matematicii, precum și a mecanicii, fizicii, astronomiei. și o serie 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) Modelul 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!

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 se numesc 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ățile graficelor Într-un grafic, suma gradelor tuturor vârfurilor sale este un număr par, egal cu dublul numărului de muchii ale graficului. Numărul de vârfuri impare ale oricărui grafic este par. În orice 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 larg 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 este 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ți cavalerii albi în locul celor negri și cavalerii negri în locul celor albi și demonstrați că este imposibil să faceți acest lucru î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

1 tobogan

2 tobogan

Bazele teoriei grafurilor au apărut pentru prima dată în lucrările lui Leonhard Euler (1707-1783; matematician elvețian, german și rus), în care a descris rezolvarea puzzle-urilor și a problemelor de divertisment matematic. Teoria grafurilor a început cu soluția lui Euler la problema celor șapte poduri din Königsberg.

3 slide

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. Dar nimeni nu a reușit, dar nici nu au reușit să demonstreze că era chiar imposibil teoretic. Într-o diagramă simplificată a părților unui oraș (graf), podurile corespund liniilor (arce ale graficului), iar părțile orașului corespund punctelor care leagă liniile (vârfurile graficului). În cursul raționamentului său, Euler a ajuns la următoarele concluzii: Este imposibil să traversezi toate podurile fără a trece de două ori peste oricare dintre ele.

4 slide

Există 4 grupe de sânge. Când sângele este transfuzat de la o persoană la alta, nu toate grupurile sunt compatibile. Dar se știe că grupuri identice pot fi transferate de la persoană la persoană, adică. 1 – 1, 2 – 2 etc. Și, de asemenea, grupul 1 poate fi transfuzat în toate celelalte grupuri, grupurile 2 și 3 numai în grupul 4. Sarcină.

5 slide

6 diapozitiv

Grafice Un grafic este un model informativ prezentat sub formă grafică. Un graf este un set de vârfuri (noduri) conectate prin muchii. Un grafic cu șase vârfuri și șapte muchii. Vârfurile sunt numite adiacente dacă sunt legate printr-o muchie.

7 slide

Grafice direcționate - digrafe Fiecare muchie are o direcție. Astfel de muchii se numesc arce. Graficul dirijat

8 slide

Graficul ponderat Acesta este un grafic căruia îi sunt atribuite muchii sau arce valori numerice (pot indica, de exemplu, distanța dintre orașe sau costul transportului). Greutatea unui grafic este egală cu suma greutăților muchiilor acestuia. Tabelul (numit matrice de greutate) are un grafic corespunzător. 1 2 4 2 3 A B C D E

Slide 9

Problemă Au fost construite drumuri între localitățile A, B, C, D, E, F, a căror lungime este prezentată în tabel. (Lipsa unui număr în tabel înseamnă că nu există un drum direct între puncte). Determinați lungimea celei mai scurte căi dintre punctele A și F (presupunând că călătoria se poate face numai pe drumuri construite). 1) 9 2) 10 3) 11 4) 12

10 diapozitive

1. 2. 3. 4. 5. Lungimea celui mai scurt traseu A-B-C-E-F este de 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

 

Ar putea fi util să citiți:

• Teza pe tema „analiza planificarii personalului la intreprindere” Analiza planificarii personalului la intreprindere;
• Prezentare „Tailed” (clasa a VI-a) la biologie – proiect, raport Cine sunt axolotii;
• Prezentare pe tema „apel”;
• Prezentări Powerpoint la școală;
• Prezentare pe tema „Grafe”;
• Ghid pas cu pas și exemplu;
• Toate domeniile profesiilor;
• Rezumatul lecției de lectură literară „Basem armean” client și maestru” Client și maestru basm autor;