< Avançar | Voltar | Content >
Matriz de Adjacências: Vértice ao Vértice
O gráfico família argumenta que uma das melhores formas para representá-los em uma matriz é através da contagem do número de uma aresta entre dois vértices adjacentes.
dois vértices são ditos adjacentes ou vizinhos se suportam pelo menos uma aresta comum.
vamos começar com exemplo
grafo abaixo tem três vértices. Assim, fazemos uma matriz de adjacência de tamanho 3 por 3. Então colocamos o nome de vértices no lado da matriz. Olhe para a imagem e começamos com uma matriz vazia. Apenas os nomes dos vértices existem
Para preencher a matriz de adjacências, olhamos para o nome de vértice na linha e coluna. Se esses vértices são conectados por uma aresta ou mais, nós contamos o número de arestas e colocamos este número como elemento de matriz.
Vértice 
e vértice 
tem uma aresta comum, dizemos que o Vértice 
e vértice 
são adjacentes (vizinho). Nós introduzimos o número de aresta na célula de matriz que corresponde ao vértice 
e vértice 
.
Vértice 
e 
é adjacente por uma borda. Thus, we input the number of edge in the matrix cell that correspond to Vertex 
e 
.
da mesma forma, vértice 
e 
está ligado por uma aresta. Thus, we input the number of edge in the matrix cell that correspond to vertex 
and 
não Existe nenhuma outra borda do gráfico, assim podemos colocar o resto das células não preenchidas na matriz como zero
A matriz para representar um gráfico desta forma é chamado de matriz de Adjacências .
O tamanho da matriz de adjacência é igual ao número de vértices no grafo. É uma matriz quadrada (que é o número de linhas é igual ao número de colunas).
a matriz de adjacência de um grafo é simétrica porque não tem direção. Dois vértices compartilham a mesma aresta podem ser chamados da primeira para a segunda, ou da Segunda para a primeira. For example, Vertex 
and vertex has one common edge, then element (A, b) = 1 and element (b, a) = 1.
vamos tentar outro exemplo:
pode fazer a matriz de adjacência deste gráfico? Tente primeiro antes de olhar para a resposta abaixo.
O grafo tem 3 vértices, assim fazemos uma matriz de tamanho 3 por 3. Colocamos o nome de vértices no lado da matriz.
Agora olhe para o vértice 
e vértice 
. Quantas arestas suportam os dois vértices? Um. Em seguida, vamos colocar esse valor na matriz
Olhar no vértice 
e vértice 
. Quantas arestas suportam estes vértices? Nenhum. Então, colocamos o valor zero na célula correspondente na matriz
seguinte, você olha para o vértice 
e vértice 
. Quantas areias estes vértices suportam? Dois. Então introduzimos a matriz em
Uma vez que não há outra aresta no grafo, podemos preencher a célula vazia com zeros. Thus, we have the answer
alguns de vocês podem perguntar sobre a parte diagonal da matriz, estas células são sempre zero? Não, se você achar que o grafo tem algum loop em alguns vértices, você pode preencher o elemento diagonal da matriz de adjacência com o número de loop.
Se um grafo tem algum vértice que não está conectado a quaisquer outros vértices, a matriz de adjacência corresponde a esse vértice único é zero.
Por favor, faça alguma prática para representar o gráfico abaixo na matriz de adjacência.
(ver a resposta na página anterior)
dada a matriz de adjacência, pode retirar o gráfico?
Check example application of graph theory in Q-Learning Tutorial
< Back / Next / Content >