grafos:subgrafos

Homomorfismo e Isomorfismo

Definição: Homomorfismo

Sejam G=(V,E)G=(V,E) e G′=(V′,E′)G′=(V′,E′) dois grafos. Um mapa φ:V→V′φ:V→V′ é um homomorfismo de GG para G′G′ se ele preserva a adjacência de vértices, isto é, se {φ(x),φ(y)}∈E′{φ(x),φ(y)}∈E′ sempre que {x,y}∈E{x,y}∈E. Em particular, para cada x′x′ na imagem de φφ sua imagem inversa φ−1(x′)φ−1(x′) é um conjunto independente de vértices em GG.

Definição: Isomorfismo

Se φφ é bijetivo e seu inverso φ−1φ−1 também é um homomorfismo (de modo que xy∈E⇔φ(x)φ(y)∈E′xy∈E⇔φ(x)φ(y)∈E′ para todo x,y∈Vx,y∈V), chamamos φφ de isomorfismo, dizemos que GG e G′G′ são isomórficos e escrevemos G≃G′G≃G′. Um isomorfismo de GG para si mesmo é um automorfismo de GG.

Normalmente não distinguimos entre grafos isomórficos. Assim, geralmente escrevemos G=G′G=G′ em vez de G≃G′G≃G′. Se quisermos enfatizar que estamos interessados apenas no tipo de isomorfismo de um determinado grafo, nos referimos informalmente a ele como um grafo abstrato.

Uma classe de grafos que é fechada sob isomorfismo é chamada de propriedade do grafo. Por exemplo, conter um triângulo é uma propriedade do grafo: se GG contém três vértices adjacentes pareados, então todo grafo isomórfico a GG também contém.

Um mapa que usa grafos como argumentos é chamado de invariante de grafo se atribuir valores iguais a grafos isomórficos. O número de vértices e o número de arestas de um grafo são duas invariantes de grafos simples; o maior número de vértices adjacentes aos pares é outro.

Definimos G∪G′:=(V∪V′,E∪E′)G∪G′:=(V∪V′,E∪E′) e G∩G′:=(V∩V′,E∩E′)G∩G′:=(V∩V′,E∩E′). Se G∩G′=∅G∩G′=∅, então GG e G′G′ são disjuntos.

Subgrafos

Um subgrafo de um grafo GG é, em linguagem informal, um “pedaço” de GG. Assim, dado G=(V,A)G=(V,A) um grafo qualquer, um subgrafo de GG é um grafo H=(V′,A′)H=(V′,A′), tal que V′⊂VV′⊂V e A′⊂AA′⊂A, ou seja, todo vértice de HH é vértice de GG e toda aresta de HH é aresta de GG, então HH é um subgrafo de GG. Denotamos, pois, H⊆GH⊆G.

Definição: Subgrafo

Seja tais dois grafos G=(V,A)G=(V,A) e H=(V′,A′)H=(V′,A′). Se V′⊆VV′⊆V e E′⊆EE′⊆E , então G′G′ é dito um subgrafo de GG, escrito como G′⊆GG′⊆G.

Definição: Grafo Induzido

Seja dois grafos G=(V,A)G=(V,A) e G′=(V′,A′)G′=(V′,A′). Se G′⊆GG′⊆G e G′G′ contém todas as arestas xy∈Axy∈A com x,y∈V′x,y∈V′, então G′G′ é um subgrafo induzido de GG; dizemos que V′V′ induz ou gera G′G′ em GG e escrevemos G′=:G[V′]G′=:G[V′].

Assim, se U⊆VU⊆V é qualquer conjunto de vértices, então G[U]G[U] denota o grafo em UU cujas arestas são precisamente as arestas de GG com ambas as extremidades em UU. Se HH é um subgrafo de GG, não necessariamente induzido, abreviamos G[V(H)]G[V(H)] para G[H]G[H].

A figura abaixo exemplifica a diferença entre essas duas subestruturas. Nela, o grafo H′H′ é um subgrafo do grafo GG representado e possui como vértices os elementos do conjunto {0,1,2,3,4}{0,1,2,3,4}. Suas arestas são algumas arestas de GG que possuem dois desses vértices como extremidades. Ainda assim, H′H′ não é um subgrafo induzido de GG, pois a aresta {0,1}{0,1} (presente no grafo GG) não é uma aresta de H′H′. O grafo HH, por outro lado, é o subgrafo de GG induzido por {0,1,2,3,4}{0,1,2,3,4}.

As seguintes observações podem ser feitas:

  • Todo grafo é um subgrafo de si próprio;
  • Um subgrafo de um subgrafo GG também é um subgrafo de GG;
  • Um vértice de um grafo GG é um subgrafo de GG;
  • Uma aresta, e os vértices aos quais ela é incidente, de um grafo GG é um subgrafo de GG;

Definição: Subgrafo Gerador

Um subgrafo gerador de um grafo G=(V,A)G=(V,A) é um subgrafo H′=(V′,A′)H′=(V′,A′) de GG tal que V=V′V=V′, ou seja, se se V′V′ gera todo GG.

Definição

Dois subgrafos de um grafo GG, G1G1 e G2G2, são aresta-disjuntos se eles não possuem arestas em comum.

Se G1G1 e G2G2 não possuírem vértices em comum, os dois subgrafos são chamados de vértices-disjuntos.

Referências

  • grafos/subgrafos.txt
  • Última modificação: 2023/08/10 13:11
  • por 127.0.0.1