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
editarSeja 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
editarNa 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
- ↑ Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8
- ↑ Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. p. 24. ISBN 0-914894-21-8