Embora existam muitos tipos diferentes de gráficos, dependendo do número de vértices, número de arestas, interconectividade e sua estrutura geral, alguns desses tipos comuns de gráficos são os seguintes:
1. Gráfico Nulo
A gráfico nulo é um grafo no qual não há arestas entre seus vértices. Um gráfico nulo também é chamado de gráfico vazio.
Exemplo
Um gráfico nulo com n vértices é denotado por Nn.
2. Gráfico Trivial
A gráfico trivial é o gráfico que possui apenas um vértice.
Exemplo
No gráfico acima, existe apenas um vértice 'v' sem nenhuma aresta. Portanto, é um gráfico trivial.
3. Gráfico Simples
A gráfico simples é o gráfico não direcionado com sem arestas paralelas e sem loops .
Um gráfico simples que possui n vértices, o grau de cada vértice é no máximo n -1.Exemplo
No exemplo acima, o primeiro gráfico não é um gráfico simples porque possui duas arestas entre os vértices A e B e também possui um loop.
O segundo gráfico é um gráfico simples porque não contém nenhum loop e arestas paralelas.
4. Gráfico não direcionado
Um gráfico não direcionado é um gráfico cujas arestas são não direcionado .
Exemplo
No gráfico acima, como não há arestas direcionadas, é um gráfico não direcionado.
5. Gráfico direcionado
A gráfico direcionado é um gráfico no qual as bordas são direcionadas por setas.
O gráfico direcionado também é conhecido como dígrafos .
Exemplo
No gráfico acima, cada aresta é direcionada pela seta. Uma aresta direcionada tem uma seta de A para B, significa que A está relacionado a B, mas B não está relacionado a A.
6. Gráfico completo
Um grafo no qual cada par de vértices é unido por exatamente uma aresta é chamado gráfico completo . Ele contém todas as arestas possíveis.
Um grafo completo com n vértices contém exatamente nC2 arestas e é representado por Kn.
Exemplo
No exemplo acima, como cada vértice do gráfico está conectado a todos os vértices restantes por exatamente uma aresta, ambos os gráficos são gráficos completos.
7. Gráfico Conectado
A gráfico conectado é um gráfico no qual podemos visitar de qualquer vértice a qualquer outro vértice. Em um grafo conectado, existe pelo menos uma aresta ou caminho entre cada par de vértices.
Exemplo
No exemplo acima, podemos percorrer de qualquer vértice para qualquer outro vértice. Isso significa que existe pelo menos um caminho entre cada par de vértices, portanto, é um grafo conectado.
8. Gráfico desconectado
A gráfico desconectado é um gráfico no qual não existe nenhum caminho entre cada par de vértices.
Exemplo
O gráfico acima consiste em dois componentes independentes que estão desconectados. Como não é possível visitar os vértices de um componente até os vértices de outros componentes, portanto, é um grafo desconectado.
9. Gráfico regular
A Gráfico regular é um gráfico em que o grau de todos os vértices é o mesmo.
Se o grau de todos os vértices for k, então ele é chamado de grafo k-regular.
Exemplo
No exemplo acima, todos os vértices têm grau 2. Portanto, eles são chamados de 2- Gráfico regular .
10. Gráfico Cíclico
Um gráfico com 'n' vértices (onde, n>=3) e 'n' arestas formando um ciclo de 'n' com todas as suas arestas é conhecido como gráfico de ciclo .
Um gráfico contendo pelo menos um ciclo é conhecido como gráfico cíclico .
No gráfico de ciclo, o grau de cada vértice é 2.
O gráfico de ciclo que possui n vértices é denotado por Cn.
primeiro portátil
Exemplo 1
No exemplo acima, todos os vértices têm grau 2. Portanto, todos são gráficos cíclicos.
Exemplo 2
Como o gráfico acima contém dois ciclos, é um gráfico cíclico.
11. Gráfico Acíclico
Um grafo que não contém nenhum ciclo é chamado de gráfico acíclico .
Exemplo
Como o gráfico acima não contém nenhum ciclo, é um gráfico acíclico.
12. Gráfico Bipartido
A gráfico bipartido é um gráfico no qual o conjunto de vértices pode ser particionado em dois conjuntos de modo que as arestas fiquem apenas entre os conjuntos, não dentro deles.
Um grafo G (V, E) é chamado de grafo bipartido se seu conjunto de vértices V(G) pode ser decomposto em dois subconjuntos disjuntos não vazios V1(G) e V2(G) de tal forma que cada aresta e ∈ E (G) tem sua última junta em V1(G) e outro último ponto em V2(G).
A partição V = V1 ∪ V2 é conhecida como bipartição de G.
Exemplo 1
Exemplo 2
13. Gráfico Bipartido Completo
A gráfico bipartido completo é um grafo bipartido em que cada vértice do primeiro conjunto é unido a cada vértice do segundo conjunto por exatamente uma aresta.
Um gráfico bipartido completo é um gráfico bipartido completo.
Complete Bipartite graph = Bipartite graph + Complete graph
Exemplo
O gráfico acima é conhecido como K4,3.
14. Gráfico Estelar
Um gráfico estrela é um gráfico bipartido completo no qual n-1 vértices têm grau 1 e um único vértice tem grau (n -1). Isto se parece exatamente com uma estrela onde (n - 1) vértices estão conectados a um único vértice central.
Um gráfico estrela com n vértices é denotado por Sn.
Exemplo
No exemplo acima, de n vértices, todos os (n-1) vértices estão conectados a um único vértice. Portanto, é um gráfico estrela.
15 Gráfico Ponderado
Um gráfico ponderado é um gráfico cujas arestas foram rotuladas com alguns pesos ou números.
O comprimento de um caminho em um gráfico ponderado é a soma dos pesos de todas as arestas do caminho.
Exemplo
No gráfico acima, se o caminho for a -> b -> c -> d -> e -> g então o comprimento do caminho é 5 + 4 + 5 + 6 + 5 = 25.
16. Multigráfico
Um gráfico no qual existem múltiplas arestas entre qualquer par de vértices ou existem arestas de um vértice para ele mesmo (loop) é chamado de multigráfico .
Exemplo
No gráfico acima, o conjunto de vértices B e C estão conectados por duas arestas. Da mesma forma, os conjuntos de vértices E e F estão conectados com 3 arestas. Portanto, é um multigráfico.
17. Gráfico Planar
A gráfico planar é um gráfico que podemos desenhar em um plano de tal forma que duas arestas dele não se cruzem, exceto em um vértice ao qual elas incidem.
Exemplo
O gráfico acima pode não parecer plano porque possui arestas que se cruzam. Mas podemos redesenhar o gráfico acima.
Os três desenhos planos do gráfico acima são:
Os três gráficos acima não consistem em duas arestas que se cruzam e, portanto, todos os gráficos acima são planares.
18. Gráfico Não Planar
Um gráfico que não é um gráfico planar é chamado de gráfico não planar. Em outras palavras, um grafo que não pode ser desenhado sem pelo menos um par de arestas cruzadas é conhecido como grafo não planar.
Exemplo
O gráfico acima é um gráfico não planar.