Teoria grafurilor. Teoria grafurilor este o ramură independentă extinsă a matematicii discrete

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

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

Cuvântul „graf” în matematică înseamnă o imagine în care sunt desenate mai multe puncte, dintre care unele sunt conectate prin linii. În primul rând, este de spus că conții, despre care se va discuta, nu au nicio legătură cu aristocrații din trecut. „Grafele” noastre sunt derivate din cuvântul grecesc „grapho”, care înseamnă „eu scriu”. Aceeași rădăcină în cuvintele „graf”, „biografie”.

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

Numărările se întâlnesc:

în fizică – în construcţia circuitelor electrice

în chimie și biologie - în studiul moleculelor lanțurilor lor

în istorie - la compilarea arborilor genealogici (pedigree)

în geografie – în cartografiere

î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 (companii aeriene, metrou, căi ferate)

Teoria graficelor este folosită în rezolvarea sarcinilor olimpiadelor matematice. Graficele dau vizibilitate condițiilor problemei, simplifică soluția și dezvăluie asemănarea problemelor.

Acum, în orice ramură a științei și tehnologiei, te întâlnești cu grafice.

Descarca:

Previzualizare:

Pentru a utiliza previzualizarea prezentărilor, creați un cont Google (cont) și conectați-vă: https://accounts.google.com

Subtitrările diapozitivelor:

Prezentare la matematică Tema: „Grafe” Completată de un elev din grupa 14-PGS-48D Korobova Anastasia

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, un număr impar se numește impar. Exemple de grafuri Teoria grafurilor

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 avut o contribuție semnificativă la dezvoltarea matematicii, precum și a mecanicii, fizicii, astronomie ş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 care are 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

Regularitate 3. Dacă toate vârfurile graficului sunt pare, atunci fără a ridica creionul de pe hârtie, desenând de-a lungul fiecărei margini o singură dată, desenați acest grafic. Mișcarea poate începe de la orice vârf și se poate termina la același vârf.

De multă vreme, o astfel de ghicitoare a fost răspândită printre locuitorii din Königsberg: cum să treci prin toate podurile (de peste râul Pregolya) fără a trece de două ori prin 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 altele pot fi nedirecționate. Număr 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 (multi)graf căruia i se atribuie o direcție muchii. Marginile direcționate sunt numite și arce. Graficul dirijat

Numărările se întâlnesc:

Teoria graficelor este folosită în rezolvarea sarcinilor olimpiadelor matematice. Graficele dau vizibilitate condițiilor problemei, simplifică soluția și dezvăluie asemănarea problemelor. Acum, în orice ramură a științei și tehnologiei, te întâlnești cu grafice.

Vă mulțumim pentru atenție!

să familiarizeze elevii cu conceptul de „Grafic”, principiile de bază ale construcției acestuia;

să formeze capacitatea de a evidenția relații care leagă obiecte;

dezvoltarea atenției, a capacității de raționament logic;

promovează asistența reciprocă, capacitatea de a lucra în echipă

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, program Microsoft Office PowerPoint 2003;
• echipamente pentru tablă albă (tema lecției, termeni noi). Înmânează.

Planul lecției.

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

III. Fixarea materialului. Munca practica. (15-20 min.)

IV. Rezumatul lecției (2 min)

v. Teme pentru acasă.

I. Moment organizatoric. Actualizare de cunoștințe.

Salut! 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 Denesh Koenig. Graficele au fost numite scheme formate din puncte și segmente de linii drepte sau curbe care leagă aceste puncte (exemple de grafice sunt prezentate în Figura 1)

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

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

Un grafic este un model de informații

Un graf este format din vârfuri sau noduri conectate prin arce sau segmente - muchii. Linia poate fi direcționată, adică are o săgeată (arc), dacă nu este direcționată - 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):

S-a stabilit o comunicare spațială între cele nouă planete ale sistemului solar. Rachetele obișnuite 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 cu puncte și traseele rachetelor cu 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 (diapozitivul 9) - soluția este 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ția este la tablă. Cinci echipe de fotbal A, B, C, D, E trebuie să joace meciuri între ele. A jucat deja A cu B, C, D; B c A, C, D. câte meciuri s-au jucat până acum? Cât a mai rămas de jucat?

Reprezentare grafică (Diapozitivul 12)

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

Liste de arc	Forma grafică	formă tabelară
(AB; 7),		A V CU A 3 V 4 CU 3 4

III. Consolidarea materialelor: elevii sunt invitați să se împartă în grupuri și să finalizeze sarcini. Lucrând într-un grup mic, elevii discută modele bazate pe cunoștințele teoretice dobândite la începutul lecției. Astfel, se realizează repetarea și consolidarea materialului.

Sarcina 2 (Diapozitivul 13)

IV. Rezumatul lecției

Băieți, ce cuvinte noi ați învățat astăzi? (Număr, vârf grafic, margini grafic.)

Ce pot reprezenta vârfurile unui grafic? (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 afișate graficele?

V. Tema pentru acasă. (Diapozitivul 15)

Numărul de vârfuri este numit
ordinea graficului.
Numărul de muchii este numit
dimensiunea graficului.

Unii termeni-1

- Fie R=(a,b) una dintre muchiile graficului. Atunci
vârfurile a și b se numesc terminale
vârfuri de margine;
- Vârfurile de capăt ale aceleiași muchii
numit vecin;
- Două muchii se numesc adiacente dacă au
vârf comun de capăt;
- Două muchii sunt numite multiple dacă
seturile vârfurilor lor de capăt coincid;
- O muchie se numește buclă dacă se termină
se potrivesc.

Unii termeni-2

- Gradul unui vârf V se notează cu deg(V)
se numește numărul de muchii, pentru
al cărui vârf este capătul;
- Un vârf se numește izolat dacă
ea nu este sfârșitul pentru nimeni
coaste;
- Un vârf se numește frunză dacă este
este terminal pentru exact unul
coaste. Pentru o foaie q, este evident că deg(q)=1.

Exemplu:

grade(C)=4
H1,…H4 - Frunze

Alt exemplu:

Orașele B și D sunt izolate
blaturi; Orașele G și E sunt frunze.

Graficul complet

Un grafic se numește complet dacă există
două vârfuri sunt conectate printr-o muchie.
Câte muchii are un grafic complet
comanda n?
Un grafic complet de ordin n are numărul de muchii
este egal cu Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Să demonstrăm...

Graficul complet cu două vârfuri
conține o margine - acest lucru este evident.
Înlocuiți n=2 în formula n*(n-1)/2
Primim:
n*(n-1)/2=1
Formula este corectă pentru n=2

Asumarea inducției

Să presupunem că formula este adevărată pentru
grafic cu k vârfuri.
Să demonstrăm că asta implică
validitatea formulei pentru grafic
cu (k+1) vârf.

Să mai adăugăm un vârf la graficul complet cu K vârfuri.

Și conectează-l cu primul K
culmi...

Primim:

Numărăm câte coaste avem...

K*(K-1)/2 + K
=
K*(K+1)/2
Se obține ultima expresie,
dacă în formula n*(n-1)/2 în loc de n
înlocuiește K+1.

Din asumarea corectitudinii
Urmează afirmația pentru n=k
valabilitatea declaraţiei la
n=k+1.
Teorema a fost demonstrată.

Exemple de grafice complete

Lămurire importantă

Perechile care definesc muchiile într-un grafic nedirecționat sunt neordonate (adică,
perechile (a,b) și (b,a) nu diferă)

Graficul dirijat

Dacă muchiile graficului sunt mulţimea
perechi ordonate (adică (a,b) ≠ (b,a)),
Se spune că graficul este direcționat.
(sau digraf)
Cum să dai orientare conceptului
sens vizual?
Foarte simplu - coastele sunt furnizate
săgeți (de la început până la sfârșit)!

Exemplu de digraf

Număr mixt

Un grafic mixt este un triplu (V, E, A).
V este mulțimea vârfurilor;
E este mulțimea de nedirecționate
coaste;
A este mulțimea muchiilor direcționate.
Apropo, marginile direcționate
se numesc arce.

Izomorfismul grafic

Să fie două grafice G1 și G2
Dacă există o corespondență unu-la-unu F
între vârfurile graficelor G1 și G2, astfel încât:
- dacă există o muchie (a,b) în graficul G1, atunci în graficul G2
există o margine (F(a),F(b))
- dacă există o muchie (p,q) în graficul G2, atunci în graficul G1
există o margine (F-1(p),F-1(q))
atunci graficele G1 și G2 se numesc izomorfe și
corespondența F este un izomorfism.

Clarificare

Pentru digrafe și grafice mixte
corespondenţa F trebuie să păstreze
orientarea arcului.

Condiție necesară pentru izomorfism

În ce condiţii între elemente
două mulţimi finite
setați unu-la-unu
conformitate?
Atunci și numai atunci, numărul de
elementele sunt aceleași.
O condiție necesară pentru izomorfism
grafice este același număr
culmi.

Este suficientă această condiție?

Nu, pentru că vârfurile pot fi
conectate în moduri diferite.

Sunt aceste grafice izomorfe?

Numărul de vârfuri este același -
conditia necesara este indeplinita...

Încercăm să construim o corespondență F...

Acesta nu este un izomorfism: G1 are o muchie (A, D),
iar imaginile acestor margini din G2 nu sunt conectate.

Inca o incercare...

Și acesta este un izomorfism!

Sunt aceste grafice izomorfe?

Din pacate, nu…

Din punct de vedere teoretic, doi
graficul izomorf este unul și același
același obiect (numai, poate, reprezentat diferit...)

Căi (lanțuri):

O cale (lanț) este o secvență
vârfuri:
a1, a2, … , an
unde vârfurile învecinate ai și ai+1
legate prin coaste.
Lungimea unei căi este numărul componentelor sale
coaste

Exemple de trasee:

(A, D, C) și (A, B, D) sunt căi. (A, B, C) nu este calea.

Noțiunea de cale pentru un digraf păstrează
putere, dar trebuie suplimentat -
culmi invecinate in
secvente
a1, a2, … , an
trebuie conectate prin arce.

Cicluri

Un ciclu este o cale a cărei inițială și
sfârșitul potrivirii vârfurilor.
Lungimea unui ciclu este numărul constituenților săi
coaste.
Un ciclu se numește simplu dacă marginile din el
nu se repetă.
Un ciclu se numește elementar dacă acesta
simplu și vârfurile din el nu se repetă.

Componente de conectivitate

Vârfurile unui graf arbitrar pot fi
împărțit în clase astfel încât pt
oricare două vârfuri ale aceleiași clase v1
și v2 există o cale de la v1 la v2
Aceste clase sunt numite componente
conectivitate.
Dacă graficul are exact o componentă
conexiune, atunci graficul este numit
conectat.

Reprezentarea automată a graficelor.

Matricea adiacentei

- Enumerăm vârfurile graficului G
numere întregi consecutive de la 1 la n;
- Construiește o masă pătrată n×n și
umple-l cu zerouri;
- Dacă există o margine de conectare
vârfurile i și j, apoi în pozițiile (i,j) și (j,i)
pune unități;
- Tabelul rezultat este numit
matricea de adiacență a graficului G.

Exemplu

Câteva proprietăți evidente ale matricei de adiacență

- Dacă un vârf este izolat, atunci rândul său și
coloana va fi complet nulă;
- Numărul de unități pe rând (coloană)
egală cu gradul corespunzătoare
blaturi;
- Pentru un grafic nedirecţionat, matricea
adiacența este simetrică
diagonala principală;
- Bucla corespunde unei unități pe care se află
diagonala principală.

Generalizare pentru un digraf

Matricea de adiacență pentru digraf
poate fi construit similar
fel, dar să ținem cont de ordine
vârfuri, puteți face acest lucru:
Dacă arcul provine de la vârful j și
intră în vârful k, apoi în poziția (j,k)
setați matricele de adiacență la 1 și în
poziţia (k, j) set -1.

Matricea de incidenta

- Enumerăm vârfurile graficului G
numere întregi consecutive de la 1 la
n;
- Construiește o masă dreptunghiulară cu
n rânduri și m coloane (coloane
corespund marginilor graficului);
- Dacă muchia j are un terminal
vârful k, apoi în poziție
(k,j) este setat la unu. In toate
în alte cazuri, este setat la zero.

Matricea de incidentă pentru un digraf

- Dacă j-al-lea arc provine de la vârful k,
atunci poziția (k,j) este setată la 1;
- Dacă arcul j intră în vârful k, atunci
în poziţia (k,j) pune -1.
- În alte cazuri, în poziţia (k, j)
rămâne zero.

Deoarece coloanele matricei
incidențele descriu margini, atunci
fiecare coloană poate să nu conţină
mai mult de două elemente diferite de zero

Un exemplu de matrice de incidență

Lista de coaste

Un alt mod de a reprezenta un grafic
– matrice bidimensională (lista de perechi).
Numărul de perechi este egal cu numărul de muchii
(sau arcuri).

Exemplu de listă de margini

Compararea diferitelor metode de prezentare

- Lista de margini este cea mai compactă și
matricea cu cea mai mică incidență
compact;
- Matricea de incidență este la îndemână când
căutarea ciclurilor;
- Matricea de adiacenta mai usoara
restul sunt în uz.

Traversarea graficului

Parcurgerea unui grafic este enumerarea acestuia.
vârfuri astfel încât fiecare vârf
vazut o data.

Acord-1

Înainte de a efectua o căutare a unui grafic
cu n vârfuri, creați un tablou Chk
de n elemente și umple-l
zerouri.
Dacă Chk[i] = 0, atunci i-lea vârf Mai mult
nevizuite.

Acordul-2

Să obținem structura datelor
(depozitar), în care vom
memorează vârfurile în proces
ocolire. Interfață de stocare
ar trebui să ofere trei funcții:
- Aduceți vârful;
- Extras blat;
- Verificați dacă depozitul este gol;

Acord-3

Când vârful j este plasat în
depozit, este marcat ca
vizualizat (adică instalat
Chk[j]=1)

Algoritmul de ocolire-1

1) Luăm un vârf inițial arbitrar,
imprimați-l și puneți-l în depozit;

3) Luați vârful Z din depozit;
4) Dacă există un vârf Q asociat cu Z și nu
verificat, apoi revenim pe Z în depozit,
magazin Q, imprimă Q;
5) Treceți la pasul 2

Bypass algoritm-2

1) Luăm un vârf inițial arbitrar și
îl punem în depozit;
2) Depozitul este gol? Dacă DA - sfârșitul;
3) Luați vârful Z din stocare, imprimați și
șterge din stocare;
4) Punem în depozit toate vârfurile,
asociat cu Z și încă nemarcat;
5) Treceți la pasul 2

Ce structuri de date sunt potrivite ca stocare?

- Stivă (PUSH - aduceți; POP - eliminați)
- Coadă (ENQUE - introduceți; DEQUE -
extrage)
Ambele structuri permit verificarea
disponibilitatea datelor.

Algoritmul-1 combinat cu stiva
se numește traversare în adâncime
Algoritmul-2 combinat cu o coadă
se numește mai întâi latimea

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 în plan printr-un set de puncte corespunzătoare vârfurilor, care sunt conectate prin linii corespunzătoare muchiilor.

O cale de grafic este o succesiune de vârfuri și muchii. O rută este închisă (ciclică) dacă vârfurile de început și de sfârșit sunt aceleași. Un traseu este o cale simplă 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 al unui grafic

