Deși, există o mulțime de tipuri diferite de grafice în funcție de numărul de vârfuri, numărul de muchii, interconectivitate și structura lor generală, unele dintre astfel de tipuri comune de grafice sunt următoarele:
1. Graficul nul
A grafic nul este un grafic în care nu există muchii între vârfurile sale. Un graf nul se mai numește și graf gol.
Exemplu
Un graf nul cu n vârfuri este notat cu Nn.
2. Grafic trivial
A grafic trivial este graficul care are un singur vârf.
Exemplu
În graficul de mai sus, există un singur vârf „v” fără nicio muchie. Prin urmare, este un grafic trivial.
3. Grafic simplu
A grafic simplu este graficul nedirecţionat cu fără margini paralele și fără bucle .
Un grafic simplu care are n vârfuri, gradul fiecărui vârf este de cel mult n -1.Exemplu
În exemplul de mai sus, Primul graf nu este un graf simplu, deoarece are două muchii între vârfurile A și B și are și o buclă.
Al doilea grafic este un grafic simplu, deoarece nu conține nicio buclă și muchii paralele.
4. Grafic nedirecționat
Un grafic nedirecţionat este un grafic ale cărui muchii sunt nedirijate .
Exemplu
În graficul de mai sus, deoarece nu există muchii direcționate, este un grafic nedirecționat.
5. Graficul Dirijat
A grafic dirijat este un grafic în care marginile sunt îndreptate prin săgeți.
Graficul direcționat este cunoscut și ca digrafe .
Exemplu
În graficul de mai sus, fiecare margine este direcționată de săgeată. O muchie direcționată are o săgeată de la A la B, înseamnă că A este legat de B, dar B nu este legat de A.
6. Completați graficul
Se numește un grafic în care fiecare pereche de vârfuri este unită de exact o muchie grafic complet . Conține toate marginile posibile.
Un grafic complet cu n vârfuri conține exact nC2 muchii și este reprezentat de Kn.
Exemplu
În exemplul de mai sus, deoarece fiecare vârf din grafic este conectat cu toate vârfurile rămase prin exact o muchie, prin urmare, ambele grafice sunt grafice complete.
7. Grafic conectat
A graficul conectat este un grafic în care putem vizita de la orice vârf la orice alt vârf. Într-un graf conectat, există cel puțin o muchie sau o cale între fiecare pereche de vârfuri.
Exemplu
În exemplul de mai sus, putem traversa de la orice vârf la orice alt vârf. Înseamnă că există cel puțin o cale între fiecare pereche de vârfuri, prin urmare, este un graf conectat.
8. Grafic deconectat
A grafic deconectat este un grafic în care nu există nicio cale între fiecare pereche de vârfuri.
Exemplu
Graficul de mai sus constă din două componente independente care sunt deconectate. Deoarece nu este posibil să se viziteze de la vârfurile unei componente la vârfurile altor componente, prin urmare, este un grafic deconectat.
9. Graficul obișnuit
A Graficul obișnuit este un grafic în care gradul tuturor vârfurilor este același.
Dacă gradul tuturor vârfurilor este k, atunci se numește graf k-regular.
Exemplu
În exemplul de mai sus, toate vârfurile au gradul 2. Prin urmare se numesc 2- Graficul obișnuit .
10. Graficul ciclic
Un grafic cu „n” vârfuri (unde, n>=3) și „n” muchii care formează un ciclu de „n” cu toate muchiile sale este cunoscut ca graficul ciclului .
Un grafic care conține cel puțin un ciclu în el este cunoscut sub numele de a grafic ciclic .
În graficul ciclului, gradul fiecărui vârf este 2.
Graficul ciclului care are n vârfuri este notat cu Cn.
împărțit prin șir de caractere java
Exemplul 1
În exemplul de mai sus, toate vârfurile au gradul 2. Prin urmare, toate sunt grafice ciclice.
Exemplul 2
Deoarece graficul de mai sus conține două cicluri, prin urmare, este un grafic ciclic.
11. Graficul aciclic
Un grafic care nu conține niciun ciclu în el se numește un grafic aciclic .
Exemplu
Deoarece graficul de mai sus nu conține niciun ciclu în el, prin urmare, este un grafic aciclic.
12. Grafic bipartit
A grafic bipartit este un grafic în care mulțimea de vârfuri poate fi împărțită în două seturi, astfel încât muchiile să meargă doar între seturi, nu în interiorul lor.
Un graf G (V, E) se numește graf bipartit dacă mulțimea sa de vârfuri V(G) poate fi descompusă în două submulțimi disjunse nevide V1(G) și V2(G) în așa fel încât fiecare muchie e ∈ E (G) are ultima articulație în V1(G) și celălalt ultim punct în V2(G).
Partiția V = V1 ∪ V2 este cunoscută ca bipartiție a lui G.
Exemplul 1
Exemplul 2
13. Graficul bipartit complet
A grafic bipartit complet este un grafic bipartit în care fiecare vârf din primul set este unit cu fiecare vârf din al doilea set de exact o muchie.
Un graf bipartit complet este un graf bipartit care este complet.
Complete Bipartite graph = Bipartite graph + Complete graph
Exemplu
Graficul de mai sus este cunoscut sub numele de K4,3.
14. Graficul stelar
Un graf stea este un graf bipartit complet în care n-1 vârfuri au gradul 1 și un singur vârf are gradul (n -1). Aceasta arată exact ca o stea în care (n - 1) vârfuri sunt conectate la un singur vârf central.
Un grafic stea cu n vârfuri este notat cu Sn.
Exemplu
În exemplul de mai sus, din n vârfuri, toate (n-1) vârfuri sunt conectate la un singur vârf. Prin urmare, este un grafic stea.
15 Grafic ponderat
Un grafic ponderat este un grafic ale cărui margini au fost etichetate cu unele greutăți sau numere.
Lungimea unei căi într-un grafic ponderat este suma greutăților tuturor muchiilor din cale.
Exemplu
În graficul de mai sus, dacă calea este a -> b -> c -> d -> e -> g, atunci lungimea căii este 5 + 4 + 5 + 6 + 5 = 25.
16. Multi-graf
Un grafic în care există mai multe muchii între orice pereche de vârfuri sau există muchii de la un vârf la el însuși (buclă) se numește multi - grafic .
Exemplu
În graficul de mai sus, setul de vârfuri B și C sunt conectate cu două muchii. În mod similar, seturile de vârfuri E și F sunt conectate cu 3 muchii. Prin urmare, este un grafic multiplu.
17. Graficul planar
A grafic planar este un grafic pe care îl putem trasa într-un plan în așa fel încât să nu se încrucișeze două margini ale acestuia decât la un vârf la care sunt incidente.
Exemplu
Graficul de mai sus poate părea să nu fie plan, deoarece are muchii care se încrucișează. Dar putem redesena graficul de mai sus.
Cele trei desene plane ale graficului de mai sus sunt:
Cele trei grafice de mai sus nu constau din două muchii care se încrucișează și, prin urmare, toate graficele de mai sus sunt plane.
18. Grafic non-planar
Un graf care nu este un graf plan se numește graf non-plan. Cu alte cuvinte, un grafic care nu poate fi desenat fără cel puțin o pereche de muchii de încrucișare este cunoscut sub numele de grafic neplanar.
Exemplu
Graficul de mai sus este un grafic non-plan.