Tuttavia, esistono molti tipi diversi di grafici a seconda del numero di vertici, del numero di bordi, dell'interconnettività e della loro struttura complessiva, alcuni di questi tipi comuni di grafici sono i seguenti:
1. Grafico nullo
UN grafico nullo è un grafo in cui non ci sono spigoli tra i suoi vertici. Un grafo nullo è anche detto grafo vuoto.
Esempio
Un grafo nullo con n vertici è denotato con Nn.
2. Grafico banale
UN grafico banale è il grafo che ha un solo vertice.
Esempio
Nel grafico sopra, c'è solo un vertice 'v' senza alcun bordo. Si tratta quindi di un grafico banale.
3. Grafico semplice
UN grafico semplice è il grafico non orientato con senza bordi paralleli E nessun loop .
Un grafo semplice che ha n vertici, il grado di ogni vertice è al massimo n -1.Esempio
Nell'esempio sopra, il Primo grafo non è un grafo semplice perché ha due spigoli tra i vertici A e B e ha anche un cappio.
Il secondo grafico è un grafico semplice perché non contiene alcun ciclo e spigoli paralleli.
4. Grafico non orientato
UN grafico non orientato è un grafico i cui bordi sono non diretto .
Esempio
Nel grafico sopra poiché non ci sono archi diretti, quindi è un grafico non orientato.
5. Grafico diretto
UN grafico diretto è un grafico in cui il i bordi sono diretti dalle frecce.
Il grafico diretto è anche noto come digrafi .
Esempio
Nel grafico sopra, ciascun bordo è diretto dalla freccia. Un bordo diretto ha una freccia che va da A a B, significa che A è correlato a B, ma B non è correlato ad A.
6. Grafico completo
Viene chiamato un grafo in cui ogni coppia di vertici è unita esattamente da un bordo grafico completo . Contiene tutti i bordi possibili.
Un grafo completo con n vertici contiene esattamente nC2 archi ed è rappresentato da Kn.
Esempio
Nell'esempio sopra, poiché ciascun vertice del grafico è collegato a tutti i restanti vertici esattamente attraverso un bordo, entrambi i grafici sono grafici completi.
7. Grafico connesso
UN grafico connesso è un grafo in cui possiamo visitare da qualsiasi vertice a qualsiasi altro vertice. In un grafo connesso esiste almeno un bordo o percorso tra ogni coppia di vertici.
Esempio
Nell'esempio sopra, possiamo passare da un vertice qualsiasi a qualsiasi altro vertice. Significa che esiste almeno un percorso tra ogni coppia di vertici, quindi è un grafo connesso.
8. Grafico sconnesso
UN grafico sconnesso è un grafo in cui non esiste alcun percorso tra ogni coppia di vertici.
Esempio
Il grafico sopra è costituito da due componenti indipendenti che sono disconnessi. Poiché non è possibile visitare dai vertici di un componente ai vertici degli altri componenti, si tratta di un grafo sconnesso.
9. Grafico regolare
UN Grafico regolare è un grafico in cui il grado di tutti i vertici è lo stesso.
Se il grado di tutti i vertici è k, allora il grafo è detto k-regolare.
Esempio
Nell'esempio sopra, tutti i vertici hanno grado 2. Pertanto sono chiamati 2- Grafico regolare .
10. Grafico ciclico
Un grafo con 'n' vertici (dove n>=3) e 'n' spigoli che formano un ciclo di 'n' con tutti i suoi spigoli è noto come grafico del ciclo .
Un grafico contenente almeno un ciclo è noto come a grafico ciclico .
Nel grafico del ciclo, il grado di ciascun vertice è 2.
Il grafo ciclo che ha n vertici è indicato con Cn.
installazione esperta
Esempio 1
Nell'esempio sopra, tutti i vertici hanno grado 2. Pertanto sono tutti grafici ciclici.
Esempio 2
Poiché il grafico sopra contiene due cicli, è un grafico ciclico.
11. Grafico aciclico
Un grafo che non contiene alcun ciclo è chiamato an grafico aciclico .
Esempio
Poiché il grafico sopra non contiene alcun ciclo, è un grafico aciclico.
12. Grafico bipartito
UN grafico bipartito è un grafo in cui l'insieme dei vertici può essere partizionato in due insiemi in modo tale che gli archi vadano solo tra gli insiemi, non al loro interno.
Un grafo G (V, E) si dice bipartito se il suo insieme di vertici V(G) può essere scomposto in due sottoinsiemi disgiunti non vuoti V1(G) e V2(G) in modo tale che ciascun arco e ∈ E (G) ha il suo ultimo giunto in V1(G) e l'altro ultimo punto in V2(G).
La partizione V = V1 ∪ V2 è detta bipartizione di G.
Esempio 1
Esempio 2
13. Grafico bipartito completo
UN grafico bipartito completo è un grafo bipartito in cui ciascun vertice del primo insieme è unito a ciascun vertice del secondo insieme esattamente da un arco.
Un grafo bipartito completo è un grafo bipartito completo.
Complete Bipartite graph = Bipartite graph + Complete graph
Esempio
Il grafico sopra è noto come K4,3.
14. Grafico stellare
Un grafo stellare è un grafo bipartito completo in cui n-1 vertici hanno grado 1 e un singolo vertice ha grado (n -1). Sembra esattamente una stella in cui (n - 1) vertici sono collegati a un singolo vertice centrale.
Un grafico stellare con n vertici è indicato con SN.
Esempio
Nell'esempio sopra, su n vertici, tutti gli (n-1) vertici sono collegati a un singolo vertice. Quindi, è un grafico stellare.
15 Grafico ponderato
Un grafico ponderato è un grafico i cui bordi sono stati etichettati con alcuni pesi o numeri.
La lunghezza di un percorso in un grafico pesato è la somma dei pesi di tutti gli archi del percorso.
Esempio
Nel grafico sopra, se il percorso è a -> b -> c -> d -> e -> g allora la lunghezza del percorso è 5 + 4 + 5 + 6 + 5 = 25.
16. Multigrafico
Un grafo in cui ci sono più bordi tra qualsiasi coppia di vertici o ci sono bordi da un vertice a se stesso (ciclo) è chiamato a multi-grafico .
Esempio
Nel grafico sopra, gli insiemi di vertici B e C sono collegati con due bordi. Allo stesso modo, gli insiemi di vertici E ed F sono collegati con 3 bordi. Pertanto, è un multi grafico.
17. Grafico planare
UN grafico planare è un grafico che possiamo disegnare su un piano in modo tale che due suoi bordi non si incrocino se non in un vertice a cui sono incidenti.
Esempio
Il grafico sopra potrebbe non sembrare planare perché ha i bordi che si incrociano. Ma possiamo ridisegnare il grafico sopra.
I tre disegni piani del grafico sopra sono:
I tre grafici precedenti non sono costituiti da due bordi che si incrociano e pertanto tutti i grafici precedenti sono planari.
18. Grafico non planare
Un grafo che non è planare è detto grafo non planare. In altre parole, un grafo che non può essere disegnato senza almeno un paio di bordi incrociati è noto come grafo non planare.
Esempio
Il grafico sopra è un grafico non planare.