Defina de forma precisa os seguintes conceitos: a) Grau e vizinhança de um vértice. b) Grafo completo com n vértices. c) Grafo bipartido com ...

Defina de forma precisa os seguintes conceitos:

a) Grau e vizinhança de um vértice.

b) Grafo completo com n vértices.

c) Grafo bipartido com bipartição (X,Y ).

d) Componentes de um grafo G.

e) Floresta e Árvore com n vértices.

Utilizando as definições conhecidas, responda (de acordo com as instruções).

f) Para qualquer n podemos afirmar que Kn é um grafo euleriado?

g) Apresente o seguinte produto cartesiano: □

Resposta. Sejam as seguinte respostas:

a) Vizinhança de vértice v ∈ V (G) é definida por NG(v) = {u : vu ∈ E(G)}. Grau de vértice v ∈ V (G) é
definido por dG(v) = |NG(v)|.

b) Definimos o grafo completo com n vértice como Kn = (V,E), onde E = {xy : x ∈ v(G), y ∈ V (G), x ̸= y}

c) Um grafo bipartido G com bipartição (X,Y ) é tal que X,Y ⊆ V (G) onde X ∩ Y = ∅, X ∪ Y = V (G) e
G[X] e G[Y ] são conjuntos independentes.

d) As componentes de um grafo G são subgrafos maximais conexos de G.

e) Floresta é um grafo aćıclico. Árvores são grafos conexos e aćıclicos.

f) Não, pois um grafo é euleriano se, e somente se, todos os vértices têm grau par e existe no máximo uma
componente não trivial. Desta forma, Kn é euleriano apenas para n ı́mpares.

g) □