Please enable JavaScript.
Coggle requires JavaScript to display documents.
Tipos de grafos - Coggle Diagram
Tipos de grafos
Tipos
Regular
Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau. O grafo G4, por exemplo, é dito ser um grafo regular-3 pois todos os seus vértices tem grau 3.
Completo
Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo. Um grafo Kn possui o número máximo possível de arestas para um dados n. Ele é, também regular-(n-1) pois todos os seus vértices tem grau n-1.
Bipartido
Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro de V2.
O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém duas partições de 3 vértices cada. Ele é completo pois todos os vértices de uma partição estão ligados a todos os vértices da outra partição.
-
Grafo Rotulado
Um grafo G(V,A) é dito ser rotulado em vértices (ou arestas) quando a cada vértice (ou aresta) estiver associado um rótulo. G5 é um grafo rotulado
Grafo Valorado
Um grafo G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números.
Multigrafo
Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas arestas entre pares de vértices de G. No grafo G8, por exemplo, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo.
Grafo complementar
Seja G um grafo simples. Definimos o grafo complementar de G, denotado por Ḡ , da seguinte maneira: V ( Ḡ ) = V (G ) e E ( Ḡ ) = {xy ; xy /∈ E (G )}.
-
Subgrafo
Um grafo Gs(Vs, As) é dito ser subgrafo de um grafo G(V,A) quando Vs ⊆ V e As ⊆ A. O grafo G9, por exemplo, é subgrafo de G8.
Um subgrafo G' (representado por H) é um subgrafo induzido de G se, para qualquer par de vértices x e y de H, xy é uma aresta de H se e somente se xy é uma aresta de G. Em outras palavras, H é um subgrafo induzido de G se ele tem todas as arestas que aparecem em G sobre o mesmo conjunto de vértices. Se o conjunto de vértices de H é um subconjunto S de V(G), então H pode ser escrito como G[S] e diz-se ser induzido por S.