Grafos e Árvores Flashcards
(45 cards)
O que é uma árvore geradora de um grafo? E uma árvore geradora mínima?
Uma árvore geradora um subgrafo conexo e acíclico de um grafo não-direcionado. Árvore geradora mínima é uma árvore geradora que minimiza o peso total de suas arestas.
O que é um emparelhamento em um grafo? O que é um emparelhamento perfeito? No contexto do problema do Casamento Estável, podemos dizer que um emparelhamento perfeito é sinônimo de emparelhamento estável?
Um emparelhamento é um conjunto de arestas de um grafo em que nenhum vértice aparece mais de uma vez no conjunto. Um emparalhamento perfeito é um emparelhamento que contém todos os vértices do grafo. Não é sinônimo de emparelhamento estável (que tem a ver com a ordem de preferência).
No contexto do problema do Casamento Estável, quais são as 3 condições para um par (h, m) ser considerado instável em um emparelhamento perfeito M?
1 - (h, m) não pode pertencer a M
2 - h deve preferir m à m’ designada pelo emparelhamento.
3 - m deve preferir h ao h’ designado pelo emparelhamento.
Quando podemos dizer que um grafo é uma árvore?
Quando o grafo é conectado e não possui ciclos.
Qual condição um grafo precisa ter para ser considerado conectado? E fortemente conectado?
Um grafo é conectado se e somente se, para qualquer par de vértices u e v, existe um caminho entre u e v. Ele será fortemente conectado se for um grafo direcionado e, para qualquer par de vértices u e v, existir um caminho entre u e v e entre v e u.
Quantas arestas possui uma árvore com n vértices?
N - 1 arestas.
De maneira resumida, como funciona o algoritmo BFS? Explique em termos de camadas.
O algoritmo BFS começa na raiz. Na primeira iteração, ele explora a primeira camada (ou seja, todos os vértices diretamente conectados à raiz). Na segunda, ele explora a segunda camada (ou seja, todos os vértices conectados aos vértices conectados à raiz) e assim por diante até nenhum vértice novo ser encontrado.
Defina camadas no contexto do algoritmo BFS.
A primeira camada são o os elementos diretamente conectados à raiz. Se temos as camadas 1, 2, …, j, a camada j+1 será composta por todos os elementos que estão conectados a j e não aparecem em nenhuma camada anterior.
Entre BFS e DFS, qual é melhor para encontrar a menor rota até um ponto? Por quê?
BFS. Na sua definição, BFS funciona explorando primeiro os elementos a uma distância 1 da raiz, seguido pela distância 2, 3 e assim por diante. Desta forma, em uma etapa n, o BFS descobre todos os pontos alcançáveis em n passos, encontrando assim a menor distância.
DFS, por outro lado, escolhe um caminho e segue ele até o final. Isso quer dizer que um vértice conectado tanto à raiz quanto à camada n pode ser encontrado primeiro explorando o caminho mais longo e não o mais curto.
Como funciona a representação de grafos por matrizes de adjacência? E por listas de adjacência? Cite vantagens e desvantagens de se usar um ao invés do outro.
Em uma matriz de adjacência, o grafo é representado como uma matriz n x n sendo n o número de vértices. Se existir uma conexão entre dois vértices i, j, m[i][j] será igual a 1, caso contrário, será um valor padrão.
Em uma lista de adjacência, o grafo é representado como uma lista com n listas representando os vértices. Cada uma dessas n listas representa os elementos conectados diretamente a n.
A matriz de adjacência tem como principal desvantagem o uso de memória na ordem de n². Sua maior vantagem é a identificação mais rápida se um vértice (u, v) existe em um grafo. A lista de adjacência, por outro lado, usa memória na ordem de m + n e por isso funciona melhor para listas esparsas.
O que é um grafo bipartido ? Qual a condição que um grafo precisa atender para ser considerado bipartido. Dê um exemplo de aplicação desse conceito.
Um grafo bipartido é um grafo que pode ser dividido em 2 conjuntos a e b de forma que não exista nenhuma aresta entre elementos do mesmo conjunto. Um grafo é bipartido se e somente se ele não possui ciclos com um número ímpar de vértices.
Uma aplicação desse conceito é o problema do Casamento Estável que pode ser modelado como um grafo bipartido em que um grupo representa os escolhedores e o outro os escolhidos.
De que forma podemos usar o algoritmo de BFS para identificar se um grafo conexo é bipartido ou não?
Para identificar se um grafo é bipartido, podemos usar o algoritmo BFS para construir uma árvore de busca em largura. O grafo será bipartido se e somente se não possuir nenhuma aresta entre vértices da mesma camada.
Em qual situação, num grafo BFS, podemos ter uma aresta conectando vértices cuja diferença de nível é maior que 1? Que nome damos a essa aresta?
Para termos arestas conectando vértices em camadas cuja diferença é maior que 1, é necessário que o grafo seja direcionado e a aresta parta de um vértice em uma camada inferior e aponte para uma camada superior. A esse tipo de aresta, damos o nome de back edge.
Quais são as 4 principais classificações para arestas em um grafo após a execução de um algoritmo como BFS/DFS?
- Tree Edge: Aresta que está presente no grafo e na árvore correspondente
- Cross Edge: Aresta que está presente apenas no grafo e conecta dois elementos sem relação direta na árvore correspondente
- Back Edge: Aresta que está presente apenas no grafo e conecta uma aresta em um nível inferior a uma aresta em um nível superior
- Forward Edge: Aresta que está presente apenas no grafo e conecta uma aresta em um nível superior a uma aresta em um nível inferior.
Quais tipos de arestas podem ser encontrados em um grafo BFS? Justifique.
Tree Edge (por definição) e Cross Edge. Se o grafo for direcionado, pode ser encontrado também back edge.
Forward edge não pode existir em uma árvore BFS porque ela parte de uma camada superior e aponta para uma camada inferior. Visto que o BFS explora em camadas, se essa aresta existir no grafo, será incluída como uma tree edge.
Quais tipos de arestas podem ser encontrados em um grafo DFS? Justifique.
Tree Edge (por definição) e back Edge. Se o grafo for direcionado, pode ser encontrado também forward edge e cross edge.
Em um grafo não direcionado, todas as arestas são descobertas pelo último elemento a ser visitado. Por isso, uma aresta entre dois vértices dependentes será ou uma Tree Edge (se for explorada pelo vértice na camada superior) ou uma Back Edge (se for explorada pelo vértice na camada inferior).
Da mesma forma, uma potencial cross Edge seria incluída ou como uma tree edge (se os vértices pertencessem a árvores diferentes) ou uma back edge (se possuírem algum descendente em comum).
Como identificar back edges em um grafo DFS?
Mantenha uma lista L com todos os vértices que estão sendo explorados mas ainda não foram finalizados. Ao explorar uma aresta nova, ela será uma back edge se e somente se ela conectar dois vértices que ainda não foram finalizados.
Como identificar back edges em um grafo BFS?
Ao explorar uma aresta nova, ela será uma back edge se e somente se ela conectar um vértice que não foi finalizado a um vértice que já foi.
Como identificar forward edges em um grafo DFS?
Mantenha em cada vértice uma variável contendo o tempo em que a exploração começou e o tempo no qual a exploração terminou. Uma aresta é uma forward edge se e somente se a exploração do vértice de origem começou antes da exploração do vértice de destino.
Como identificar cross edges em um grafo DFS?
Mantenha em cada vértice uma variável contendo o tempo em que a exploração começou e o tempo no qual a exploração terminou. Uma aresta é uma forward edge se e somente se a exploração do vértice de origem começou depois da exploração do vértice de destino.
Como identificar cross edges em um grafo BFS?
Mantenha uma lista L com todos os vértices que estão sendo explorados mas ainda não foram finalizados. Ao explorar uma aresta nova, ela será uma cross se e somente se ela conectar dois vértices que ainda não foram finalizados.
Como identificar um ciclo em um grafo a partir dos tipos de suas arestas, do tipo do grafo e do algoritmo usado?
Independente do algoritmo ou do grafo utilizado, uma back edge sempre indica um ciclo. No caso de um BFS em um grafo não direcionado, uma Cross Edge também indica um ciclo.
Qual propriedade relaciona as arestas de um grafo G que conectam dois pontos x e y com os níveis no qual esses pontos aparecerão dentro da árvore BFS formada a partir de G ? Que conclusão podemos tirar sobre as arestas que estão no grafo mas não estão na árvore?
Se (x,y) é uma aresta em um grafo G, x e y aparecerão na árvore BFS ou no mesmo nível ou em níveis consecutivos. A consequência que podemos tirar é que as arestas presentes em G que não estão na árvore conectam sempre vértices que estão ou no mesmo nível ou em níveis consecutivos.
Qual é a complexidade do algoritmo BFS em função de seus vértices e arestas?
O (m + n)
