Teoria grafurilor este un domeniu al matematicii, o caracteristică a căruia este o abordare geometrică a studiului obiectelor. Teoria grafurilor și a algoritmilor pe grafice este larg utilizată în programare. Noțiunea de grafic și conceptul de relație sunt concepte egale. Teoria graficelor oferă un limbaj foarte convenabil pentru descrierea modelelor software. Imagini vă permit să imediat „văzut“ inima problemei la un nivel intuitiv, care completează și decorarea plictisitoare dovezi textuale raționale și formule complexe. Primele sarcini ale teoriei grafurilor au fost legate de rezolvarea problemelor matematice de divertisment și de puzzle-uri.
Prima lucrare pe teoria grafurilor Euler apartine lui A (1736god), deși termenul „Graficul“ a fost introdus pentru prima dată în 1936 de matematicianul maghiar Denes Konig.
Un grafic G (V, X) este o pereche de două seturi finite: setul de puncte și setul de linii care leagă câteva perechi de puncte.
Punctele sunt numite noduri sau noduri ale graficului, marginile liniilor.
Fie G (V, X) graficul, unde V = 1. V2 ...> este mulțimea vârfurilor sale și X (V1, V2) marginea sa.
Dacă elementele lui X sunt tratate ca perechi neordonate, atunci se spune că graficul este nedirecționat. iar perechile sunt numite coaste. Dacă elementele lui E sunt considerate ordonate, atunci graficul este orientat. iar perechile sunt arce.
Dacă o margine a graficului G unește două dintre vârfurile sale, atunci se spune că această margine este incidentă pentru ei.
Două vârfuri ale unui grafic sunt considerate a fi învecinate dacă există un incident marcat cu ele.
Se spune că două margini sunt adiacente dacă au un vârf comun.
-vârfurile adiacente - A și B, A și C.
- vârfurile A și C care se încadrează la marginea x3
Dacă graficul are o margine a cărei început și sfârșit coincid, atunci această margine se numește o buclă.
Graficul G (V, E) poate avea marginile cu perechi identice de forma X (V, W).
Astfel de margini sunt numite multiple sau paralele.
Pe figură, muchiile multiple x1 (A, B) și x2 (A, B)
Numărul de perechi identice ale formei x (V, W) se numește multiplicitatea marginii (V, W).
În figura 3, marginea AS are o multiplicitate egală cu 3, iar marginea AB este o multiplicitate egală cu 2.
2. Numărul de margini care se încadrează în vârful A se numește gradul acestui vârf și se notează deg (A) (din gradul englez).
Dacă vârful este incident cu o buclă, atunci el contribuie la o putere de două, deoarece ambele capete ajung la acest vârf.
În figura deg (A) = 5, deg (B) = 2, deg (C) = 3
Un vârf al unui grafic cu grad egal cu zero este numit izolat.
Un grafic constând din vârfuri izolate este numit graf zero. Pentru graficul nul X = t.
Un vârf al unui grafic care are un grad egal cu 1 este numit agățat
În graficul G (V, E), suma gradelor tuturor vârfurilor este un număr egal de două ori numărul de margini ale graficului:
unde n = V este numărul de vârfuri, m = X este numărul de margini ale graficului.
Se spune că un vârf este chiar dacă gradul său este un număr par.
Un vertex se numește ciudat dacă gradul său este un număr impar.
În figura 3, vârful B este egal. iar nodurile A și C sunt ciudate.
Numărul de vârfuri ciudate ale oricărui grafic este egal.
Corolar. Este imposibil să se elaboreze un grafic cu un număr impar de vârfuri ciudate.
4. Un grafic în care toate margini posibile nu sunt construite se numește un grafic incomplet
Un grafic în care oricare două dintre vârfurile sale diferite sunt conectate printr-o singură margine se numește un grafic complet.
Un grafic complet este definit numai de vârfurile sale
Dacă graficul complet are n noduri, atunci acesta va avea
graficul complet din Fig.
Articole similare
Trimiteți-le prietenilor: