Pe această pagină veți găsi exemple gata făcute în teoria graficelor (secțiunea de matematică discretă). Teoria grafurilor are originile în secolul al 18-lea, când Euler a scris lui celebru articol pe poduri Konigsberskih (a se vedea. Soluții pentru algoritmul Euler). În prezent, realizările teoriei grafurilor sunt folosite în construcții, programare, inginerie electrică, sociologie, economie, biochimie, telecomunicații și planificarea comunicațiilor de transport, psihologie etc.
Ce tipuri de sarcini sunt rezolvate de către studenți?
Problemele rezolvate în cadrul teoriei grafurilor pot fi împărțite în mai multe grupe:
- Definiția grafului și a proprietăților acestuia. Obiective pentru construcția graficului de către un număr predeterminat de noduri și muchii, iar construirea matricei adiacenta de incidență, calculul caracteristicilor de bază ale graficului (conectivității, simplitate, Euler, plinătate, bipartiție, regularitatea graficului, și altele asemenea). Verificarea planarității și izomorfismului graficelor.
- Acțiuni cu grafice. Adăugați și eliminați vârfuri și marginile, componentele de conectivitate, îmbinarea vârfurilor, alăturați-vă, intersectați, uniți-vă și produsul cartezian al graficelor. Construirea unui grafic complementar.
- Trasee, lanțuri și cicluri, contururi. Lanțul Eulerian și ciclul Hamiltonian și verificarea graficului pentru îndeplinirea acestor proprietăți.
- Calculul caracteristicilor grafice. Distanțe: diametrul graficului, centrul graficului, raza graficului. Calculul numărului ciclomatic și cromatic.
- Sarcini pe grafice. Problema celei mai scurte căi (algoritmul Dijkstra, Bellman, construirea arborelui traseului). Problema construirii unui arbore minim spanning (algoritm Kruskal). Problema debitului maxim în rețea (algoritmul Ford-Folkerson). Problema de colorare a unui grafic.
- Studiul copacilor (tipuri speciale de grafice fără cicluri). Copacii sunt utilizați în criptare, programare și multe alte domenii aplicate.
Sarcini pentru grafice cu o soluție online
Sarcina 1. Construiește un grafic al relației "x + y ≤7" pe setul M =. Determinați proprietățile sale.
Problema 2. Găsiți cele mai scurte căi din digraph de la primul vârf la toate celelalte, folosind algoritmul Dijkstra. Construiți un copac cu cele mai scurte căi.
Problema 3. Găsiți debitul maxim și reducerea minimă în rețeaua de transport, folosind algoritmul Ford-Fulkerson (note de algoritm de plasare) construi un grafic trepte. Verificați îndeplinirea condiției de debit maxim a fluxului construit complet. Sursa este vârful 1, scurgerea este vârful 8.
Sarcina 4. Construiți un arbore spanning de greutate minimă utilizând algoritmii Prima și Kruskal. Folosind matricea Kirchhoff, găsiți numărul copacilor (non-izomorf) ce se întind pe arbori folosind pachete matematice de calculator (de exemplu, MathCAD, Mathematica, MatLab).
Problema 5. Necesită a crea matricea structurală pentru digraph (sau grafic) și tehnicile de algebrei booleene, găsiți tot drumul de la $ P_ $ $ i $ noduri nod $ j $, apoi căutați toate secțiunile $ S_ $ între aceste noduri. În această sarcină (pentru a evita posibilele ambiguități desen grafic) indică toate marginile îndreptate și înregistrarea (2-4) înseamnă că cele două asociate vertex 4 minute, și nici un feedback. Să ne amintim că, pentru găsirea unor rute de vertex $ i $ a vertex $ j $ nevoie dezvăluie structurale matrice $ $ M- minor (aducerea la zero a matricei structurale cu numărul de rând $ j $ și coloana numărul $ i $). Secțiunile sunt negarea căilor (conjuncția se schimbă în disjuncție și invers).
Problema 6. Pentru graficul $ G = (X, U) $, efectuați următoarele:
1.1. construi:
- matricea adjacency,
- incidența matricei.
1.2. Determinați gradele pentru toate nodurile $$ ale unui grafic dat.
Problema 7. Găsiți toate căile cele mai scurte din digraf folosind algoritmul Floyd.
Problema 8. Am dat $ G (X, HX) $
$ X = $,
GC:
Gx1 =, Гx2 =, Гх3 =, Гх4 =, Гх5 =.
Determinați numărul cromatic și ciclomatic al unui grafic dat.
Problema 9. Presupunând că acest grafic este nedirecționat, denumiți vârfurile și marginile sale prin simboluri diferite și determinați.
3.1. Grade locale și medii ale fiecărui vârf sub forma unei structuri de apropiere;
3.2. Construiți matrici de incidență și contiguitate;
3.3. Luați în considerare părțile din grafic. Dați exemple de sugraf care acoperă sugraful. Afișați un subgraf format din trei noduri. Câte subgrafe pot fi găsite în această coloană? Arătați exemple de intersecție și unire a unor părți ale graficului;
3.4. Dați exemple de traseu ciclic, lanț, lanț simplu. Încercați să găsiți ciclul Euler;
3.5. Determinați centrul, diametrul și raza graficului.
Presupunând că graficul este orientat, determină
3.6. Gradele de vârfuri
3.7. Matrice de incidență și contiguitate.
3.8. Dați exemple de o cale, un lanț orientat, un lanț simplu, un contur, un ciclu și un ciclu simplu.
Soluția teoriei grafurilor la cerere
Realizăm soluția de probleme, control și lucrări practice pe orice secțiune a teoriei grafurilor. Proiectarea detaliată, tabele, desene, explicații, este posibilă scrierea de programe în limbi de programare (pentru algoritmi pe grafice) sau utilizarea programelor speciale. Rezolvarea problemelor economice asociate teoriei grafurilor.
Costul exemplului este de 100 de ruble. înregistrarea se face în Word, o perioadă de 2 zile. De asemenea, asistăm la trecerea testelor pe grafice.
Ordonați cu ușurință soluția problemelor teoriei grafurilor
Articole similare
Trimiteți-le prietenilor: