subgrafos

Subgrafos são grafos formados a partir de um grafo G=(V,E) ao escolher um conjunto de vértices V' ⊆ V e, possivelmente, um conjunto de arestas E' ⊆ E, de modo que cada aresta em E' conecte dois vértices pertencentes a V'. Em termos simples, um subgrafo conserva parte dos vértices e das arestas do grafo original, sem adicionar novas ligações.

Podem ser classificáveis de várias formas. Subgrafo induzido (ou gerado) por V' é o grafo H=(V',E' ) em que E' é o conjunto de todas as arestas de E cujos extremos estão em V'. Subgrafo não induzido, ou simplesmente subgrafo, utiliza V' e E' escolhidos livremente entre as arestas de E com ambos os extremos em V', sem incluir todas as arestas entre V'. Spanning subgraph é aquele cujo conjunto de vértices é o mesmo do grafo original, ou seja, V' = V.

Propriedades e operações relacionadas são comuns na teoria dos grafos. Todo subgrafo de um grafo planar também é planar. Subgrafos podem ser usados para estudar conectividade, ciclos e árvores; por exemplo, um subgrafo de uma floresta é sempre também uma floresta. Às vezes, propriedades não são preservadas por subgrafos (por exemplo, um grafo conectado pode ter subgrafos desconectados).

Aplicações típicas incluem análise de redes, algoritmos de busca e de teste de propriedades, decomposição de grafos e o estudo de minors e reduções. Subgrafos fornecem uma forma fundamental de modularização: grande parte da teoria de grafos é construída a partir da análise de partes menores extraídas de grafos maiores.