Atividade 1 Teoria dos Grafos

Prévia do material em texto

Universidade Federal do Estado do Rio de Janeiro - UNIRIO 
Centro de Ciências Exatas e Tecnológicas - CCET 
Escola de Engenharia de Produção 
 
 
Atividade 1 – Teoria dos Grafos 
Grupo: 
Alessandra Carvalho 
Amanda Duarte 
Everton Dias 
Raquel Neves 
Ricardo Santos 
 
 
1. Pesquise: 
A) O que são grafos de Kuratowski. Desenhe-os. 
São dois grafos não planares, regulares sendo o grafo K5 com menor número de vértices e o 
grafo K3,3 com menor número de arestas: 
 
 
B) Enuncie o Teorema de Kuratowski. 
Um grafo é planar se e somente se não contém nenhum subgrafo, ou seja, uma subdivisão do 
K5 e nem do K3,3. 
C) O que é uma clique? Dê um exemplo num grafo. 
Uma clique em um grafo não-dirigido é um conjunto de vértices dois a dois adjacentes. Em 
outras palavras, um conjunto C de vértices é uma clique se tiver a seguinte propriedade: para 
todo par v, w de vértices distintos em C, existe uma aresta com pontas v e w. 
 
 
D) O que é um conjunto independente? Dê um exemplo num grafo. 
Um conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si que 
não está estritamente contido em outros conjuntos independentes. 
 
E) O que é uma ponte? Dê um exemplo num grafo. 
Uma aresta que, quando removida, desconecta o grafo, ou mais precisamente, aumenta o 
número de componentes conectados no grafo. Uma aresta é uma ponte, se e somente se ela não 
está contida em qualquer ciclo. 
As arestas em vermelho são as pontes 
F) O que é um grafo auto-complementar? Dê dois exemplos de grafos auto- 
complementares. 
Um grafo é autocomplementar se ele for isomorfico ao seu complemento. 
 
 
G) O que é uma fonte? Dê exemplo num digrafo 
Uma fonte é um vértice que tem grau de entrada nulo. 
 
H) O que é um sumidouro? Dê exemplo num digrafo. 
Um vértice v com grau de saída nulo. 
 
I) O que são grafos perfeitos? 
São grafos em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior 
clique deste subgrafo. 
J) O que é um grafo Split? Dê exemplos. 
Um grafo é split, se e somente se, seu conjunto de vértices pode ser particionado em dois 
subconjuntos, �(�) e �(�), tal que existe aresta entre quaisquer dois vértices de �(�), e não 
existe aresta entre vértices de �(�). 
 
K) O que é um vértice simplicial? Dê exemplos. 
É um vértice em que todos os vértices de sua vizinhança, aberta ou fechada, induzem uma 
clique no grafo original. 
 
 
 
 
 
L) O que é um grafo ciclo ou circuito? Mostre exemplos 
Um ciclo em um grafo é um caminho fechado sem vértices repetidos. 
 
 
M) O que é um grafo caminho? Mostre exemplos 
Um grafo caminho é um exemplo simples de uma árvore, ou seja, uma árvore com dois ou mais 
vértices que não tem ramificações, contendo apenas vértices de grau 2 e 1. 
 
2. Um grafo possui 100 vértices e 98 arestas. Justifique usando a teoria dos grafos se 
esse grafo pode ser conexo. 
Para o grafo ser conexo precisa existir um caminho entre quaisquer vértices. Neste caso o 
grafo não pode ser conexo. Pois para um grafo com n=100 vértices precisa ter pelo menos n-
1 arestas, ou seja, 99 arestas. 
3. Quantas arestas tem o grafo complementar de um grafo de 100 vértices e 98 
arestas? 
Para sabermos quantas arestas tem o grafo complementar de um grafo de 100 vértices e 98 
arestas, precisamos primeiro saber qual máximo de arestas ele teria. Para isso usamos a 
expressão n(n-1)/2. Tendo n=100, obtemos 100(100-1)/2= 4950 arestas. Como o grafo 
complementar é um grafo que possui o mesmo conjunto de vértices de seu original onde 
dois vértices são vizinhos em seu complementar se e somente se não são vizinhos em seu 
grafo original. Ou seja, subtraindo a quantidade de arestas que o grafo original tem do valor 
máximo de arestas que esse grafo poderia ter, obtemos o seu complementar. Sendo assim 
4950- 98= 4852 arestas, possui o grafo complementar de um grafo com 100 vértices e 98 
arestas. 
 
4. Prove que todo grafo Split é perfeito. 
 Consideramos que G é um grafo split se existir uma bipartição de V(G) em conjuntos A e B 
