NEW
Font size
WorksheetsQuiz sobre Teoria dos Grafos
Total questions: 58
Worksheet time: 29mins
Qual é a origem da Teoria dos Grafos na história da matemática?
Século XVII
Século XVIII
Século XIX
Século XX
Como pode ser visto informalmente um grafo?
Como um conjunto de arestas e vértices
Como um conjunto de pontos e arestas
Como um conjunto de vértices e pares de pontos
Como um conjunto de pontos e pares desses pontos
O que cada aresta liga em um grafo?
Um ponto a outro ponto
Um vértice a outro vértice
Um par de pontos (extremidades)
Um par de vértices (extremidades)
Como é feita a representação usual de grafos?
Por linhas (arestas) e pontos do plano (vértices)
Por círculos e quadrados
Por números e letras
Por cores e formas geométricas
O que é um grafo ( G = (V, A) )?
Um par de conjuntos ( V ) e ( A )
Um conjunto de vértices
Um conjunto de arestas
Um conjunto de números
O que representa o conjunto ( V ) em um grafo?
Conjunto de arestas
Conjunto de vértices
Conjunto de números
Conjunto de letras
O que representa o conjunto ( A ) em um grafo?
Conjunto de vértices
Conjunto de números
Conjunto de arestas
Conjunto de letras
Qual é a definição de uma aresta ( a = (v, w) ) em um grafo?
Um par de vértices ( v ) e ( w ) onde ( v in V ) e ( w in V )
Um par de números ( v ) e ( w )
Um par de letras ( v ) e ( w )
Um par de conjuntos ( v ) e ( w )
Em um exemplo de grafo ( G = (V, A) ), o que representa V?
Conjunto de pessoas
Conjunto de números
Conjunto de letras
Conjunto de arestas
Em um exemplo de grafo ( G = (V, A) ), o que representa A?
Conjunto de números
Conjunto de letras
Conjunto de amigos
Conjunto de arestas
O que é um digrafo?
Um grafo com arestas sem direção
Um grafo com arestas com origem e destino
Um grafo sem arestas
Um grafo com apenas um vértice
No grafo definido, o que representa o conjunto V?
Conjunto de arestas
Conjunto de vértices
Conjunto de pais
Conjunto de filhos
No grafo definido, o que representa o conjunto A?
Conjunto de vértices
Conjunto de arestas
Conjunto de pais
Conjunto de filhos
No grafo definido, o que significa a relação (v, w)?
v é filho de w
v é irmão de w
v é pai ou mãe de w
v é amigo de w
O que determina a ordem de um grafo G?
O número de arestas de G
O número de vértices de G
O número de ciclos de G
O número de componentes de G
Em um grafo, dois vértices v e w são adjacentes se:
Há uma aresta a=(v,w) em G.
Não há aresta entre v e w.
v e w são isolados.
v e w são folhas.
Como é chamada a aresta que conecta dois vértices adjacentes em um grafo?
Aresta incidente
Aresta isolada
Aresta pendente
Aresta paralela
O que determina o grau de um vértice em um grafo?
O número de vértices conectados a ele
O número de arestas a ele incidentes
O número de ciclos no grafo
O número de componentes conexas
Para um grafo dirigido (G2), a noção de grau é especializada em:
Grau de emissão e grau de recepção
Grau de entrada e grau de saída
Grau de conexão e grau de desconexão
Grau de adjacência e grau de incidência
O grau de emissão de um vértice v corresponde ao número de:
Arcos que partem de v
Arcos que chegam a v
Vértices adjacentes a v
Vértices conectados a v
O grau de recepção de um vértice v corresponde ao número de:
Arcos que chegam a v
Arcos que partem de v
Vértices adjacentes a v
Vértices conectados a v
O que é um vértice fonte em um grafo?
Um vértice com grauDeRecepção(v) = 0
Um vértice com grauDeEmissão(v) = 0
Um vértice com grauDeRecepção(v) > 0
Um vértice com grauDeEmissão(v) > 0
Quais são os vértices fonte no grafo G2?
Renata e Emerson
Isadora, Alfredo e Cecília
Antonio e Cecília
Emerson e Isadora
O que é um vértice sumidouro em um grafo?
Um vértice com grauDeRecepção(v) = 0
Um vértice com grauDeEmissão(v) = 0
Um vértice com grauDeRecepção(v) > 0
Um vértice com grauDeEmissão(v) > 0
O que é um laço em um grafo?
Uma aresta que conecta dois vértices diferentes.
Uma aresta que conecta um vértice a ele próprio.
Uma aresta que conecta três vértices.
Uma aresta que não conecta nenhum vértice.
O que caracteriza um grafo regular?
Todos os vértices têm o mesmo grau.
Todos os vértices têm graus diferentes.
O grafo tem um número ímpar de vértices.
O grafo tem um número par de vértices.
Por que o grafo G4 é considerado um grafo regular-3?
Porque todos os seus vértices têm grau 3.
Porque tem 3 vértices.
Porque tem 3 arestas.
Porque é um grafo completo.
O que é um grafo completo?
Um grafo onde há uma aresta entre cada par de seus vértices.
Um grafo onde não há arestas.
Um grafo onde há apenas um vértice.
Um grafo onde há uma aresta entre alguns pares de vértices.
Como são designados os grafos completos?
K_n, onde n é a ordem do grafo.
G_n, onde n é a ordem do grafo.
H_n, onde n é a ordem do grafo.
J_n, onde n é a ordem do grafo.
O que é um grafo bipartido?
Um grafo onde todos os vértices estão conectados entre si.
Um grafo onde o conjunto de vértices pode ser particionado em dois subconjuntos, e toda aresta une um vértice de um subconjunto a outro do outro subconjunto.
Um grafo onde não há arestas.
Um grafo onde todos os vértices pertencem ao mesmo subconjunto.
Qual é a condição necessária para que um grafo seja considerado bipartido?
Que todos os vértices estejam conectados entre si.
Que o conjunto de vértices possa ser particionado em dois subconjuntos, e toda aresta una um vértice de um subconjunto a outro do outro subconjunto.
Que não haja arestas no grafo.
Que todos os vértices pertençam ao mesmo subconjunto.
O que é um grafo rotulado?
Um grafo onde cada vértice ou aresta está associado a um rótulo (descrição)
Um grafo onde todos os vértices são conectados
Um grafo que não possui rótulos
Um grafo que possui apenas um vértice
O que é um grafo valorado?
Um grafo onde os vértices ou arestas têm valores numéricos associados.
Um grafo onde todos os vértices são conectados.
Um grafo onde não há ciclos.
Um grafo onde todos os vértices têm o mesmo grau.
O que é um multigrafo?
Um grafo com múltiplos vértices.
Um grafo com múltiplas arestas entre pares de vértices.
Um grafo com um único vértice.
Um grafo sem arestas.
No exemplo G8, quais são os pares de vértices que têm duas arestas entre eles?
A e B, A e D
A e C, B e D
A e C, A e B
B e C, A e D
O que é um subgrafo?
Um grafo que contém todos os vértices e arestas de outro grafo.
Um grafo que é uma parte de outro grafo, contendo alguns vértices e arestas.
Um grafo que não tem nenhuma conexão com outro grafo.
Um grafo que é maior que outro grafo.
Quando um grafo ( G_s(V_s, A_s) ) é dito ser subgrafo de um grafo ( G(V,A) )?
Quando ( V_s ⊆ V ) e ( A_s ⊆ A ).
Quando ( V_s ⊇ V ) e ( A_s ⊇ A ).
Quando ( V_s ∩ V = ∅ ) e ( A_s ∩ A = ∅ ).
Quando ( V_s = V ) e ( A_s = A ).
Qual dos seguintes grafos é um exemplo de subgrafo de G8?
G1
G2
G9
G10
O que é uma cadeia em grafos?
Uma sequência de vértices adjacentes.
Uma sequência de arestas adjacentes.
Um conjunto de vértices isolados.
Um conjunto de arestas isoladas.
Para grafos orientados, o que se ignora ao definir uma cadeia?
O número de vértices.
O número de arestas.
O sentido da orientação dos arcos.
A cor dos vértices.
No grafo G11, quais vértices formam uma cadeia?
(x1, x2, x3, x4)
(x6, x5, x4, x1)
(x2, x3, x4, x5)
(x3, x4, x5, x6)
O que é um caminho em um grafo orientado?
Uma cadeia fechada onde o vértice inicial é o mesmo que o vértice final.
Um caminho fechado.
Uma cadeia de um grafo orientado na qual todos os arcos possuem a mesma orientação.
Um conjunto de vértices conectados por arestas.
Qual é a definição de um ciclo em um grafo?
Um caminho fechado.
Uma cadeia de um grafo orientado na qual todos os arcos possuem a mesma orientação.
Um conjunto de vértices conectados por arestas.
Uma cadeia fechada onde o vértice inicial é o mesmo que o vértice final.
O que é um circuito em um grafo?
Uma cadeia de um grafo orientado na qual todos os arcos possuem a mesma orientação.
Um caminho fechado.
Uma cadeia fechada onde o vértice inicial é o mesmo que o vértice final.
Um conjunto de vértices conectados por arestas.
O que é um grafo conexo?
Um grafo onde há pelo menos uma cadeia ligando cada par de vértices.
Um grafo onde não há nenhuma cadeia ligando os vértices.
Um grafo onde todos os vértices são isolados.
Um grafo onde há apenas um vértice.
Quais dos seguintes grafos são exemplos de grafos conexos?
G11 e G12
G11 e G13
G12 e G13
Nenhum dos grafos
O que é um grafo desconexo?
Um grafo onde há pelo menos um par de vértices que não está ligado por nenhuma cadeia.
Um grafo onde todos os vértices estão conectados.
Um grafo onde todos os vértices são isolados.
Um grafo onde há apenas um vértice.
O que é uma árvore em teoria dos grafos?
Um grafo desconexo com ciclos.
Um grafo conexo com ciclos.
Um grafo desconexo sem ciclos.
Um grafo conexo sem ciclos.
Para um grafo G(V,A) com ordem n ≥ 2, quais propriedades são suficientes para caracterizar G como uma árvore?
G é desconexo e tem ciclos.
G é conexo e tem ciclos.
G é desconexo e não tem ciclos.
G é conexo e não tem ciclos.
Qual é a ordem mínima de um grafo G(V,A) para que ele possa ser caracterizado como uma árvore?
n ≥ 1
n ≥ 2
n ≥ 3
n ≥ 4
Como são geralmente representadas as árvores?
Em linhas
Em colunas
Em níveis
Em círculos
Qual é o nível mais alto em uma árvore?
Folha
Nó
Galho
Raiz
O que é um grafo planar?
Um grafo onde todos os vértices estão conectados.
Um grafo onde nenhum par de arestas se cruza.
Um grafo com exatamente quatro vértices.
Um grafo que não pode ser desenhado em um plano.
Por que K₄ é considerado um grafo planar?
Porque tem exatamente quatro vértices.
Porque pode ser desenhado em um plano sem cruzamento de arestas.
Porque todas as arestas se cruzam.
Porque é um grafo completo.
Quais são exemplos de grafos não planares mencionados no texto?
K4 e K2,2
K5 e K3,3
K6 e K4,4
K7 e K5,5
O que é afirmado sobre os grafos K5 e K3,3 no texto?
Eles são exemplos de grafos planares.
Eles admitem representações planares.
Eles não admitem representações planares.
Eles são exemplos de grafos bipartidos.
O que é uma coloração de um grafo ( G )?
Uma atribuição de cores para cada aresta de ( G ).
Uma atribuição de cores para cada vértice de ( G ) de tal modo que a dois vértices adjacentes sejam atribuídas cores diferentes.
Uma atribuição de cores para cada vértice de ( G ) de tal modo que todos os vértices tenham a mesma cor.
Uma atribuição de cores para cada aresta de ( G ) de tal modo que todas as arestas tenham cores diferentes.
O que é uma ( k )-coloração de um grafo ( G )?
Uma coloração que utiliza um total de ( k ) vértices.
Uma coloração que utiliza um total de ( k ) arestas.
Uma coloração que utiliza um total de ( k ) cores.
Uma coloração que utiliza um total de ( k ) grafos.
