Subgrafo

Em teoria dos grafos, um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G e o conjunto de arestas é um subconjunto do conjunto de arestas de G, ou seja, cuja relação de adjacência é um subconjunto de G restrita a esse subconjunto. Dizemos que um grafo G contém um outro grafo H se algum subgrafo de G é H ou é isomorfo a H.

Subgrafo

Definição

Seja G=(V, A). G’=(V’,A’) é dito ser subgrafo de G se:

1- V’ $\subseteq$ V

2- A' $\subseteq$ A

3- (V’,A’) é um grafo

• Se G’=(V’,A’) é subgrafo de G, para todo v $\in$ G se cumpre gr (G’,v)= gr (G, v) G2 é um subgrafo de G.

Outras definições correlatas

Subgrafo induzido

Na outra direção, um supergrafo de um grafo G é um grafo do qual G é um subgrafo.

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.

Um grafo que não contém H como um subgrafo induzido é dito ser H-livre.

Um grafo universal em uma classe de grafos K é um grafo simples em que cada elemento de K pode ser incorporado como um subgrafo.

Um subgrafo H é um subgrafo abrangente, ou factor, de um grafo G se ele tem o mesmo conjunto de vértices que G. Dizemos que H abrange G.

Um subgrafo H de um grafo G que contenha todos os vértices de G e seja uma árvore é chamado de árvore de extensão de G

Referências