Pesquisa · Mapa mental
Subgrafo
Na teoria dos grafos, um subgrafo é como uma 'parte' de um grafo maior. Ele é formado por um subconjunto dos vértices e das arestas do grafo original, mantendo as relações de adjacência. Se um grafo G possui um subgrafo que é idêntico ou isomorfo a outro grafo H, dizemos que G 'contém' H. Este conceito é fundamental para analisar a estrutura e as propriedades dos grafos.
Pontos-chave
- Um subgrafo utiliza um subconjunto de vértices e arestas do grafo original.
- A relação de adjacência do subgrafo é um subconjunto da do grafo original, restrita aos vértices selecionados.
- Um grafo G 'contém' H se H for um subgrafo de G ou isomorfo a um subgrafo de G.
- Subgrafos induzidos mantêm todas as arestas originais entre seus vértices.
- Árvores de extensão são subgrafos que abrangem todos os vértices do grafo original e formam uma árvore.
Para um grafo G = (V, A), onde V é o conjunto de vértices e A é o conjunto de arestas, um grafo G' = (V', A') é considerado um subgrafo de G se as seguintes condições forem atendidas:
Além da definição básica de subgrafo, existem outras terminologias importantes que descrevem diferentes tipos de relações entre grafos e suas partes, enriquecendo a análise estrutural.
