Skip to main content
adicionou 782 caracteres ao conteúdo
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

Adjacências e cliques

Um clique é um grafo em que todos os vértices são ligados uns com os outros (retirando a auto-ligação). Ou seja, uma matriz de adjacências de um clique de 3 vértices é isto:

0  1  1
1  0  1
1  1  0

A única mudança que pode haver é se existe alguma aresta que tem origem e destino no mesmo vértice, então na diagonal principal vai haver o valor verdade para essa ligação.

Quando se trata de uma matriz indicando as distâncias entre pontos em um plano (como a matriz existente nessa pergunta), então temos um clique, pois sempre é possível sair de um ponto e chegar no outro. Para casos assim, a matriz de adjacências é redundante, sendo preferível usar a matriz de distâncias.

Adjacências e cliques

Um clique é um grafo em que todos os vértices são ligados uns com os outros (retirando a auto-ligação). Ou seja, uma matriz de adjacências de um clique de 3 vértices é isto:

0  1  1
1  0  1
1  1  0

A única mudança que pode haver é se existe alguma aresta que tem origem e destino no mesmo vértice, então na diagonal principal vai haver o valor verdade para essa ligação.

Quando se trata de uma matriz indicando as distâncias entre pontos em um plano (como a matriz existente nessa pergunta), então temos um clique, pois sempre é possível sair de um ponto e chegar no outro. Para casos assim, a matriz de adjacências é redundante, sendo preferível usar a matriz de distâncias.

Número correto.
Fonte Link
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189
  1. o grafo é conexo?
  2. o grafo G é isomorfo ao grafo H? (só porque pode responder não quer dizer que seja fácil responder)
  3. quais são as pontes nesse grafo?
  4. qual o caminho/quais os caminhos entre os vértices i e j com menos saltos?1
  5. existe algum "poço" em relação ao subconjunto de vértices U? quais os vértices que pertencem a esse "poço"?12
  1. o grafo é conexo?
  2. o grafo G é isomorfo ao grafo H? (só porque pode responder não quer dizer que seja fácil responder)
  3. quais são as pontes nesse grafo?
  4. qual o caminho/quais os caminhos entre os vértices i e j com menos saltos?1
  5. existe algum "poço" em relação ao subconjunto de vértices U? quais os vértices que pertencem a esse "poço"?1
  1. o grafo é conexo?
  2. o grafo G é isomorfo ao grafo H? (só porque pode responder não quer dizer que seja fácil responder)
  3. quais são as pontes nesse grafo?
  4. qual o caminho/quais os caminhos entre os vértices i e j com menos saltos?1
  5. existe algum "poço" em relação ao subconjunto de vértices U? quais os vértices que pertencem a esse "poço"?2
conteúdo editado
Fonte Link
Jéf Bueno
  • 69,8mil
  • 22
  • 134
  • 244

se a matriz na posição (i,j) for verdade, então há aresta de i para j no grafose a matriz na posição (i,j) for verdade, então há aresta de i para j no grafo

se a matriz na posição (i,j) for verdade, então há aresta de i para j no grafo

se a matriz na posição (i,j) for verdade, então há aresta de i para j no grafo

Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158
Carregando