Matriz de incidência




Uma matriz de incidência representa computacionalmente um grafo através de uma matriz bidimensional, onde uma das dimensões são vértices e a outra dimensão são arestas.


Dado um grafo G com n vértices e m arestas, podemos representá-lo em uma matriz n x m M.
A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que se
deseja representar, porém de forma geral guarda informações sobre como os
vértices se relacionam com cada aresta (isto é, informações sobre a
incidência de uma aresta em um vértice[1]).


Para representar um grafo sem pesos nas arestas e não direcionado, basta que as entradas da matriz M contenham 1 se a aresta incide no vértice, 2 caso seja um laço (incide duas vezes) e 0 caso a aresta não incida no vértice.


Grafo com 4 vértices e 4 arestas

Por exemplo, a matriz de incidência do grafo ao lado é representada abaixo:





















































a
b
c
d
e
f

1
1
1
0
0
0
0

2
1
0
1
0
0
1

3
0
1
1
1
0
0

4
0
0
0
1
1
1

[110000101001011100000111]{displaystyle {begin{bmatrix}1&1&0&0&0&0\1&0&1&0&0&1\0&1&1&1&0&0\0&0&0&1&1&1\end{bmatrix}}}{displaystyle {begin{bmatrix}1&1&0&0&0&0\1&0&1&0&0&1\0&1&1&1&0&0\0&0&0&1&1&1\end{bmatrix}}}



Ver também |



  • Teoria dos grafos

  • Matriz de adjacência

  • Lista de adjacência



Referências




  1. Scheinerman, Edward R. (2011). Matemática Discreta: uma introdução. São Paulo: Cengage Learning. ISBN 978-85-221-0796-4 



















































Popular posts from this blog

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Aardman Animations

Are they similar matrix