Lista11 Grafos

Matemática Discreta - 2024.
1
Lista 11 - Grafos
Profª Anjolina Grisi
Questão 1
Para cada cadeira de Ciência da Computação no CIn, pode haver um ou mais
outros cursos que são seus pré-requisitos e co-requisitos. Como pode um grafo
ser usado para modelar essas cadeiras e quais cadeiras são pré-requisitos e
co-requisitos para quais cadeiras? Forme um grafo para exemplificar. As
arestas devem ser direcionadas ou não direcionadas? Olhando para o grafo,
como podemos encontrar cursos que não possuem pré-requisitos e como en-
contramos cadeiras que não são pré-requisito para qualquer outra cadeira?
Questão 2
Considere os grafos G1 e G2 descritos abaixo:
• Grafo G1 : Vértices {A, B, C, D, E}, com arestas {(A, B), (A, C), (B, C), (B, D), (C, E)}.
• Grafo G2 : Vértices {1, 2, 3, 4, 5}, com arestas {(1, 2), (1, 3), (2, 3), (2, 4), (3, 5)}.
(a) Verifique se G1 e G2 são isomorfos. Se forem, forneça uma bijeção entre
os vértices de G1 e G2 que preserve as arestas.
(b) Caso G1 e G2 sejam isomorfos, determine quais propriedades dos grafos
foram preservadas. Liste pelo menos duas propriedades.
(c) Explique o conceito de isomorfismo de grafos e o que significa dois
grafos serem isomorfos.
1
Questão 3
Sobre isomorfismo, responda:
(a) Mostre um isomorfismo entre os dois grafos seguintes ou utilize um

argumento rigoroso para provar que não existe.
(b) Isomorfismo entre grafos simples é uma relação de equivalência? Ex-

plique.
Questão 4
Desenhe os seguintes grafos:
(a) K7
(b) K1,8
(c) K4,4
(d) C7
(e) W7
(f) Q4
Questão 5
Mostre que um grafo simples G é bipartido se e somente se ele não tem
circuitos com um número ı́mpar de arestas.
2
Questão 6
Para quais valores de m e n o grafo bipartido Km.n tem um circuito euleriano?
Responda também para quais valores ele tem um caminho euleriano também.
Questão 7
Responda cada item a seguir:
(a) Qual o maior número de arestas que um grafo simples com 12 vértices
pode possuir?
(b) Qual o maior número de arestas que um grafo bipartido com 12 vértices
pode ter?
(c) Quantas arestas tem um grafo 40-regular com 80 vértices?
(d) O grafo C6 é isomorfo ao seu complemento?
(e) Quantas folhas uma árvore 4-ária cheia com 120 vértices deve ter?
Questão 8
Considere um grafo G = (V, E) onde V representa os vértices e E as arestas.
Suponha que este grafo tenha 10 vértices e 15 arestas. Sabendo que o grau
de cada vértice do grafo é dado por d(v), responda:
(a) Qual é a soma dos graus de todos os vértices desse grafo?
(b) O grafo pode ser um grafo regular? Se sim, qual seria o grau de cada
vértice?
(c) Use o Teorema das Mãos Apertadas para explicar a relação entre a
soma dos graus dos vértices e o número de arestas.

Lista11 Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

Lista11 Grafos

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Lista11 Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

Matemática Discreta - 2024.

Profª Anjolina Grisi

(a) Mostre um isomorfismo entre os dois grafos seguintes ou utilize um

(b) Isomorfismo entre grafos simples é uma relação de equivalência? Ex-

(c) Quantas arestas tem um grafo 40-regular com 80 vértices?

(d) O grafo C6 é isomorfo ao seu complemento?

(a) Qual é a soma dos graus de todos os vértices desse grafo?

Você também pode gostar