WorksheetsQuiz sobre Grafos
Total questions: 25
Worksheet time: 19mins
Em um grafo G = (V, A), o conjunto V representa
as arestas
os vértices
os pesos
os caminhos
Dois vértices são adjacentes quando
pertencem ao mesmo subgrafo
existe uma aresta ligando-os
possuem o mesmo grau
formam um laço
O símbolo |V| indica
número de arestas
grau máximo
número de vértices
ordem das arestas
O grau de um vértice v, denotado por d(v), é
a maior distância a outro vértice
a contagem de vértices adjacentes a v
a quantidade de arestas incidentes em v
o comprimento mínimo de um caminho que parte de v
Um grafo direcionado é aquele em que
todas as arestas são laços
cada aresta tem orientação
não existem arestas paralelas
todos os vértices formam um clique
Um grafo completo com n vértices é indicado por
Pn
Cn
Kn
Dn
Uma aresta que liga um vértice a ele mesmo chama-se
multiaresta
laço
ponte
caminho
A existência de duas ou mais arestas entre o mesmo par de vértices caracteriza um
grafo simples
grafo conectado
multigrafo
subgrafo induzido
Um grafo simples é obrigatoriamente
sem laços e sem arestas múltiplas
direcionado e ponderado
completo e conexo
formado apenas por laços
A ordem de um grafo corresponde ao
número de componentes conexas
número total de arestas
número total de vértices
grau médio dos vértices
Em grafos direcionados, o grau de entrada de um vértice é
o total de arestas que partem dele
o total de arestas que chegam a ele
a soma dos laços em v
sempre igual ao grau de saída
Um vértice com grau 0 é classificado como
pendente
isolado
terminal
intermediário
Um vértice com grau 1 recebe o nome de
isolado
raiz
pendente (folha)
interno
Entre todos os vértices de um grafo, o grau mínimo é
o menor grau encontrado
metade do grau máximo
sempre zero
igual ao número de componentes
Se H é subgrafo de G, então
V(H) = V(G)
A(G) ⊆ A(H)
V(H) ⊆ V(G) e A(H) ⊆ A(G)
H é completo
Uma trilha difere de um passeio por
não repetir arestas
não repetir vértices
obrigar orientação nas arestas
ter comprimento mínimo
Um caminho é uma trilha que
não repete vértices nem arestas
possui pelo menos um laço
conecta todos os vértices
é direcionado
Um grafo é conexo se
possui pelo menos um laço
contém um subgrafo completo
existe caminho entre qualquer par de vértices
não possui multiarestas
Uma representação que utiliza uma matriz |V| × |V| com 0 e 1 para indicar adjacência denomina-se
lista de adjacência
matriz de incidência
matriz de adjacência
representação gráfica
Na lista de adjacência, cada vértice é
uma linha e uma coluna
um nó com a lista de vizinhos
um registro de grau
um valor na diagonal principal da matriz
O comprimento de um passeio corresponde ao
número de vértices visitados
soma dos graus dos vértices
número de arestas percorridas
distância entre os extremos
Se um grafo possui vértices isolados, ele
nunca é simples
é necessariamente desconexo
não pode ter grau mínimo
é sempre completo
Em um multigrafo, duas arestas entre o mesmo par de vértices são chamadas
paralelas
direcionadas
cruzadas
diagonais
O termo grau de saída em grafos direcionados refere-se às arestas que
chegam ao vértice
partem do vértice
formam laços
conectam vértices não adjacentes
Em K5 (grafo completo com 5 vértices), cada vértice tem grau
3
4
5
10