de tal forma que G[B] é independente e G[A] é um clique. Dessa forma vemos que G é perfeito 
pelo seguinte modo: pegando A com o maior número possível de vértices e obtemos que para 
todo vértice “v” de B teremos pelo menos um vértice “u” em A que não é seu vizinho. Com 
isso damos para “u” a mesma cor de “v”. Colorindo todo grafo G com a mesma cor. 
5. Numa cidade, existem apenas 11 casas muito distantes entre si. É possível que cada casa 
esteja ligada a exatamente 9 outras casas através de estradas? Justifique sua resposta com 
base nos teoremas aprendidos no curso. 
De acordo com o Teorema do aperto de mão, dado um grafo com n vértices e m arestas, a soma 
do grau dos vértices é duas vezes o número de arestas. Portanto, aplicando ao problema: 
Não é possível, pois quando somamos a quantidade de estradas que saem de cada casa, obtemos 
11 x 9 = 99 estradas 
Como cada estrada liga duas cidades, a contagem feita contou cada estrada duas vezes. Logo, 
o número obtido deveria ser par. 
 6. Para o grafo a seguir determine: 
 
 
 
 
 
 
 
 
a) Sua matriz de adjacência 
 
 
 
b) Seu número cromático 
O número cromático é o número mínimo de cores necessárias para se colorir o 
grafo de modo que nenhum tenha adjacente a ele uma mesma cor. 
O número cromático para o grafo em questão é 4. 
 
 
c) Seu índice cromático 
4 - colorível 
 
 
d) O grafo possui um circuito euleriano? Justifique 
Segundo o Teorema de Euler, seja G um grafo planar simples com m arestas e n 
vértices. Seja r o número de regiões na representação planar de G. Temos que: 
r = m – n + 2 
Aplicando ao problema: 
m = 15 
n = 10 
Temos: 
r = 15 - 10 + 2 
r = 7 
Aplicando o corolário 1, que diz que se G é um grafo simples conexo e planar 
com m arestas e n vértices, sendo n ≥ 3, então m ≤ 3n − 6. Temos: 
n ≥ 3 
15 ≤ 3.10 − 6 
15 ≤ 24 O que satisfaz a condição 
Aplicando o corolário 2, que diz que Se G é um grafo simples conexo e planar com 
m arestas e n 
vértices, sendo que n ≥ 3 e nenhum ciclo de comprimento três, então m ≤ 2n − 
4. Temos: 
15 ≤ 2. 10 − 4 
15 ≤ 16 O que satisfaz a condição. Logo: 
Não é possível definir se o grafo possui um circuito euleriano. 
e) O grafo possui um ciclo hamiltoniano? Justifique 
Como não há um método eficiente para determinar se tal ciclo existe em um grafo, 
o grupo tentou fazer alguns caminhos mas não chegamos ao ciclo hamiltoniano. 
 
 
f) O grafo é bipartido? Justifique 
O grafo não é bipartido pois para ser bipartido é necessário que toda aresta de G 
tenha um extremo na partição 1 e outro na partição 2, e para isso o grafo precisa ser 
bicolorível, o que não é o caso do grafo da questão pois se trata de um grafo 4 - 
colorível. 
 
 
 
 
 
 
Referências Bibliográficas 
KUNIGAMI. Kuratowski e a planaridade de grafos. Disponível em: 
<https://kuniga.wordpress.com/2012/07/14/kuratowski-e-a-planaridade-de-grafos/>. Acesso 
em: 23 mar. 2021. 
MARCO ANTONIO M. CARVALHO (UFOP). Teoria dos Grafos. 2019. Disponível em: 
<http://www.decom.ufop.br/marco/site_media/uploads/bcc204/16_aula_16.pdf>. Acesso em: 
23 mar. 2021. 
PAULO FEOFILOFF IME-USP. Cliques e conjuntos estáveis. 2017. Disponível em: 
<https://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/cliques.html>. Acesso em: 23 mar. 
2021. 
EDSON PRESTES - UFRGS. Teoria dos Grafos. Disponível em: 
<http://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/GrafosA2.pdf>. Acesso em: 23 
mar. 2021. 
ARNALDO MANDEL - DCC - IME. Algoritmos em Grafos. 2012. Disponível em: 
<https://www.ime.usp.br/~am/328-12/aulas/aula-0327h.pdf>. Acesso em: 23 mar. 2021. 
LOUREIRO - UFMG/ICEX/DCC. Lista de Exercícios 9 - Soluções Grafos. 2018. Disponível 
em: <https://homepages.dcc.ufmg.br/~loureiro/md/md_LE9_Solucao.pdf>. Acesso em: 23 
mar. 2021. 
CASTRO, L.A.L. CARACTERIZAÇÃO ECOLORAÇÃO DE ARESTAS EM 
GRAFOSSPLIT-CO-COMPARABILIDADE. 2018. Trabalho de Conclusão de Curso 
(Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, 
Ponta Grossa. 
ALEFFER ROCHA - UTFP. Diversidade dos conjuntos independentes maximais em 
alguns grafos não-simpliciais. 2016. Disponível em: 
<http://www.wpccg.pro.br/apresentacoes/2016/aleffer-rocha>. Acesso em: 23 mar. 2021. 
WIKIPEDIA. Teoria dos grafos. 2020. Disponível em: 
<https://pt.wikipedia.org/wiki/Grafo_caminho>. Acesso em: 23 mar. 2021.