Subgrafo

Origem: Wikipédia, a enciclopédia livre.
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,[1] 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.

Definição[editar | editar código-fonte]

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

1- V’ V

2- A' A

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

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

Outras definições correlatas[editar | editar código-fonte]

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[2]

Referências

  1. Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8 
  2. Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. p. 24. ISBN 0-914894-21-8