Rezumat: Definiția unui grafic. Definiția digraph. Un grafic complet. Un grafic complet orientat. Graficul graficului bipartit. Gradul de vârf. Conectarea unui grafic. Probleme care duc la grafice
Definiția unui grafic
Un grafic este o pereche, unde este un set finit non-gol, numit noduri. a este o familie finită de perechi neordonate de elemente din (nu neapărat distincte), numite margini. Utilizarea cuvântului "familie" indică faptul că sunt permise mai multe muchii. Vom numi "setul de vârfuri". a este o familie de margini ale graficului. Fiecare margine a speciilor se spune că leagă vârfurile și fiecare bucla conectează vârful la sine.
Când sunt reprezentate grafice în cifre sau diagrame, segmentele pot fi rectilinie sau curbilinare; lungimile segmentelor și localizarea punctelor sunt arbitrare.
Definiția digraphului
O digrafa este o pereche, unde este un set finit de elemente nenumărate, denumite vârfuri, și este o familie finită de perechi ordonate de elemente, numite arce (sau muchii orientate). Arcul. în care vârful este primul element, iar vârful este al doilea, se numește arcul din. Observăm că arcele sunt diferite. Deși graficele și digrafurile sunt obiecte în esență diferite, în anumite cazuri graficele pot fi considerate ca diggrafe în care două arce orientate opus corespund fiecărei margini.
Graficul complet
Un grafic este numit complet. dacă fiecare două vârfuri diferite ale acestuia sunt conectate printr-o singură margine. Într-un grafic complet, fiecare dintre vârfurile sale aparține aceluiași număr de muchii. Pentru a specifica un grafic complet, este suficient să cunoașteți numărul de vârfuri. Un grafic complet cu vârfuri este de obicei marcat cu.
Graf. care nu este completă, poate fi transformată în complete cu aceleași vârfuri, adăugând marginile lipsă. Vârfurile graficului și marginile care sunt adăugate formează de asemenea un grafic. Un astfel de grafic este numit complementul unui grafic și îl denumește.
O adăugare a unui grafic este un grafic cu aceleași noduri ca și graful și cu acele și numai marginile care trebuie adăugate graficului pentru a obține un grafic complet.
Dacă graficul este complet sau nu, aceasta este caracteristica sa ca întreg.
Un grafic complet orientat
Un grafic complet orientat este un grafic. Fiecare pereche de noduri este conectată printr-o singură margine orientată. Dacă o direcție este îndepărtată de la fiecare margine a unui grafic complet orientat, se formează un grafic complet cu marginile neorientate.
Luați în considerare o competiție în care fiecare echipă joacă odată cu fiecare dintre echipele rămase. O astfel de competiție se numește un turneu circular sau un turneu cu un singur tur.
Dacă fiecare meci trebuie să se încheie neapărat cu victoria uneia dintre echipe, atunci turneul rotund este numit fără compromisuri. Un turneu circular, fără compromis, este organizat, de exemplu, în volei și baschet.
Fiecare turneu are un grafic complet orientat. în care vârfurile reprezintă comenzile și fiecare margine orientată exprimă relația "câștigată".
Trimiteți-le prietenilor: