Întrebări pentru repetare
1.Care este secțiunea de matematică discretă care studiază teoria grafică dedicată?
2. Care este diferența dintre grafice orientate și nedirecționate?
3. Dați definiția graficului?
4. Care este semnificația relației de incidență?
5. Este gradul local al topului grafic?
6. În ce caz sunt graficele numite izomorfe?
7. Care sunt modalitățile de specificare a graficelor?
8. Menționați diferențele dintre matricea incidenței și matricea de adjuvant?
9. Când este un grafic numit parte a unui grafic?
Se ia în considerare o diviziune a matematicii discrete care studiază teoria graficelor. Sunt date conceptele de bază ale teoriei grafurilor, cum ar fi un vârf, o margine, un grafic orientat și așa mai departe. Noțiunea de grad local este dată. Sunt prezentate modalitățile de specificare a graficelor cu demonstrația lor. Separat, sunt luate în considerare operațiile asupra unor părți ale graficului, precum și a graficelor și a relațiilor binare.
Scop. pentru a studia diferite tipuri de construcții grafice.
1 Luați în considerare conceptele traseului, traseului, lanțului și ciclului aplicate grafurilor.
2 Luați în considerare structura arborelui și graficul pădurii.
Fie G un grafic nedirecționat.
O rută în G este o secvență de margini M în care fiecare două muchii vecine au un vârf comun. În traseu, aceeași margine poate apărea de mai multe ori. Începutul rutei este incidentul de vârf la margine și nu incident; Sfârșitul rutei este incidental și nu incidental. Dacă acestea sunt multipli, este necesară o indicație suplimentară care dintre cele două vârfuri de incidente este considerată începutul (sfârșitul) traseului.
O rută în care începe și se încheie, adică închisă, se numește ciclică. O rută în care toate marginile sunt diferite este numită lanț. Un lanț care nu se intersectează, adică care nu conține vârfuri repetate, se numește un lanț simplu.
O rută ciclică este numită ciclu, dacă este un lanț și un ciclu simplu. când este un lanț simplu.
Se spune că vertexele sunt conectate dacă există un traseu M cu începutul și sfârșitul. Vitezele conectate prin traseu sunt de asemenea conectate printr-un lanț simplu. Relația de conectare a vârfurilor are proprietățile de echivalență și determină partiția setului de vârfuri ale unui grafic în subseturi disjuncte. Se spune că un grafic G este conectat. dacă toate nodurile sale sunt conectate. Prin urmare, toate subgrafurile G () sunt conectate și se numesc componente conectate ale graficului. Fiecare n-grafic se descompune în mod unic în suma directă a componentelor sale conectate
Fie G un grafic orientat.
O secvență de margini în care sfârșitul fiecărei margini anterioare coincide cu începutul următorului se numește calea (în care toate marginile merg de-a lungul orientării lor). Pe drum, aceeași margine poate apărea de mai multe ori. Începutul căii este începutul marginii, sfârșitul căii este sfârșitul marginii.
O cale este numită lanț orientat (sau pur și simplu un lanț) dacă fiecare margine are loc în ea nu mai mult de o dată și un lanț simplu. dacă orice vârf al lui G se încadrează la cel mult două dintre margini.
Schița este calea în care se află. Un contur este numit ciclu dacă este un lanț și un ciclu simplu atunci când este un lanț simplu. Dacă graficul conține cicluri, atunci acesta conține cicluri simple. Un grafic care nu conține cicluri se spune că este aciclic.
Un vertex este numit realizabil dintr-un vertex, dacă există o cale cu un început și un sfârșit.
Un digraph G se numește conectat dacă este conectat fără să țină cont de orientarea arcurilor și este puternic legat dacă există de la un vertex la altul o cale.
Numărul de margini ale unei rute (calea) se numește lungimea acesteia.
Distanța d (,) între noduri și n-graficul G este lungimea minimă a unui lanț simplu cu începutul și sfârșitul. Centrul este vârful n-grafului, din care maximul distanțelor față de alte noduri ar fi minim. Distanța maximă de la centrul G la vârful său se numește raza graficului r (G).
Ciclul Euler este un ciclu al unui grafic ce conține toate margini ale graficului. Graficul Euler este un grafic care are un ciclu Euler (ciclul Eulerian poate fi considerat o urmă a stiloului care traversează acest grafic fără a lăsa hârtie).
Teorema lui Euler. graful nedeterminat finit G al clasei Euler dacă și numai dacă este conectat și gradele tuturor vârfurilor sale sunt egale.
Lanțul Eulerian este un lanț care include toate marginile unui anumit n-graf finit dat, dar are un început și un sfârșit diferit. Pentru ca în n-graficul finit G să existe un lanț Eulerian, este necesar și suficient ca acesta să fie conectat și chiar în puterea tuturor nodurilor, cu excepția primului și ultimului (și trebuie să aibă puteri ciudate). Pentru ca ciclul Euler să existe în digraphul final, legătura acestuia este necesară și suficientă, precum și egalitatea gradei vârfurilor acestui grafic în ceea ce privește marginile de intrare și ieșire, adică .
Ciclul Hamiltonian este un ciclu simplu care trece prin toate vârfurile graficului examinat. Lanțul Hamiltonian este un lanț simplu care trece prin toate vârfurile graficului, cu începutul și sfârșitul la diferite noduri.
Articole similare
Trimiteți-le prietenilor: