Dê um exemplo de grafo bipartido com 8 vértices, onde todos os seus vértices têm grau 3 e, para todo par de vértices
e
.
Passo 1
Beleza, vamos resolver esse exercício juntos! O enunciado pede para criar um grafo bipartido com 8 vértices, onde todos os vértices têm grau 3. Além disso, para qualquer par de vértices
e
, os conjuntos de vizinhos
e
devem ser diferentes. Isso envolve conceitos de teoria dos grafos, especificamente sobre grafos bipartidos e grafos regulares. Para resolver, vamos precisar entender como dividir os vértices em dois grupos e conectar cada vértice de um grupo a exatamente três vértices do outro grupo, garantindo que os conjuntos de vizinhos sejam únicos.
Passo 2
Primeiro, vamos lembrar o que é um grafo bipartido. É um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos, digamos
e
, de modo que não haja arestas entre vértices do mesmo conjunto. Ou seja, todas as conexões são entre
e
.
Passo 3
Como temos 8 vértices e o grafo é bipartido, vamos dividir os vértices em dois conjuntos iguais:
e
, cada um com 4 vértices. Vamos chamar os vértices de
e
.
Passo 4
Agora, precisamos que todos os vértices tenham grau 3, ou seja, cada vértice em
deve estar conectado a três vértices em
, e vice-versa. Além disso, queremos que para qualquer par de vértices, seus conjuntos de vizinhos sejam diferentes.
Passo 5
Vamos começar conectando os vértices de
aos de
:
- A1 será conectado a B1, B2, B3.
- A2 será conectado a B1, B2, B4.
- A3 será conectado a B1, B3, B4.
- A4 será conectado a B2, B3, B4.
Passo 6
Vamos verificar as conexões para garantir que todos os vértices têm grau 3 e que os conjuntos de vizinhos são únicos:
- A1: B1, B2, B3
- A2: B1, B2, B4
- A3: B1, B3, B4
- A4: B2, B3, B4
Agora, vemos que cada vértice em
está conectado a três vértices em
, e nenhum par de vértices em
compartilha exatamente o mesmo conjunto de vizinhos.
Passo 7
Da mesma forma, vamos verificar para os vértices em
:
- B1: A1, A2, A3
- B2: A1, A2, A4
- B3: A1, A3, A4
- B4: A2, A3, A4
Cada vértice em
também está conectado a três vértices em
, e todos têm conjuntos de vizinhos únicos.
Resposta
Um exemplo de grafo bipartido com 8 vértices, todos com grau 3 e com conjuntos de vizinhos distintos para cada vértice, é o grafo com os conjuntos
e
e as seguintes arestas:
- A1 está conectado a B1, B2, B3
- A2 está conectado a B1, B2, B4
- A3 está conectado a B1, B3, B4
- A4 está conectado a B2, B3, B4
Esse grafo satisfaz todas as condições do enunciado.