fluxuri ce Teoria rețelelor au luat naștere din luarea în considerare a problemelor reale, cum ar fi transportul de mărfuri prin sistemul feroviar, de pompare de petrol prin conducte, gestionarea inventarului, și așa mai departe. E. curge Înainte de teorie rezumate în rețele, prezintă unele definiții ale teoriei graficului.
Count - o combinație de două seturi: un set de puncte, numite noduri. și o multitudine de nervuri. Fiecare element este o pereche ordonată de elemente ale setului. sus și numite puncte finale sau margini și capete. Un grafic este finit. în cazul în care o pluralitate de R și finit.
Această definiție a graficului trebuie să fie completate într-o privință importantă. În definiția marginilor pot fi luate sau nu sunt luate în considerare ordinea celor două capete ale lui. Dacă această comandă nu este esențială, adică. E. În cazul în care. atunci spunem că există un neorientirovannoerebro; în cazul în care această comandă este semnificativă, aceasta se numește o margine direcționată (marginea orientată este adesea numit arc). În acest din urmă caz este, de asemenea, numit nodul inițial. și - final Pinnacle rebraa. Un grafic este neorientat. în cazul în care fiecare dintre marginile sale neorientat și orientate. Dacă se concentreze toate marginile sale. În unele cazuri, considerate în mod natural grafice mixte, cu ambele nervuri și neorientate.
Nervurile au aceleași vârfuri de capăt se numesc paralele. noduri de capăt nervură care coincid, se numește buclă. Acesta este de obicei considerat a fi non-orientate. Nodurile și marginile incidente numit unul de altul, în cazul în care nodul este un capăt la această margine. Vertex nu incident de la orice margine se numește izolat. Grafic constând numai din vârfuri izolate, numite graficul nul. Două vârfuri, un punct final pentru o margine sunt numite noduri adiacente. Două muchii incidente la același vertex se numesc adiacente.
Numărul de muchii incidente la un nod. Vom fi notat cu. Acest număr se numește gradul local sau un grad în graficul de sus. În cazul unui grafic direcționat G denotă numărul de muchii, respectiv vârful și constituentul acestuia. Aceste numere sunt numite stepenyamiG locale în. Dacă toate numerele sunt finite, graficul este local finit. gradul 1 nod este numit agățat. Vertex de grad 0 este numit izolat.
Fig. 14.1 și - margini paralele; - o buclă; Nodurile și marginile sunt incidente unele cu altele; - nodurile adiacente - nodurile adiacente; gradul unui nod este egal cu trei - partea superioară a agățat - izolate.
Teorema14.1.V graf G este suma gradelor de toate nodurile sale - un număr chiar egal cu de două ori numărul de muchii :. unde n - numărul de noduri, m - numărul muchiilor sale.
Teorema14.2. Orice număr impar de noduri ale grafului, adică. E. Nodurile având grad impar este chiar.
Un grafic G este declarat a fi completă. dacă oricare două vârfuri distincte legate de margine și nu conține margini paralele. GrafaG plus este graficul cu aceleași vârfuri ca graful G, care conțin numai acele margini pe care doriți să le adăugați la grafului G. Pentru a obține un grafic complet. Un grafic G este declarat a fi plat. în cazul în care acesta poate fi reprezentat pe un plan, astfel încât toate muchiile de intersecție sunt nodurile sale.
Fig. 14.2 prezintă următoarele domenii: - grafic complet cu cinci noduri - un grafic cu cinci noduri, complementul graficului.