Seja G=(V,A) um grafo.
Subgrafos
Dado um subconjunto V1 de vértices em V,
chama-se subgrafo de G gerado por V1 ao
grafo G1=(V1,A1)
onde A1 é formado por todas as arestas de
A com ambas as extremidades em V1.
Diz-se simplesmente que G1 é um subgrafo de G
quando para algum subconjunto de vértices V1 de V
o grafo G1 fôr o subgrafo de G gerado por V1.
Mais geralmente, diz-se que
G1 é um subgrafo de G
quando o grafo G1 fôr isomorfo a um subgrafo de G.
Subgrafos Parciais
Chama-se subgrafo parcial de G a
um grafo G1=(V1,A1)
onde os conjuntos V1 e A1 sejam
subconjuntos de V e A, respectivamente.
Está implícito nesta definiçăo que toda a aresta de A1
tenha as suas extremidades em V1.
Mais geralmente, diz-se que
G1 é um subgrafo parcial de G
quando o grafo G1 fôr
isomorfo a um subgrafo parcial de G.
Grafos Parciais
Chama-se grafo parcial de G a
um grafo G1=(V,A1)
que tenha exactamente os mesmos vértices de G
e cujas arestas sejam arestas de G, i.e.
sendo A1 um
subconjunto de A. Diz-se também que G1
é o grafo parcial de G gerado por A1.
Mais geralmente, diz-se que
G1 é um grafo parcial de G
quando o grafo G1 fôr
isomorfo a um grafo parcial de G.