Construcția unui arbore întins conectat de greutate minimă. Algoritmul lui Kruskal Toate muchiile sunt eliminate din grafic și se obține un subgraf care se întinde, unde toate vârfurile sunt izolate. Fiecare vârf este plasat într-un subset singleton. Marginile sunt sortate în ordine crescătoare a greutăților. Marginile 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 cu un singur element, apoi sunt combinate într-o nouă submulțime conectată; 2) unul dintre vârfuri aparține unei submulțimi conexe, iar 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 cu greutate minimă pentru graficul GG Acțiuni efectuate Setul de vârfuri Graficul 1 Construiți un subgraf de întindere cu izolate și vârfuri Obținem 5 submulțimi singleton: (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2 Găsiți muchia greutății minime (R 15) și adăugați-o la subgraful spanning Formează o submulțime conexă de vârfuri: (V 1,V 5 ). Salvați submulțimile (V 2 ), (V 3 ), (V 4 )

Acțiuni efectuate Set de vârfuriGrafic 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 vârful la submulțimea conexă: (V 1,V 5, V 4 ). Salvăm submulțimile (V 2 ), (V 3 ) 4 Printre cele rămase, găsiți marginea greutății minime (R 23) și adăugați-o la subgraful spanning Formează o nouă submulțime conexă de vârfuri: (V 2,V 3 ) . Păstrăm primul submulțime conectată (V 1,V 5, V 4 ).

Acțiuni efectuate Setul de vârfuriGrafic 5Dintre cele rămase, găsiți marginea greutății minime (R 25) și adăugați-o la subgraful de întindere Combină submulțimile într-o singură submulțime conectată (V 1,V 5, V 4,V 2,V 3 ). 6 Restul marginilor nu sunt incluse în grafic, deoarece toate vârfurile lor aparțin deja aceleiași mulțimi conectate.

Acțiuni efectuate Setul de noduriGraficul 7A fost obținut un grafic care: este un grafic de întindere (toate nodurile sunt incluse); conectat (toate vârfurile pot fi conectate prin rute); arbore (fără cicluri); are o greutate minima. 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, care corespunde cu numărul de margini nu într-un copac.

Declararea variabilelor Două matrice întregi de cinci elemente X și Y pentru stocarea coordonatelor vârfurilor graficului Matricea întregi bidimensionale R pentru stocarea greutăților muchiilor graficului Variabile întregi i, n și k pentru contoare de ciclu Variabila întreagă S pentru stocarea sumei greutăților muchiilor arborelui de greutate minima

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