REVISÃO GRAFOS
[Link] UM GRAFO NÃO DIRECIONADO G COM N VERTICES E E ARESTAS. A
CONECTIVIDADE DE UM GRADO REFERE-SE A:
A: O NÚMERO MÍNIMO DE ARESTAS QUE PRECISAM SER REMOVIDAS PARA DESCONECTAR O
GRAFO
B: O NÚMERO DE VÉRTICES DO GRAFO
C: A DISTÂNCIA ENTRE DOIS VÉRTICES QUAISQUER NO GRAFO
D: O NÚMERO DE COMPONENTES CONECTADOS NO GRAFO
E: O NUMERO TOTAL DE ARESTAS NO GRAFO
[Link] DAS SEGUINTES AFIRMAÇÕES É CORRETA SOBRE A CONCEITUAÇÃO E FORMALIZAÇÃO
DE GRAFOS NA TEORIA DOS GRAFOS?
A: UM GRAFO BIPARTIDO É UM GRAFO ONDE TODOS OS VERTICES TEM O MESMO GRAU
B: UM GRAFO PONDERADO É UM GRAFO NO QUAL OS VÉRTICES TÊM PESOS ASSOCIADOS,
MAS AS ARESTAS NÃO TEM PESO
C: UM CICLO EM UM GRAFO É UMA SEQUÊNCIA DE VÉRTICES ONDE CADA VÉRTICE APARECE
EXATAMENTE 2 VEZES
D: UM GRAFO É UMA ESTRUTURA MATEMÁTICA QUE CONSISTE APENAS EM VÉRTICES E NÃO
INCLUI ARESTAS
E: UM DIGRAFO É UM GRAFO NÃO DIRECIONADO ONDE AS ARESTAS TEM UMA DIREÇÃO
ESPECÍFICA
[Link] UM GRAFO DIRECIONADO PONDERADO G COM N VERTICES E E ARESTAS, ONDE
CADA ARESTA TEM UM PESO ASSOCIADO QUE REPRESENTA O CUSTO DE ATRAVESSÁ-LA. EM
RELAÇÃO AOS CAMINHOS EM GRAFOS, QUAL DAS SEGUINTES AFIRMAÇÕES É VERDADEIRA?
A: O ALGORITMO DE BELLMAN-FORD NÃO É EFICIENTE PARA ENCONTRAR O CAMINHO MAIS
CURTO EM GRAFOS COM PESOS NEGATIVOS
B: O ALGORITMO DE DIJKSTRA ENCONTRA O CAMINHO MAIS CURTO EM UM GRAFO
DIRECIONADO PONDERADO COM PESOS NÃO NEGATIVOS
C: EM UM GRAFO ACICLICO DIRECIONADO (DAG), O ALGORITMO DE DIJKSTRA E O ALGORITMO
DE BELLMAN-FORD SEMPRE PRODUZEM O MESMO CAMINHO MAIS CURTO
D: UM CAMINHO MAIS CURTO ENTRE DOIS VÉRTICES EM UM GRAFO É SEMPRE ENCONTRADO
USANDO O ALGORITMO DE BUSCA EM PROFUNDIDADE
E: O ALGORITMO DE FLOYD-MARSHALL É ADEQUADO APENAS PARA GRAFOS NÃO
PONDERADOS
4.A TEORIA DOS GRAFOS É UM RAMO DA MATEMÁTICA QUE ESTUDA AS PROPRIEDADES DOS
GRAFOS QUE SÃO ESTRUTURAS COMPOSTAS POR VÉRTICES CONECTADOS POR ARESTAS. O
QUE CARACTERIZA UM "GRAFO DIRECIONADO"?
A: É UM GRAFO QUE REPRESENTA APENAS NÚMEROS INTEIROS
B: É UM GRAFO EM QUE TODAS AS ARESTAS TÊM O MESMO VALOR
C: É UM GRAFO EM QUE AS ARESTAS TEM UMA DIREÇÃO ESPECÍFICA
D: É UM GRAFO EM QUE CADA VÉRTICE ESTÁ CONECTADO A TODOS OS OUTROS VÉRTICES
E: É UM GRAFO QUE NÃO CONTÉM CICLOS
[Link] O ALGORITMO DE BUSCA EM PROFUNDIDADE E O ALGORITMO DE BUSCA EM
LARGURA. JULGUE AS SENTENÇAS ABAIXO EM VERDADERAS E FALSAS E MARQUE A SENTENÇA
QUE REPRESENTA A SEQUÊNCIA CORRETA ENCONTRADA
(F) TANTO O ALGORITMO DE BUSCA EM PROFUNDIDADE QUANTO O DE BUSCA EM LARGURA
UTILIZAM O CRITÉRIO DE PILHA
(V) TODOS OS NÓS COM DISTÂNCIA K A UM NÓ V SÃO VISITADOS ANTES DOS NÓS COM
DISTANCIA K+1
(V) DESCOBRE TODOS OS VÉRTICES ALCANÇAVEIS A PARTIR DE V
(V) NO DIAGRAMA DE BUSCA EM LARGURA, NOS GRAFOS DIRIGIDOS, CADA ARESTA É VISITA
UMA ÚNICA VEZ
[Link] UM GRAFO SIMPLES G(V,E), ASSINALE A OPÇÃO CORRETA SOBRE A SUA COLORAÇÃO:
A: O NÚMERO CROMÁTICO DE UM GRAFO G,X(G) É O MENOR NÚMERO DE CORES
NECESSÁRIAS PARA COLORIR ESTE GRAFO
B: UMA COLORAÇÃO EM UM GRAFO SIMPLES É A ASSOCIAÇÃO DE UMA COR A CADA VÉRTICE
DO GRAFO DE MODO QUE DOIS VÉRTICES ADJACENTES PODEM TER A MESMA COR.
C: O NÚMERO CROMÁTICO DE UM GRAFO PLANAR É SEMPRE MAIOR DO QUE 5
D: UMA COLORAÇÃO EM UM GRAFO SIMPLES É A ASSOCIAÇÃO DE UMA COR A CADA VÉRTICE
DO GRAFO DE MODO QUE DOIS VÉRTICES ADJACENTES TENHAM A MESMA COR
E: O NÚMERO CROMÁTICO DE UM GRAFO G,X(G) É O MAIOR NÚMERO DE CORES
NECESSÁRIAS PARA COLORIR ESTE GRAFO
[Link] UM GRAFO DIRECIONADO PONDERADO G COM VÉRTICES E E ARESTAS, ONDE
CADA ARESTA TEM UM PESO ASSOCIADO QUE REPRESENTA O CUSTO DE ATRAVESSÁ-LA. EM
RELAÇÃO AOS CAMINHOS EM GRAFOS, QUAL DAS SEGUINTES AFIRMAÇÕES É VERDADEIRA?
A: O ALGORITMO DE BELLMAN-FORD NÃO É EFICIENTE PARA ENCONTRAR O CAMINHO MAIS
CURTO EN GRAFOS COM PESOS NEGATIVOS.
B: O ALGORITMO DE DIJKSTRA ENCONTRA O CAMINHO MAIS CURTO EN UN GRAFO
DIRECIONADO PONDERADO COM PESOS NÃO NEGATIVOS.
C: EM UM GRAFO ACÍCLICO DIRECIONADO (DAG), O ALGORITMO DE DIJKSTRA E O ALGORITMO
DE BELLMAN-FORD SEMPRE PRODUZEM O MESMO CAMINHO MAIS CURTO.
D: UM CAMINHO MAIS CURTO ENTRE DOIS VÉRTICES EM UM GRAFO É SEMPRE ENCONTRADO
USANDO O ALGORITMO DE BUSCA EM PROFUNDIDADE (DFS)
E: O ALGORITMO DE FLOYD-WARSHALL É ADEQUADO APENAS PARA GRAFOS NÃO
PONDERADOS.
[Link] UM GRAFO PLANO G COM V VERTICES, E ARESTAS E F FACES. O TEOREMA DE
EULER ESTABELECE UMA RELAÇÃO FUNDAMENTAL ENTRE V,E E F EM UM GRAFO PLANAR.
QUAL É A FORMULAÇÃO CORRETA DO TEOREMA DE EULER PARA UM GRAFO PLANAR?
A: V-E-F=2
B: V-E+F+2
C: V+E-F=2
D: V+E=F+2
E: V-E+F=2
9. QUAL É A PRINCIPAL DIFERENÇA ENTRE A MATRIZ DE ADJACÊNCIA E A MATRIZ DE
INCIDÊNCIA EM TEORIA DOS GRAFOS?
A: MATRIZ DE INCIDÊNCIA É USADA APENAS PARA GRAFOS SIMPLES, ENQUANTO A MATRIZ DE
ADJACÊNCIA PODE REPRESENTAR QUALQUER TIPO DE GRAFO.
B: A MATRIZ DE INCIDÊNCIA USA COLUNAS PARA REPRESENTAR VÉRTICES, ENQUANTO A
MATRIZ DE ADJACÊNCIA USA COLUNAS PARA REPRESENTAR ARESTAS
C: A MATRIZ DE INCIDÊNCIA NÃO PODE LIDAR COM GRAFOS PONDERADOS, AO CONTRÁRIO
DA MATRIZ DE ADJACÊNCIA
D: A MATRIZ DE INCIDÊNCIA REPRESENTA AS CONEXÕES ENTRE VÉRTICES, ENQUANTO A
MATRIZ DE ADJACÊNCIA REPRESENTA AS CONEXÕES ENTRE ARESTAS.
E: A MATRIZ DE INCIDÊNCIA É USADA PARA REPRESENTAR GRAFOS NÃO DIRECIONADOS,
ENQUANTO A MATRIZ DE ADJACÊNCIA É USADA PARA GRAFOS DIRECIONADOS
10. OBSERVE AS ALTERNATIVAS ABAIXO QUE SE REFEREM A GRAFOS PLANARES E ASSINALE A
ALTERNATIVA QUE CORRESPONDE A UM GRÁFICO QUE NÃO É PLANAR:
A: UM GRAFO CICLO PAR
B: UM GRAFO CICLO DE 3 VÉRTICES
C: GRAFO BIPARTIDO COM 2 VÉRTICES EM CADA PARTIÇÃO
D: K_4
E: K_3,3