Mostrar código-fonte de Subgrafo

[[Ficheiro:Subgraph.svg|thumb|300px|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'',<ref name=jayme>{{citar livro|autor=Szwarcfiter, Jayme Luiz|título=Grafos e algoritmos computacionais|subtítulo=|idioma=|edição=|local=Rio de Janeiro|editora=Campus|ano=1988|páginas=|volume=|isbn= 85-7001-341-8}}</ref> 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==

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

1- V’ <math>\subseteq</math> V

2- A' <math>\subseteq</math> A

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

* Se G’=(V’,A’) é subgrafo de G, para todo v <math>\in</math> G se cumpre gr (G’,v)= gr (G, v) '''G2 é um subgrafo de G.'''

=={{Âncora|Subgrafo induzido}}Outras definições correlatas==
[[Ficheiro:Induced subgraph.svg|thumb|300px|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 (estrutura de dados)|árvore]] é chamado de [[árvore de extensão]] de G<ref name=shimon>{{citar livro|autor=Even, Shimon|título=Graph Algorithms|subtítulo=|idioma=|edição=|local=Rockville, Maryland|editora=Computer Science Press|ano=1979|página=24|volume=|isbn= 0-914894-21-8}}</ref>

{{Referências}}

[[Categoria:Teoria dos grafos]]