UNIVERSIDADE DA BEIRA INTERIOR

Ciências

Matrizes e Grafos
Versão definitiva após defesa pública

Elias Tchivembe

Dissertação para obtenção do Grau de Mestre em

Matemática Para Professores
(2.º Ciclo de Estudos)

Orientadora: Professora Doutora Ana Catarina Santos Carapito

Coorientadora: Professora Doutora Ilda Inácio

Covilhã, julho de 2018

 Matrizes e Grafos

ii
Matrizes e Grafos

Dedicatória

À minha esposa Cecília e aos nossos filhos, Regina, Etiandro, Edmárcio, Edmilson e Sachiela,
cujo apoio, encorajamento e orações a meu favor, tornaram este sonho uma realidade.

iii
 Matrizes e Grafos

iv
Matrizes e Grafos

Agradecimentos

Agradeço a Deus em primeiro lugar pelo dom da vida e por permitir que se cumpra mais uma
etapa na minha carreira académica.

Aos meus pais que não pouparam esforços em apostar na minha formação e mesmo nas dificul-
dades sempre acreditaram que poderia ir mais longe.

Agradeço de igual modo aos meus irmãos, aos meus afilhados Pedro Andito e Elisa Andito, aos
meus amigos, colegas e a família cristã por todo suporte material, moral e espiritual.

Faço um agradecimento especial à minha esposa Cecília Kanhãnga que me ajudou nesta empre-
itada dando incentivos à distância todos os dias e sempre compreendeu a minha ausência no
convívio familiar. Todo mérito para ela, pois soube liderar o nosso lar na minha ausência.

Manifesto a minha gratidão às minhas orientadoras, Professora Doutora Ana Catarina Santos
Carapito e Ilda Carla Inácio pelo rigor científico e por me ajudarem a melhorar as minhas debil-
idades.

Finalmente agradeço ao governo angolano pela oportunidade da formação, a qual me dará com
certeza a possibilidade de poder contribuir para a melhoria da qualidade do ensino em Angola.

v
 Matrizes e Grafos

vi
Matrizes e Grafos

Resumo

No seguimento do trabalho desenvolvido nas Unidades Curriculares dos Projetos de Ensino do

2.º Ciclo em Matemática para Professores, nas áreas de Teoria de Matrizes e Grafos, aprofun-
damos os conceitos e resultados envolvidos e, ao mesmo tempo, estabelecemos uma ligação ao
ensino apresentando uma abordagem adequada à leccionação daqueles ao ensino secundário.
A importância da Teoria de Matrizes e Grafos é amplamente reconhecida em diversas áreas,
nomeadamente na Engenharia, Física e Ciências da Computação. Como tal, apresentamos neste
trabalho algumas aplicações com o intuito de realçar o alcance da Teoria de Matrizes e Grafos
na vida quotidiana e, com isto, contribuir para o enriquecimento do ensino destes conceitos no
ensino ao optar por apresentá-las em contexto de sala de aula.
Não menos importante que a aplicabilidade da Teoria de Matrizes e Grafos, é o respetivo en-
quadramento histórico que contemplamos neste trabalho.

Palavras-chave

Matrizes, Transformações Lineares, Grafos, Matriz de Adjacência, Matriz de Incidência.

vii
 Matrizes e Grafos

viii
Matrizes e Grafos

Abstract

Following the work developed in the Curricular Units of Teaching Projects of the 2nd Cycle in
Mathematics for Teachers, in the areas of Theory of Matrices and Graphs, we deepen the con-
cepts and results involved and at the same time, we have established a connection to teaching
by presenting an appropriate approach to the teaching of those to secondary education.
The importance of Theory of Matrices and Graphs is widely recognized in several areas, namely
in Engineering, Physics and Computer Science. As such, we present in this work some applica-
tions in order to highlight the reach of Matrix Theory and Graphs in daily life and with this, to
contribute to the enrichment of the teaching of these concepts in the teaching when choosing
to present them in context of classroom.
No less important than the applicability of Theory of Matrices and Graphs, is the respective
historical framework that we contemplate in this work.

Keywords

Matrices, Linear Transformations, Graphs, Adjacency Matrix , Incidence Matrix.

ix
 Matrizes e Grafos

x
Matrizes e Grafos

Conteúdos

1 Introdução 1
1.1 Breve historial das matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Breve historial dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Matrizes 5
2.1 Definições e Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Operações com matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Inversa de uma matriz quadrada . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Transposição de Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Sistemas de Equações Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.1 Matrizes elementares . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6 Determinante de uma Matriz Quadrada . . . . . . . . . . . . . . . . . . . . . . 17
2.7 Transformações Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Subspaços Fundamentais de uma matriz . . . . . . . . . . . . . . . . . . 25
2.7.2 Matriz de uma transformação linear . . . . . . . . . . . . . . . . . . . . 28

3 Algumas Aplicações de Matrizes 31

3.1 Aplicação à Economia: Modelo Fechado [de Input-Output] de Leontief . . . . . . 31
3.2 Aplicação à Química (Equilibrando equações) . . . . . . . . . . . . . . . . . . . 33
3.3 O problema de Alocação de Tarefas . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Aplicação à Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Teoria de Grafos 41
4.1 Conceitos e resultados fundamentais . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Grafos e Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.1 Matriz de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 Matriz de Incidência . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.3 Espaço vetorial do conjunto de vértices . . . . . . . . . . . . . . . . . . 55
4.3 Matriz de circuito e matriz de caminho . . . . . . . . . . . . . . . . . . . . . . 56

5 Considerações Finais 61

Bibliografia 63

xi
 Matrizes e Grafos

xii
Matrizes e Grafos

Lista de Figuras

1.1 Problema das pontes de Königsberg . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Grafo do problema das pontes de Königsberg. . . . . . . . . . . . . . . . . . . . 3

4.1 O primeiro grafo é não orientado e o segundo é orientado. . . . . . . . . . . . 42

4.2 Os grafos são complementares. . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Grafos completos K1 , · · · , K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Grafos bipartidos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.6 Grafo desconexo com duas componentes. . . . . . . . . . . . . . . . . . . . . . 46
4.7 Floresta formada por três árvores . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.8 Grafo G e três árvores abrangentes de G. . . . . . . . . . . . . . . . . . . . . . 47
4.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.11 Grafo completo K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.12 Árvores abrangentes do grafo completo k3 . . . . . . . . . . . . . . . . . . . . . 52
4.13 Grafo G da matriz de Incidência . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.14 Grafo orientado e sua matriz de Incidência . . . . . . . . . . . . . . . . . . . . 53
4.15 Grafo G e sua matriz de incidência . . . . . . . . . . . . . . . . . . . . . . . . 55
4.16 Árvore abrangente do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.17 Grafo e sua matriz de incidência . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.18 Árvore abrangente e a sua matriz fundamental de circuito. . . . . . . . . . . . . 59

xiii
 Matrizes e Grafos

xiv
Matrizes e Grafos

Lista de Tabelas

1.1 Esquematização do problema em tabela . . . . . . . . . . . . . . . . . . . . . 1

3.1 Distribuição dos concertos por casas. . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Escavadeiras e as distâncias em relação aos locais de construção . . . . . . . . . 36
3.3 Cifras de substituição letra por letra. . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Cifras de substituição letra por número. . . . . . . . . . . . . . . . . . . . . . 38

xv
 Matrizes e Grafos

xvi
Matrizes e Grafos

Capítulo 1

Introdução

Nesta secção aprestaremos em síntese a história das matrizes e grafos. Para tal usamos as
referências [7], [8] e [12].

1.1 Breve historial das matrizes

A história da matemática retrata que o estudo das matrizes vem de tempos muito antigos da hu-
manidade. Elas estão presentes em textos chineses, por volta do século II a.c, aplicadas em prob-
lemas de resolução de equações lineares. O livro chinês ”Nove Capítulos da Arte matemática”
em seu capítulo VII, traz 20 problemas com exceção de apenas um deles, que apresentam o
método das matrizes para resolver equações lineares através da regra chamada ”dupla falsa
posição”. Vejamos um exemplo:”A idade da Joana, somada de outro tanto com ela, somada
com a sua metade, com a sua terça parte e com a sua quarta parte, dá o resultado 148. Qual a
idade da Joana?” Para resolver este problema, escolhe-se o número ”falso” e supõe-se que 12
é a idade da Joana. Então facilmente se conclui que 37 seria a idade da Joana (resultado de
12+12+6+4+3). Esquematizando o mesmo problema através de um quadro ou matriz:

Número(idade) Resultado
Falso 12 37
Verdadeiro x 148

Tabela 1.1: Esquematização do problema em tabela

Concluímos que recorrendo à proporção

12 37
=
x 148

a Joana tem 48 anos de idade.

Outro tipo de problema abordado no livro chinês ”Nove capítulos da arte matemática” no capí-
tulo VIII tem que ver com a resolução de sistemas de equações com 2 e 3 incógnitas por meio de
tabelas e processos que lembram as resoluções matriciais, tal como se pode constatar no exem-
plo que apresentamos:Cinco contentores grandes e um contentor pequeno têm, no conjunto,
uma capacidade de 3hu, enquanto que um contentor grande e cinco contentores pequenos
têm a capacidade de 2hu. Determine a capacidade de cada um dos contentores. Considere
1hu=10tou1 .

A resolução passa por alguns passos, cabendo ao primeiro a organização da informação: numa
tabela com três linhas e duas colunas, do tipo daquelas que hoje identificamos como uma matriz,
a primeira linha era reservada para o número de contentores grandes, a segunda linha para o
número de contentores pequenos e a terceira para a capacidade conjunta.
1
1tou=10 litros

1
 Matrizes e Grafos

 
1 5
 
5 1
2 3

Através de operações elementares (combinações lineares) sobre colunas, anulavam alguns el-
ementos e liam as soluções; assim, da matriz infra concluíam que a capacidade do contentor
7
pequeno era 24 hu.

 
0 5
 
24 1
7 3

O método de resolução de sistemas de equações lineares apresentado constitui um dos maiores

empreendimentos algébricos da obra Nove Capítulos e é considerado uma invenção chinesa.

Nas obras Matemáticas chinesas, percebe-se, ainda, o quanto eles gostavam de diagramas de
formato quadrado: os quadrados mágicos.

4 9 2
3 5 7
8 1 6

Matematicamente um ”quadrado mágico elementar” representa uma matriz quadrada(mesmo

número de linhas e colunas) de ordem n (n linhas e n colunas), cujos elementos (números
naturais) variam sucessivamente de 1 até n, 2 que são arrumados de modo que a soma de cada
linha, cada uma das suas diagonais principais ou de cada coluna seja sempre uma constante.
O quadrado mágico foi supostamente trazido para os homens por uma tartaruga do Rio Lo nos
dias do lendário Imperador Yii, considerado um engenheiro hidráulico. A preocupação com tais
diagramas levou o autor dos Nove capítulos a resolver o sistema de equações lineares simultâneas

3x + 2y + z = 39

2x + 3y + z = 34

x + 2y + 3z = 26

É portanto um facto que a aplicação das matrizes possui uma forte componente histórica na
resolução de equações lineares.

Ao longo dos tempos, surgiram muitos matemáticos que desenvolveram métodos de resolução
de equações lineares baseadas em tabelas numéricas que deram origem ao que hoje chamamos
matrizes, que além de serem aplicadas ao estudo de sistemas lineares, possibilitam o desen-
volvimento de novos ramos da matemática.

Atualmente as matrizes são aplicadas em inúmeras áreas tais como na Economia, na Criptografia,
na Pesquisa Operacional para resolução dos problemas de alocação de tarefas, na engenharia e
muitas outras áreas.

2
Matrizes e Grafos

1.2 Breve historial dos Grafos

A teoria dos grafos é relativamente recente, tendo origem no século XVIII com o conhecido
problema das pontes de Königsberg, talvez o mais conhecido exemplo na teoria de grafos.
Este problema foi resolvido pelo matemático Leonhard Euler (1707-1783) em 1736. Parte da
cidade de Königsberg (a então capital de Prussia e hoje Kaliningrad) , localizava-se em duas
ilhas do rio Pregel as quais estavam ligadas às margens e uma à outra através de sete pontes,
conforme ilustra a figura 1.1 [6] página 22:

Figura 1.1: Problema das pontes de Königsberg

Pôs-se então a questão a saber, se de algum modo, seria possível passear através da cidade
atravessando todas as pontes exatamente uma vez e regressar ao ponto de partida. Ninguém
conseguiu encontrar um caminho que satisfizesse o problema, nem tão pouco justificar a sua
impossibilidade, até ao ano de 1736. Foi neste ano que o matemático Leonhard Euler solucionou
o problema e apresentou uma justificação da não possibilidade de existência de um caminho
nas condições impostas.

Para tal Euler recorreu à construção do grafo associado ao mapa da cidade, considerando as
áreas da terra assinaladas por A, B, C e ILHA como vértices do grafo e as pontes como as
respetivas arestas conforme ilustra a figura 1.2 [6] Página 22.

Figura 1.2: Grafo do problema das pontes de Königsberg.

Desde esta data surgiram muitos outros problemas, alguns de caráter lúdico, contudo, tornaram-
se célebres dada a sua aplicabilidade na resolução de problemas do quotidiano. No entanto, o
grande desenvolvimento da teoria dos grafos só veio a notar-se no século XX, tanto ao nível da

3
 Matrizes e Grafos

matemática como das suas aplicações nos diversos campos do conhecimento.

A teoria dos grafos é uma ”ferramenta” fundamental na resolução de problemas em diversas
áreas da matemática, da informática, da engenharia, da química, da psicologia, da economia e
da indústria;
Em termos práticos, tendo em conta vários campos profissionais, a teoria dos grafos permite-nos,
por exemplo, representar um mapa de estradas, usar algoritmos específicos para determinar o
caminho mais curto ou o mais económico entre dois pontos, estudar e compreender a interação
social, entre outros.

4
Matrizes e Grafos

Capítulo 2

Matrizes

Neste capítulo, apresentamos alguns conceitos da Teoria de Matrizes e apresentamos as no-

tações que irão ser usadas ao longo deste trabalho. Para o efeito, recorremos a referências
bibliográficas comumente conhecidas, tais como [?], [4] e [5].

2.1 Definições e Generalidades

Definição 2.1.1. Chama-se Matriz do tipo m × n sobre R (ou C) a todo quadro que se obtém
dispondo mn números - elementos/entradas da matriz- segundo m linhas e n colunas.
Uma matriz diz-se real ou complexa consoante os seus elementos sejam números reais ou com-
plexos.
O conjunto das matrizes do tipo m × n sobre R representa-se por Mm×n (R). Usamos a notação
Rn para Mn×1 (R).

Exemplo 2.1.1.    
[ ] 0 −2 7 2
1 2 7    
, 1 2 3 e  4 
−5 3 8
12 5 8 9

são matrizes reais do tipo 2 × 3, 3 × 3 e 3 × 1, respetivamente. A primeira pertence a M2×3 (R),

a segunda a M3×3 (R) e a terceira a R3 .

Usam-se letras romanas maiúsculas para designar matrizes. Numa matriz abstrata é comum
designar os elementos por uma letra minúscula com dois índices, indicando o primeiro a linha
da matriz em que o elemento se encontra e o segundo a coluna.

Deste modo, se A for uma matriz do tipo m × n, então aij é o elemento de A situado na linha i e
coluna j, com i ∈ {1, · · · , m} e j ∈ {1, · · · , n}. Tal elemento é também referido como elemento
de A na posição (i, j) ou apenas por elemento (i, j) de A.

Assim, uma matriz abstrata do tipo m × n é habitualmente apresentada da seguinte forma:

 
a11 a12 a13 ··· a1n
 
 a21 a22 a23 ··· a2n 
 
 ··· a3n 
A =  a31 a32 a33 
 . .. .. .. 
 . .. 
 . . . . . 
am1 am2 am3 ··· amn

que também pode ser apresenta por A = [aij ]m×n , ou simplesmente A = [aij ], se o tipo da
matriz for conhecido a partir do contexto ou não comprometer o entendimento da abordagem.

5
 Matrizes e Grafos

Na definição seguinte registamos terminologias e notações básicas relativas a matrizes.

Definição 2.1.2. 1. Duas matrizes A = [aij ] e B = [bij ] ∈ Mm×n (R) são iguais se aij = bij ,
para todo o i = 1, · · · , m e para todo o j = 1, · · · , n.

2. Mm×n (R) diz-se quadrada de ordem n se m = n, e retangular se m ̸= n.

3. Os elementos diagonais de A = [aij ] ∈ Mm×n (R) são a11 , a22 , · · · , ann . A sequência orde-
nada constituída por estes elementos diz-se diagonal principal de A.

4. Seja A = [aij ] quadrada. A diz-se triangular superior se aij=0 quando i > j, triangular
inferior se aij = 0 quando i < j, e diagonal se aij = 0 quando i ̸= j.

5. A matriz identidade de ordem n,In , é a matriz diagonal, de ordem n, com os elementos

diagonais iguais a 1.

 
1 0 0 ··· 0
 
0 1 0 ··· 0
 
 0
In = 0 0 1 ... 
. .. .. .. 
. 
. . . ··· .
0 0 0 ··· 1

Se a ordem da matriz tiver clara a partir do contexto, usamos simplesmente I.

6. A matriz nula m×n é a matriz m×n cujos elementos são todos iguais a zero. Representa-
se por 0m×n ou simplesmente por 0 se o tipo da matriz tiver claro a partir do contexto.

7. Sendo A = [aij ]m×n , define-se −A = [−aij ]m×n .

8. Sendo A uma matriz, uma submatriz de A é uma matriz que se obtém por supressão de
linhas e/ou colunas de A.

[ ] [ ]
1 2 7 a 2 7
Exemplo 2.1.2. As matrizes e são iguais se a = 1 e b = 3. Estas duas
−5 3 8 8 −5 b
 
10 5 −7
 
matrizes são retangulares, enquanto a matriz A =  8 2 3  é quadrada de ordem 3. Os
15 6 5
elementos diagonais de A são 10, 2, 5 e a sua diagonal principal é (10, 2, 5).
     
1 2 −7 1 0 0 2 0 0
     
As matrizes 0 2 1  7 3 0 e 0 2 0 são, respetivamente, triangular superior,
0 0 −2 5 0 5 0 0 7
triangular inferior e diagonal.
   
[ ] 5 −7 10 5 −7
10 −7    
As matrizes e 2 3  são exemplos de submatrizes de A =  8 2 3.
15 5
6 5 15 6 5

Neste trabalho precisamos da igualdade de duas matrizes do mesmo tamanho, mas numa abor-
dagem de congruência módulo k. Ou seja, considerando duas matrizes arbitrárias A = [aij ] e
B = [bij ] em Mm×n (R) dizemos que A e B são iguais módulo k se aij ≡ bij (mod k), para todo
o i = 1, · · · , m e para todo o j = 1, · · · , n. Denotamos A = B(mod k).

6
Matrizes e Grafos

2.2 Operações com matrizes

Definição 2.2.1. Sejam A, B ∈ Mm×n (R). Chamamos matriz soma da matriz A com a matriz
B, e denotamos por A + B, à matriz de Mm×n (R) cuja entrada (i, j) é Aij + Bij , isto é,

(A + B)ij = Aij + Bij , i = 1, · · · , m; j = 1, · · · , n.

[ ] [ ]
2 −3 0 −3 1 4
Exemplo 2.2.1. 1. sendo e tem-se
0 5 1 2 0 3
[ ]
−1 −2 4
A+B =
2 5 4

Propriedades 1. Sejam A,B e C matrizes arbitrárias em Mm×n (R). Então verifica-se:

1. A + B = B + A (Comutatividade da adição).

2. A + (B + C) = (A + B) + C (Associatividade da adição).

3. A + 0m×n = 0m×n + A = A (A matriz nula é o elemento neutro da adição).

4. A + (−A) = (−A) + A = 0m×n (−A é o elemento simétrico ou oposto de A).

Definição 2.2.2. Sejam α ∈ R e A ∈ Mm×n (R). Chamamos matriz produto do escalar α pela
matriz A, e denotamos por αA.

[ ]
2 2 −3 0
Exemplo 2.2.2. Dado o número real α = 3 e a matriz A = 7
, tem-se:
5 1 5
[ ]
2 4
3 −2 0
α.A = .A = 10 2 14
3 3 3 15

Propriedades 2. Sejam A, B ∈ Mm×n (R) e α , β ∈ R. Tem-se:

1. α(A + B) = αA + αB.

2. (α + β)A = αA + βA.

3. (αβ)A = α(βA).

4. 1.A = A

5. (−α)A = α(−A) = −(αA) e, em particular, (−1)A = −A.

6. Se αA = 0m×n então α = 0 ou A = 0m×n

Definição 2.2.3. Sendo A = [aij ] ∈ Mm×n (R) e B = [bij ] ∈ Mn×p (R), define-se AB como sendo
a matriz do tipo m × p cujo elemento (i, j) é

ai1 b1j + ai2 b2j + · · · + ain bnj .

7
 Matrizes e Grafos

Assim,
[∑ ]
n
AB = k=1 aik bkj . .
m×p

Depreende-se da definição que o produto AB da matriz A pela matriz B, apenas está definido
se o número de colunas de A for igual ao número de linhas de B. Neste caso o número de linhas
da matriz AB é igual ao número de linhas de A e o número de de colunas é igual ao de B. O
elemento de AB situado na linha i e coluna j obtém-se a partir da linha i de A e da coluna j de
B:
 
  ··· b1j ···  
··· ··· ··· ···   ··· ··· ···
  · · · b2j · · ·  
ai1 ai2 ··· ain  
 .. .. 
..  = · · · ai1 b1j + ai2 b2j + · · · +ain bnj · · · .
. . .
··· ··· ······ ··· ··· ···
··· bnj ···

Vemos assim que, para cada i = 1, · · · , m, a linha i de AB se obtém multiplicando a linha i de A

pela matriz B, e que, para cada j = 1, · · · , p, a coluna j de AB se obtém multiplicando a matriz
A pela coluna j de B.

Ilustremos com um exemplo prático o produto de duas matrizes.

Exemplo 2.2.3. Durante a 1.ª fase do Europeu de Futebol 2004, o grupo de Portugal era for-
mado também pela Grécia, Espanha e Rússia, os resultados registados apresentam-se na tabela
seguinte:
País/Resultado Vitória Empate Derrota
Portugal 2 0 1
Grécia 1 1 1 .
Espanha 1 1 1
Rússia 1 0 2

Para apurar a pontuação obtida por cada equipa consideremos, a partir dos dados apresentados,
a matriz (4 × 3) que representa os resultados de cada equipa:
 
2 0 1
 
1 1 1
A=
1
.
 1 1
1 0 2

Consideremos ainda a pontuação obtida em cada jogo de acordo com a seguinte tabela

Número de pontos
Vitória 3
,
Empate 1
Derrota 0

à qual está associada a matriz, 3 × 1,  

3
 
B = 1 .
0

8
Matrizes e Grafos

Assim, terminada a 1.ª fase, a pontuação obtida por cada país é dada por:

Portugal: 2.3 + 0.1 + 1.0 = 6

Grécia : 1.3 + 1.1 + 1.0 = 4
Espanha: 1.3 + 1.1 + 1.0 = 4
Rússia:1.3 + 0.1 + 2.0 = 3.
 
6
 
4
Em termos matriciais, a pontuação pode ser dada pela matriz AB: AB =  
4 .
 
3
 
[ ] 5 4 3
1 2 7  
Exemplo 2.2.4 (Outros exemplos). 1. Sejam A = e 8 0 6. Então AB =
9 3 8
1 2 9
[ ]
28 18 78
.
77 52 117
Note-se que neste caso o produto BA não está definido, visto o número de colunas de B
ser diferente do número de linhas de A.
 
[ ] 2
 
2. Sejam A = 3 1 5 e 7. Então
4
 
[ ] [ ] 6 2 10
 
AB = 3 × 2 + 1 × 7 + 5 × 4 = 33 e BA = 21 7 35 .
12 4 20

     
3 0 0 5 0 0 15 0 0
     
3. Sejam A = 0 5 0 e B = 0 7 0. Então AB = BA =  0 35 0
0 0 1 0 0 9 0 0 9
[ ] [ ]
1 2 4 −6
4. Sendo A = eB= , tem-se
−1 −2 −2 3
[ ] [ ]
0 0 10 20
AB = e BA = .
0 0 −5 −10

Como pode ser observado nestes exemplos, a multiplicação de matrizes comporta-se de modo
diferente da multiplicação de números. Dadas as matrizes A e B, pode acontecer estar o produto
AB definido, mas o produto BA não estar. Estando AB e BA definidos, nada implica que AB
seja igual a BA. Se AB = BA, dizemos que as duas matrizes comutam.
De realçar ainda que o produto de duas matrizes pode ser nulo sem que nenhuma delas o seja
(conforme 4.).

Propriedades 3. Sejam A, A′ ∈ Mm×n (R), B, B ′ ∈ Mn×p (R), C ∈ Mp×p (R), matrizes arbi-
trárias e α ∈ R. Então tem-se:

1. A0n×p = 0m×p , 0r×m A = 0r×n , AIn = Im A = A.

2. (AB)C = A(BC)(Associativa da multiplicação).

9
 Matrizes e Grafos

3. A(B + B ′ ) = AB + AB ′ , (A + A′ )B = AB + A′ B (distributividades do produto em relação

à adição).

4. α(AB) = (αA)B = A(αB).

5. AB = 0 ⇏(A = 0 ou B = 0).

6. (AB = AB ′ e A ̸= 0) ⇏ B = B ′ , e também (AB = A′ B e B ̸= 0) ⇏ A = A′ .

7. A multiplicação de matrizes não é comutativa.

Através do resultado que se segue, apresentamos um conceito muito importante da Álgebra

Linear - o de combinação linear.

Teorema 2.2.1. Seja A ∈ Mm×n (R) e designe-se vj a coluna j de A, j = 1, · · · , n. Dada a matriz

coluna  
x1
 
 x2 
x= 
 ..  ,
.
xn

tem-se Ax = x1 v1 + x2 v2 + · · · + xn vn . Dizemos então que Ax é uma combinação linear das

colunas de A.

Demonstração: Atendendo à definição de produto de matrizes, tem-se

  
a11 a12 a13 ··· a1n x1
  
 a21 a22 a23 ··· a2n   x2 
Ax = 
 .. .. .. .. ..   
 . 
 . . . . .   .. 
am1 am2 am3 · · · amn xn
 
a11 x1 + a12 x2 + · · · + a1n xn
 
 a21 x1 + a22 x2 + · · · + a2n xn 

=  
··· 
 
am1 x1 + am2 x2 + · · · + amn xn
     
a11 a12 a1n
     
 a21     
= x1   + x2  a22  + · · · + xn  a2n 
 ···   ···   ··· 
     
am1 am2 amn

= x 1 v1 + x 2 v2 + · · · + x n vn .

Note-se que, uma vez que AB se obtém multiplicando A pelas colunas de B, podemos concluir
deste teorema que as colunas de AB são combinações lineares das colunas de A.

2.3 Inversa de uma matriz quadrada

Definição 2.3.1. Seja A ∈ Mn×n (R).Dizemos que A é invertível, ou que A tem inversa, se
existir uma matriz B ∈ Mn×n (R) tal que

10
Matrizes e Grafos

AB = BA = In .

Teorema 2.3.1. Se A ∈ Mn×n (R) é invertível então existe uma, e uma só, matriz B tal que
AB = In = BA.

Demonstração: Suponhamos que B, C ∈ Mn×n (R) são tais que

AB = In = B e AC = In = CA

e demonstremos que B = C. De facto, tem-se

B = BIn = B(AC) = (BA)C = In C = C.

Definição 2.3.2. Se A ∈ Mn×n (R) é invertível, à única matriz B tal que AB = In = BA

chamamos inversa de A e representamos por A−1 .

Se A ∈ Mn×n (R) é invertível tem-se, pois,

AA−1 = In = A−1 A.

Teorema 2.3.2. Seja A ∈ Mn×n (R) uma matriz invertível.

1. Se B ∈ Mn×n (R) é tal que AB = In então B = A−1 .

2. Se B ∈ Mn×n (R) é tal que BA = In então B = A−1 .

Demonstração:

1. Como A é invertível, A−1 existe (e é única). Da igualdade

AB = In

resulta, multiplicando ambos os membros, à esquerda, por A−1 ( isto é, A−1 (AB) =
A−1 In ):
(A−1 A)B = A−1

o que é equivalente a
In B = A−1 ,

isto é,
B = A−1 .

2. Demonstração análoga à anterior: partindo da igualdade BA = In e seguidamente multi-

plicando ambos os membros, à direita, por A−1 .

11
 Matrizes e Grafos

Exemplo 2.3.1.

[ ] [ ][ ] [ ][ ]
3 5 3 5 2 5 2 5 3 5
1. Seja A = . Como = I2 e =I2 con-
−1 −2 −1 −2 −1 −3 −1 −3 −1 −2
[ ]
2 5
cluímos que A é invertível e que A−1 = .
−1 −3

2. In é invertível e (In )−1 = In pois

In In = In = In In .

3. Se A ∈ Mn×n (R) tem uma linha nula, então A é não invertível pois,para qualquer matriz
B ∈ Mn×n (R), AB tem uma linha nula e, portanto, AB ̸= In .

4. Se A ∈ Mn×n (R) tem linhas i e j iguais, com i ̸= j, então A não é invertível pois, para
qualquer matriz B ∈ Mn×n (R), AB tem as linhas i e j iguais pelo que AB ̸= In .

Terminamos esta secção apresentando algumas propriedades das matrizes invertíveis.

Propriedades 4. As matrizes invertíveis gozam das seguintes propriedades

1. Se A ∈ Mn×n (R) é invertível, então A−1 é invertível e

(A−1 )−1 = A.

2. Se α ∈ R\{0} e A ∈ Mn×n (R) é invertível então αAé invertível e

(αA)−1 = α−1 A−1 .

3. Se A, B ∈ Mn×n (R) são invertíveis então AB é invertível e

(AB)−1 = B −1 A−1 .

4. Mais geralmente, se k ∈ N e A1 , · · · , Ak ∈ R são invertíveis então A1 · · · Ak é invertível e

(A1 · · · Ak )−1 = A−1 −1

k · · · A1 .

5. Se A ∈ Mn×n (R) é invertível então, para qualquer k ∈ N, Ak é invertível e

(Ak )−1 = (A−1 )k .

Observações:

• (A + B)−1 ̸= A−1 + B −1 ;

• Se uma matriz quadrada admite inversa diz-se uma matriz regular;

• Se uma matriz quadrada não admite inversa, diz-se uma matriz singular;

12
Matrizes e Grafos

2.4 Transposição de Matrizes

Definição 2.4.1. Dada uma matriz do tipo m × n

 
a11 a12 a13 ··· a1n
 
 a21 a22 a23 ··· a2n 
A=
 .. .. .. .. .. 

 . . . . . 
am1 am2 am3 ··· amn

define-se a transposta de A como sendo n × m

 
a11 a21 a13 ··· am1
 
 a12 a22 a23 ··· am2 
AT = 
 ..

 .
..
.
..
.
..
. ... 

a1n a2n am3 ··· amn

Ou seja: o elemento (i, j) de AT é aij , para i = 1, · · · , n , j = 1, · · · , m.

A matriz A diz-se simétrica se A = AT .

Como se vê pela definição, os elementos da coluna j de AT são da linha j de A, para j =

1, · · · , m. Vemos também que uma matriz é simétrica se e só se for quadrada e forem iguais os
elementos situados em posições simétricas relativamente à diagonal principal.

Exemplo 2.4.1.
 
[ ] 1 1
2 0 1  
A transposta da matriz A = é a matriz AT = 2 5 .
1 5 3
0 3
   
3 5 2 3 1 5
   
A matriz 2 1 7 é simétrica, mas a matriz 2 1 7 já não é, uma vez que os elementos
5 7 9 5 7 9
(1, 2) e (2, 1) não são iguais.

Propriedades 5. A transposição de matrizes goza das seguintes propriedades:

1. (AT )T = A.

2. (A + B)T = AT + B T .

3. (AB)T = B T AT .

4. (αA)T = αAT , qualquer que seja o número α.

5. (Ak )T = (AT )k , para qualquer que seja o número natural k.

6. Se A é invertível então AT é invertível e

(AT )−1 = (A−1 )T

13
 Matrizes e Grafos

2.5 Sistemas de Equações Lineares

Um dos principais tópicos da Álgebra Linear é o estudo de equações lineares devido a sua im-
portância em Matemática Aplicada. Muitos problemas, por exemplo nas engenharias conduzem
à necessidade de resolver sistemas de equações lineares. Alguns sistemas por possuírem um
número elevado de equações e de tipos especiais a sua resolução insere-se no campo computa-
cional e na Análise Numérica.
Nesta secção iremos apresentar de forma sucinta os conceitos e resultados de maior ênfase
usando a linguagem matricial.

Definição 2.5.1. Uma equação linear nas incógnitas x1 , · · · , xn é uma equação do tipo

a1 x1 + · · · + an xn = d,

onde a1 , · · · , an e d são números. A d costuma chamar-se segundo membro ou termo indepen-

dente da equação.
Um sistema de equações lineares é uma colecção finita ordenada de equações lineares(todas
nas mesmas incógnitas) consideradas em conjunto.

Um sistema genérico com m equações e n incógnitas



 a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1




a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn = b2
 ..

 .



a x + a x + a x + · · · + a x = b
m1 1 m2 2 m3 3 mn n m

apresenta-se abreviadamente na forma AX = B, onde

     
a11 a12 ··· a1−n a1n x1 b1
     
 a21 a22 ··· a2n−1 a2n   x2   b2 
A=
 .. .. ..  
..  , X =  ..  , e B = 
 
 .. .
 . . . .  .  . 
am1 am2 ··· amn−1 amn xn bm

A é a matriz do sistema, ou dos coeficientes, X é a matriz coluna das incógnitas e B é a

matriz coluna dos segundos membros ou, abreviadamente, o segundo membro do sistema.

Chamamos matriz ampliada do sistema à matriz de Mm×(n+1) (R) cuja coluna i, para i =
1, · · · , n, é igual à coluna i da matriz A e cuja coluna n + 1 é igual à coluna (única) de B. Tal
matriz é denotada por

[A|B].

O grande objetivo perante um sistema de equações lineares é resolvê-lo, isto é, achar as

soluções.

Definição 2.5.2. Uma solução de um sistema de equações lineares nas incógnitas x1 , · · · , xn é

uma matriz-coluna n × 1

14
Matrizes e Grafos

 
α1
 
 α2 
 . 
 . 
 . 
αn

de números tais que as substituições xi = αi , i = 1, · · · , n, transformam todas as equações do

sistema em identidades verdadeiras. Resolver um sistema de equações é determinar todas as
suas soluções ou provar que não existe nenhuma.
Um sistema de equações lineares que tenha pelo menos uma solução diz-se possível: se só tiver
uma solução, é possível determinado; se tiver mais do que uma, é possível indeterminado.
Um sistema de equações lineares que não tenha nenhuma solução diz-se impossível.

Exemplo 2.5.1. Consideremos o sistema de equações lineares


2x + 5x = 3
1 2
.
4x + 9x = 7
1 2
[ ] [ ] [ ]
2 5 x1 3
A matriz dos coeficientes é A = , enquanto que X = eB= , são, respecti-
4 9 x2 7
vamente as[ matrizes-coluna
] das incógnitas e dos termos independentes. A matriz ampliada do
2 5 3
sistema é .
4 9 7
[ ]
4
Este sistema é possível e determinado, sendo a sua solução.
−1

Definição 2.5.3. Um sistema em que os segundos membros das equações são todos iguais a 0
diz-se homogéneo.

Note-se que um sistema homogéneo é sempre possível: possui sempre, pelo menos, a solução
 
0
 
0
 .  , chamada solução trivial.
.
.
0

Definição 2.5.4. Dois sistemas com o mesmo número de equações e de incógnitas dizem-se
equivalentes se tiverem exatamente as mesmas soluções.

Teorema 2.5.1. Seja AX = B um sistema de equações lineares com Am×n . Seja E uma matriz
m × m invertível. Então o sistema EAX = EB é equivalente ao sistema AX = B.

Demonstração: Claramente, qualquer solução do sistema AX = B é também solução do sis-

tema EAX = EB. Reciprocamente, seja U uma solução do sistema EAX = EB, isto é, tem-se
EAU = EB. Multiplicando à esquerda ambos os membros desta igualdade por E −1 , obtemos
AU = B, isto é, U é solução do sistema AX = B.
□

15
 Matrizes e Grafos

2.5.1 Matrizes elementares

As matrizes elementares aparecem no estudo dos sistemas de equações lineares. Para definir-
mos esta classe de matrizes é útil conhecer certo tipo de operações que se podem efetuar sobre
as linhas de uma matriz, ditas operações elementares:

1. Troca entre sí de duas linhas da matriz;

2. Multiplicação de uma linha por um número diferente de zero.

3. Substituição de uma linha da matriz pela sua soma com um múltiplo de outra.

Definição 2.5.5. Chama-se matriz elementar de ordem n a toda matriz que se obtém de In
por aplicação de uma operação elementar às suas linhas.

Exemplo 2.5.2. Consideremos o sistema


x + 3y = 21
.
2x + 4y = 5

Utilizando operações elementares transformemos a matriz dos coeficientes na matriz identi-

dade:
[ ] [ ] −−−→ [ ] [ ]
1 3 2 −−−−−−−→ 1 3 2 1 1 3 2 −−−−−−−→ 1 0 7
l2 + (−2)l1 − l2 → l1 + (−3)l2 2
.
2 4 5 0 −2 1 2 0 1 − 12 0 1 − 21

x = 7
2
Donde se conclui que o sistema dado é equivalente ao sistema , pelo que é um
y = − 1
2
sistema possível e determinado.

Antes de terminar esta secção podemos concluir que através de operações elementares é pos-
sível transformar um sistema dado num sistema muito fácil de resolver. Este novo sistema,
digamos U X = C, equivalente ao sistema original e cuja matriz U , que é ainda m × n, tem uma
forma especial, a que se costuma chamar matriz escada.

Definição 2.5.6. Uma matriz diz-se uma matriz em escada se satisfizer as seguintes condições:

• Se o primeiro elemento não nulo numa linha está na coluna j, então a linha seguinte
começa com pelo menos j elementos nulos.

• Se houver linhas totalmente constituídas por zeros, elas aparecem depois das outras.

O primeiro elemento não nulo de cada linha de uma matriz em escada chama-se pivot da matriz.

Exemplo 2.5.3.

16
Matrizes e Grafos

1. Representando por • os pivós da matriz e por ∗ as entradas da matriz que podem tomar
qualquer valor, estão em forma de escada, por exemplo as matrizes da forma

     
0 • ∗ ∗ • ∗ ∗ • [ ]
     
0 0 0 • , 0 • ∗ , 0 , ou • ∗ ∗ ∗
0 0 0 0 0 0 • 0

2. As matrizes
 
  0 0 0 0   
1 0 −1   0 0 0 7 1 3 −1 2
  0 −1 0
0 3 5  ,
3 ,
0 −1 3
 
0  e 0 0 0 0

0 −4
 0 6 
0 3 0 0 0 6 −4 0 0 2 −2
0 0 0 0
não estão em forma de escada.

Definição 2.5.7. A característica de A, abreviadamente car(A), é o número de pivots que

aparecem quando se aplica a A o método de eliminação. Equivalentemente, car(A) é o número
de linhas não nulas da matriz U produzida pelo algorítmo de eliminação aplicado a A. (Se A for
uma matriz nula, tem-se car(A) = 0).
Uma matriz quadrada An×n diz-se não-singular se tiver característica n. Se car(A) < n, a
matriz A diz-se singular.

 
1 1 2
 
Exemplo 2.5.4. Considere a matriz A = 1 3 3  . Recorrendo a operações elementares,
2 8 12
obtemos:
     
1 1 2 1 1 2 1 1 2
  −−−−−−−−−−−−−−−−−→   −−−−−−−→  
1 3 3  l2 + (−1)l1 ; l3 + (−2)l1 0 2 1 l3 + (−3)l2 0 2 1
2 8 12 0 6 8 0 0 5
 
1 1 2
 
A matriz resultante do processo de transformação anterior é a matriz escada U = 0 2 1,
0 0 5
pelo que car(A) = 3.

2.6 Determinante de uma Matriz Quadrada

Como vimos anteriormente, uma matriz quadrada é invertível quando a característica dessa
matriz é igual à ordem dessa matriz.
Nesta secção iremos ver que podemos associar a cada matriz A ∈ Mn×n (R) um elemento de R
que, tal como a característica, também nos vai permitir decidir sobre a invertibilidade de A.
Mais especificamente, iremos ver que, para qualquer n ∈ N, podemos associar a cada matriz
A ∈ Mn×n (R) um elemento R, a que chamaremos ”determinante” de A e que A é invertível se,
e só se, esse elemento for não nulo.

Nota 2.6.1. Seja A ∈ Mn×n (R), com n ≥ 2. Dado i, j ∈ {1, · · · , n}, representamos por

A(i|j)

17
 Matrizes e Grafos

a matriz que se obtém de A suprimindo a linha i e a coluna j. Assim

A(i|j) ∈ Mn−1×n−1 (R)

Definição 2.6.1. Seja A ∈ Mn×n (R). Chamamos determinante de A, e representamos por

det A ou |A|, ao elemento de R definido, por recorrência, da seguinte forma:

Se n = 1, então det A = a11 .

Se n > 1, então

det A = a11 (−1)1+1 det A(1|1) + · · · + a1n (−1)1+n det A(1|n)

∑n
= a1k (−1)1+k det A(1|k).
k=1

Notemos que, pela definição anterior, para

[ ]
a11 a12
A= ∈ M2×2 (R)
a21 a22

resulta que

det A = a11 (−1)1+1 det A(1|1) + a12 (−1)1+2 det A(1|2)

= a11 det[A22 ] − a12 det[A21 ]
= a11 a22 − a12 a21

Utilizando a definição, o determinante de uma matriz A, de ordem n = 3,

 
a11 a12 a13
 
A = a21 a22 a23 
a31 a32 a33

tem-se

det A = a11 (−1)1+1 det A(1|1) + a12 (−1)1+2 det A(1|2) + a13 (−1)1+3 det A(1|3)
[ ] [ ] [ ]
a22 a23 a21 a23 a21 a22
= a11 det − a12 det + a31 det
a32 a33 a31 a33 a31 a32
= a11 (a22 a33 − a23 a32 ) − a12 (a21 a33 − a23 a31 ) + a13 (a21 a32 − a22 a31 )
= a11 a22 a33 − a11 a23 a32 − a12 a21 a33 + a12 a23 a31 + a13 a21 a32 − a13 a22 a31
= (a11 a22 a33 + a12 a23 a31 + a13 a21 a32 ) − (a11 a23 a32 + a12 a21 a33 + a13 a22 a31 ).

Assim, para n = 3, a expressão de det A tem 6 parcelas que podem ser escritas como uma
diferença em que o aditivo tem 3 parcelas e o subtrativo outras 3 parcelas.
No caso geral, de A ∈ Mn×n (R) a expressão de detA tem n! parcelas, como se pode demonstrar
usando o método de indução em n.

A partir do conceito que apresentamos na definição que se segue, é possível calcular de forma
mais expedita o determinante de uma matriz quadrada de qualquer ordem.

18
Matrizes e Grafos

Definição 2.6.2. Seja A ∈ Mn×n (R), com n ≥ 2. Designamos por complemento algébrico da
posição (i, j) de A, e representamos por âij , o escalar

âij = (−1)i+j detA(i|j),

em que A(i|j) é a matriz que se obtém de A suprimindo a linha i e a coluna j.

Notemos que âij não depende do elemento da posição (i, j) de A pois esse elemento não figura
na matriz A(i|j).

De acordo com a definição 2.6.1, se A ∈ Mn×n (R) e n ≥ 2, então o determinante de A é igual

à soma dos produtos dos elementos da linha 1 pelos complementares algébricos das respetivas
posições, isto é,

det A = a11 â11 + · · · + a1n â1n .

 
1 0 3
 
Exemplo 2.6.1. Seja A = −1 2 4 ∈ M3×3 (R). Então, tendo em conta que
3 1 2
[ ]
1+1 2 4
â11 = (−1) =0
1 2
[ ]
1+2 −1 4
â12 = (−1) = 14
3 2
[ ]
−1 2
â13 = (−1)1+3 = −7,
3 1

e a11 = 1, a12 = 0 e a13 = 3, concluímos que det A = 1.0 + 0.14 + 3.(−7) = −21.

O resultado seguinte, cuja demonstração deixamos que o leitor consulte a referência [?] pági-
nas 162 e 163, afirma que se procedermos de forma análoga para uma qualquer linha ou uma
qualquer coluna de A, obtemos ainda o determinante de A.

Teorema 2.6.1. Seja A ∈ Mn×n (R),com n ≥ 2. O determinante de A é igual à soma dos produ-
tos que se obtêm multiplicando os elementos de uma qualquer linha de A pelos complementos
algébricos das respetivas posições, isto é,

det A = ai1 âi1 + · · · + ain âin para qualquer linha i de A. (2.1)

O mesmo resultado é válido se substituirmos ”linha” por ”coluna”, isto é,

det A = a1j â1j + · · · + anj ânj para qualquer coluna j de A. (2.2)

Este resultado é conhecido como Teorema de Laplace.

19
 Matrizes e Grafos

À expressão (2.1) chamamos o desenvolvimento do determinante de A segundo a linha i ou

dizemos que é a expressão resultante da aplicação do Teorema de Laplace à linha i de A.
Analogamente, dizemos que (2.2) é a expressão resultante da aplicação do Teorema de Laplace
à coluna j de A.

Propriedades 6. Como consequência imediata do Teorema de Laplace tem-se:

1. Se A ∈ Mn×n (R), tem uma linha nula, então

det A = 0.

2. Seja A ∈ Mn×n (R), com n ≥ 2. Se A tem a linha i igual à linha j, com i ̸= j, então

det A = 0.

3. Seja A ∈ Mn×n (R). Tem-se

det A = det AT

isto é, uma matriz e a sua transposta têm o mesmo determinante.

4. Se A ∈ Mn×n (R) é uma matriz triangular superior(superior ou inferior), então o deter-

minante de A é igual ao produto dos elementos da diagonal principal de A.

5. Seja A ∈ Mn×n (R). Se os elementos da linha i de A são da forma Aik = Bik + Cik , com
k = 1, · · · , n, então

     
a11 ··· a1n a11 ··· a1n a11 ··· a1n
     
 ···   ···   ··· 
     
det 
bi1 + ci1 ··· 
bin + cin  = det  bi1
 ··· 
bin  + det  ci1
 ··· cin 
.
     
 ···   ···   ··· 
an1 ··· ann an1 ··· ann an1 ··· ann

2.7 Transformações Lineares

Nesta secção abordaremos muito brevemente os conceitos e alguns resultados fundamentais das
Transformações Lineares, funções entre dois espaços vetoriais definidos sobre o mesmo corpo
que respeitam as operações de adição de vetores e multiplicação de escalares por vetores con-
sideradas nos dois espaços. Muitos resultados já apresentados são válidos para as transformações
lineares tal é o caso do conceito de combinação linear já apresentado e demonstrado no teorema
2.2.1. Estes conceitos serão utilizados principalmente no capítulo 4 deste trabalho.

Definição 2.7.1. Seja V um conjunto não vazio e seja K um corpo. Diz-se que V é um es-
paço vetorial sobre K se estiverem definidas duas operações, uma adição de elementos de
V , denotada pelo símbolo +,e uma multiplicação de elementos de K por elementos de V ,
denotada pelo símbolo ., ou por simples justaposição (operações em ambos os casos produzindo
elementos de V ), que satisfazem as seguintes propriedades:

1. ∀u,v,w∈V (u + v) + w = u + (v + w);

20
Matrizes e Grafos

2. ∀u,v∈V u + v = v + u;

3. ∃z∈V ∀v∈V v + z = v;

4. ∀v∈V ∃v′ ∈V v + v ′ = z;

5. ∀u,v∈V ∀α∈K α(u + v) = αu + αv;

6. ∀u∈V ∀αβ∈K (α + β)v = αv + βv;

7. ∀u∈V ∀αβ∈K (αβ)v = α(βv);

8. ∀α∈V 1K v = v.

Se K = R, diz-se que se tem um espaço vetorial real. Se K = C diz-se que se tem um espaço
vetorial complexo.
Aos elementos de um espaço vetorial V chamamos genericamente vetores, e aos elementos do
corpo K escalares.

Exemplo 2.7.1. O conjunto dos números reais, com soma e produto usuais é um espaço vetorial
sobre R.

Exemplo 2.7.2. O conjunto das matrizes quadradas de ordem 2, com entradas reais, denotado
por M2 ,
{( ) }
a b
M2 = : a,b,c, d ∈ R ,
c d

com adição de matrizes e multiplicação por escalar, forma um espaço vetorial.

Definição 2.7.2. Seja V um espaço vetorial sobre um corpo K. Um subconjunto W de V diz-se

um subspaço de V se for ele próprio um subspaço vetorial para as operações nele naturalmente
definidas (por ser um subconjunto de V ).

Teorema 2.7.1. Seja V um espaço vetorial sobre um corpo K e W um suconjunto de V . W é

um subspaço de V se e só se satisfizer as seguintes condições:

1. W ̸= ∅;

2. W é fechado para a adição, isto é, u, v ∈ W ⇒ u + v ∈ W ;

3. W é fechado para a multiplicação por elementos de K, isto é, α ∈ K, v ∈ W ⇒ αv ∈ W .

Demonstração: A condição necessária é evidente, dada a definição de espaço vetorial. Ve-

jamos a condição suficiente. As propriedades 1, 2, 5, 6, 7 e 8 da definição de espaço vetorial
são satisfeitas em W porque o são em V , e W está contido em V . Em seguida, o zero de V
pertence necessariamente a W , porque sendo v um vetor qualquer de W (existe pelo menos um
porque W ̸= ∅), a terceira condição do teorema obriga a que 0K v = 0V ∈ W . Finalmente, sendo
v ∈ W , e sabemos que −v = (−1)v e, portanto, pelo facto de ser fechado para a multiplicação
por elementos de K, −v ∈ W .
□

21
 Matrizes e Grafos

Exemplo 2.7.3. Se V =M2 , {( ) }

α β
V = :α e β∈R
0 0

então W é um subespaço de V .

Definição 2.7.3. Seja V um espaço vetorial sobre K e sejam ,v1 , v2 · · · vn elementos de V . Dize-
mos que v ∈ V é combinação linear dos vectores v1 , · · · , vn se existirem escalares α1 , · · · , αn ∈
K tais que
v = α1 v1 + α2 v2 + · · · + αn vn

Aos escalares α1 , · · · , αn , chamamos os coeficientes da combinação linear e a (α1 , · · · , αn ) a

sequência dos coeficientes da combinação linear.

Definição 2.7.4. Sejam v1 , v2 · · · vn , elementos de um espaço vetorial V . chamamos Subspaço

(de V)gerado pela sequência (v1 , v2 · · · vn ) ou pelos vectores v1 , v2 · · · vn ao conjunto de todas
as combinações lineares dos vectores v1 , v2 · · · vn . Tal subspaço é frequentemente denotado por
⟨v1 , v2 · · · vn ⟩, isto é,

⟨v1 , v2 · · · vn ⟩ = {α1 v1 + α2 v2 + · · · + αn vn , α1 , α2 , · · · , αn ∈ K}.

Se W = ⟨v1 , v2 · · · vn ⟩ dizemos, ainda, que v1 , v2 · · · vn geram W , que v1 , v2 · · · vn , são geradores

de W ou que a sequência (v1 , v2 · · · vn ) é geradora de W .

[ ] [ ]
1 0 0 1
No exemplo anterior v1 = e v2 = geram o subespaço W .
0 0 0 0
Portanto, {( ) }
α β
W = ⟨v1 , v2 ⟩ = :α eβ∈R .
0 0

Definição 2.7.5. Seja V um espaço vetorial . Seja v1 , · · · , vn ∈ V (com n ≥ 2) .Os vetores

v1 , · · · , vn dizem-se linearmente independente (LI) se nenhum deles for igual a uma combinação
linear dos outros n − 1. Um vetor v1 é linearmente independente se v1 ̸= 0. Se v1 , · · · , vn não
forem linearmente independentes, dizem-se linearmente dependentes(LD).

Exemplo 2.7.4. As matrizes de M2×2 (K)

[ ] [ ] [ ]
1 0 0 1 0 0
, ,
0 0 0 0 0 1

são linearmente independentes. Para o mostrar, escreva-se a matriz nula como combinação
linear destas matrizes, com coeficientes a determinar:
[ ] [ ] [ ] [ ]
1 0 0 1 0 0 0 0
α1 + α2 + α3 =
0 0 0 0 0 1 0 0

Então tem-se [ ] [ ]
α1 α2 0 0
= ,
0 α3 0 0

o que implica α1 = α2 = α3 = 0.

22
Matrizes e Grafos

Definição 2.7.6. Seja V um espaço vetorial e (v1 , · · · , vn ), uma sequência de vetores de V .

Dizemos que (v1 , · · · , vn ) é uma base de V se é uma sequência geradora de V e é linearmente
independente.
Convencionamos que se V = 0V então a sequência vazia é base de V .

Definição 2.7.7. Seja V um espaço vetorial que admite uma base com n elementos, com n ∈ N.
Dizemos então que V tem dimensão n e escrevemos dim V = n.

Exemplo 2.7.5. Consideremos V = {(x, y, z) ∈ R3 : x + y − z = 0}. Tendo em conta a

definição anterior, se conhecermos uma base, então temos também a dimensão de V , por isso
concentremo-nos em encontrar uma base para V . Precisamos de uma sequência de geradores
que sejam LI. Ora, z = x + y e, portanto, V pode ser definido como

V = {(x, y, x + y) ∈ R3 ∀x,y∈R }.

Por outro lado,      

x 1 0
     
 y  = x  
0 + y 1 ,
x+y 1 1

ou seja    
⟨ 1 0 ⟩
   
V = 0 , 1
1 1

Mas, (1, 0, ) e (0, 1, 1) são linearmente independentes. Na verdade, temos

         
1 0 0 1 0 |0 1 0 |0
         
α1 0 + α2 1 = 0 → 0 1 |0 → 0 1 |0 .
1 1 0 1 0 |0 0 0 |0
   

 1 0 
   
Logo uma base de V é 0 , 1 , e V tem dimensão 2.

 

1 1

Definição 2.7.8. Sejam V e W dois espaços vetoriais sobre o mesmo corpo K. Uma função
T : V → W , que satisfazendo as condições:

1. T (u + v) = T (u) + T (v),

2. T (αv) = αT (v),

para quaisquer u, v ∈ V e α ∈ K, diz-se transformação linear.

Para ilustrarmos uma transformação linear basta pensarmos numa equação matricial Av = B
em que a matriz A multiplicada com o vetor v produz um novo vetor B. Assim, dizemos que a
multiplicação por A transforma v em B.

23
 Matrizes e Grafos

Por exemplo, seja A uma matriz m × n. A transformação T : Rn → Rm , definida por T (v) = Av

 
x1
 
 x2 
para cada v =  
 ..  ∈ R , é linear.
n
.
xn

Propriedades 7. Sejam V e W espaços vetoriais sobre o corpo K e T : V → W uma transfor-

mação linear.Então tem-se:

1. T (0V ) = 0W .

2. T (−v) = −T (v), para qualquer v ∈ V .

3. T (u − v) = T (u) − T (v), para quaisquer u, v ∈ V .

4. T (α1 v1 + · · · + αn vn ) = α1 T (v1 ) + · · · + αn T (vn ), para qualquer natural n e quaisquer

α1 , · · · , αn ∈ K, v1 , · · · , vn ∈ V .

As transformações lineares estão associadas a dois importantes subspaços que a seguir passamos
a definir.

Definição 2.7.9. (Núcleo e imagem )Sendo T : V → W uma transformação linear, o núcleo de

T é o conjunto ker(T ) = {v ∈ V : T (v) = 0W }. A imagem de T é o conjunto im(T ) = {T (v) :
v ∈ V }.

Proposição 2.7.1. Seja T : V → W uma transformação linear. Então ker(T ) é um subespaço de

V e im(T ) é um subespaço de W .

Demonstração: Mostraremos que ker(T ) é um subspaço de V . Note-se, em primeiro lugar, que

0V ∈ ker(T ), uma vez que T (0V ) = 0W . Dados u e v elementos arbitrários de ker(T )( isto é
T (u) = T (v) = 0W ) e um escalar α, tem-se, pela linearidade de T ,

T (u + v) = T (u) + T (v) = 0W + 0W = 0W e T (αu) = αT (u) = α0W = 0W .

Assim, u + v e αu pertencem a ker(T ), o que termina a prova de que ker(T ) é um subspaço de

V.
Consideremos agora im(T ). Claramente este conjunto é não vazio, pois 0W = T (0V ) ∈ im(T ).
Dados w, z ∈ im(T ), existem x, y ∈ V tais que w = T (x) e z = T (y). Então, pela linearidade de
T,

w + z = T (x) + T (y) = T (x + y) ∈ im(T ) e αT (x) = T (αx) ∈ im(T ),

uma vez que, pelo facto de V ser um espaço vetorial, x + y e αx ∈ V . Concluímos assim que
im(T ) é um subspaço de W . □

No caso de im(T ) ter dimensão finita, chamamos a essa dimensão a característica da transfor-
mação linear T . Usamos a notação car(T ) para este número, ou seja, car(T ) = dim(T ).

Existe uma relação muito simples entre as dimensões de im(T ) e ker(T ), cujo resultado apre-
sentamos a seguir.

24
Matrizes e Grafos

Teorema 2.7.2. Sejam V e W espaços vetorial, com V de dimensão finita, e seja T : V → W

uma transformação linear. Então tem-se

car(T ) = dim V − dim ker(T ).

Demonstração: Seja dim V = n. Suponhamos que ker(T ) ̸= {0} e seja {v1 , · · · , vk } uma base de

ker(T ). (Se ker(T ) = {0}, o raciocínio decorre de modo análogo, tomando k = 0 no resto da
demonstração). Acrescentemos a estes k vetores n − k vetores vk+1 , · · · , vn de forma a obter
uma base de V .
Vamos ver que os n − k vetores T (vk+1 ), · · · , T (vn ) constituem uma base de im(T ). Isso provará
o teorema.
Primeiro mostremos que T (vk+1 , · · · , T (vn ) são linearmente independentes. Se

α1 T (vk+1 + · · · + αn−k T (vn ) = 0,

vem

T (α1 vk+1 + · · · + αn−k vn ) = 0,

e tem-se

α1 vk+1 + · · · , αn−k vn ∈ ker(T )

Então, como {v1 , · · · , vk } é uma base de ker(T ), tem-se

α1 vk+1 + · · · , αn−k vn = β1 v1 + · · · + βk vk ,

para certos escalares β1 , · · · , βk , o que é mesmo que

β1 v1 + · · · + βk vk − α1 vk+1 − · · · − αn − kvn = 0.

Agora mostremos que T (vk+1 , · · · , T (vn ) geram im(T ). Seja w um vetor qualquer de im(T ).
Então, w = T (v) para algum v ∈ V e, como v1 , · · · , vn constituem uma base de V , tem-se

v = γv1 + · · · + γn vn ,

para certos escalares γ1 , · · · , γn . Então, como v1 , · · · , vk ∈ ker(T ), tem-se

T (v) = γk+1 T (vk+1 + · · · + γn T (vn )

e w é uma combinação linear de T (vk+1 , · · · , T (vn ).

□

2.7.1 Subspaços Fundamentais de uma matriz

Definição 2.7.10. O espaço nulo de uma matriz Am×n , escrita como N ulA, é o conjunto de
todas soluções da equação homogénea AX = 0. Denotamos por

N ulA = {X : X ∈ Rn |AX = 0}

25
 Matrizes e Grafos

[ ]
1 −3 −2 [ ]T
Exemplo 2.7.6. Sejam as matrizes A = eX= 5 3 −2 . Como
−5 9 1
 
[ ] 5 [ ] [ ]
1 −3 −2   5−9+4 0
AX =  3 = = ,
−5 9 1 −25 + 27 − 2 0
−2

concluímos que X está no espaço nulo de A.

Teorema 2.7.3. O espaço nulo de uma matriz A m×n é um subspaço de Rn . Equivalentemente,

o conjunto de todas soluções do sistema AX = 0 de m equações lineares homogéneas em n
incógnitas é um subspaço de Rn .

Demonstração: Certamente N ulA é um subspaço de Rn porque A possui n colunas. Devemos

provar que N ulA satisfaz as três propriedades de um subspaço. É claro que zero está em N ulA.
Seguidamente sejam u e v dois vetores em N ulA. Assim, Au = 0 e Av = 0.
Para provar que u + v está em N ulA, devemos mostrar que A(u + v) = 0. Usando a propriedade
da multiplicação de matrizes, vem

A(u + v) = Au + Av = 0 + 0 = 0.

Portanto, u + v está em N ulA e N ulA é fechado para a adição de vetores. Finalmente, se α é

um escalar qualquer, vem

A(αu) = α(Au) = α(0) = 0,

o que mostra que αu está no espaço nulo de A. Portanto N ulA é um subspaço de Rn . □

Definição 2.7.11. O espaço coluna de uma matriz A m × n, denotado por ColA, é o conjunto
de todas as combinações lineares das colunas de A.

ColA = {b : b = AX; X ∈ Rn }

Exemplo 2.7.7. Consideremos o conjunto

  

 6a − b 

 
W =  a + b  : a, b ∈ R .

 

−7a

Podemos(escrever W em que cada um dos seus elementos é combinação linear de outros ele-
[ ]T [ ]T )
mentos neste caso, de [ccc]6 1 −7 e de [ccc] − 1 1 0 :

         
 6 −1  ⟨ 6 −1 ⟩
 
       
W = a  1  + b  1  : a, b ∈ R =  1  ,  1  .

 

−7 0 −7 0

O conjunto W também pode ser escrito usando os vetores do conjunto gerador como colunas
de uma matriz A:

26
Matrizes e Grafos

 
6 −1
 
A= 1 1 .
−7 0

Portanto, o espaço coluna de uma matriz A m × n é um subspaço de Rm .

O espaço nulo e o espaço coluna estão relacionados. Para ilustrarmos melhor esta ideia, con-
sideremos uma matriz genérica

 
a11 a12 a13 a14
 
A = a21 a22 a23 a24  .
a31 a32 a33 a34

Um vetor X tal que AX está definido, deve ter quatro entradas, assim o espaço nulo é um
subspaço de R4 . Por outro lado, cada coluna de A possui três entradas, assim ColA é um
subspaço de R3 .

Se A é uma matriz m × n então é possível definir ainda outros dois espaços vetoriais associados
com matrizes:

• Espaço nulo de AT ou espaço nulo esquerdo de A: é um subspaço de Rn .

• Espaço coluna de AT ou espaço linha de A: espaço de Rn gerado pelos vetores linha de

A.

As matrizes fundamentais estão relacionadas com o teorema do Núcleo e imagem de uma trans-
formação linear. Vejamos um exemplo que nos levará a esta conclusão.

Seja T : V → W uma transformação linear. Consideremos a matriz

 
1 2 3 5
 
A = 0 1 2 −1 ,
1 3 5 4

que representa uma transformação linear T : R4 → R3 . Determinemos a característica de A:

     
1 2 3 5 1 2 3 5 1 2 3 5
  −−−−−−−→   −−−−−−−→  
0 1 2 −1 l3 + (−1)l1 0 1 2 −1 l3 + (−1)l2 0 1 2 −1
1 3 5 4 0 1 2 −1 0 0 0 0

Portanto, car(A) = 2.
Determinemos agora o Núcleo de T. Considerando a matriz ampliada do sistema
 
  x1  
1 2 3 5   0
 x2 
  
0 1 2 −1   = 0
x3 
1 3 5 4 0
x4

27
 Matrizes e Grafos

e reduzindo-a à sua forma em escada obtemos

 
1 2 3 5 0
 
 0 1 2 −1 0 
0 0 0 0 0

donde,
{ { {
x1 + 2x2 + 3x3 + 5x4 = 0 x1 + 2x2 + 3x3 + 5x2 + 10x3 = 0 x1 = −7x2 − 13x3
↔ ↔
x2 + 2x3 − x4 = 0 x4 = x2 + x2 + 2x3 x4 = x2 + x2 + 2x3

Portanto, os elementos do Núcleo são da forma

     
−7x2 − 13x3 −7 −13
     
 x2     
  = x 2  1  + v3  0  .
     
 x3  0  1 
x2 + 2x3 1 2

Logo, a dimensão de N (A) é 2.

A Imagem de T é constituído por vetores da forma

 
  x1        
1 2 3 5   1 2 3 5
 x2 
        
0 1 2 −1   = x2 0 + x2 1 + x3 2 + x4 −1
x3 
1 3 5 4 1 3 5 4
x4

Mas, como a car(A) = 2, das colunas consideradas só duas são linearmente independentes.
Portanto a característica da Imagem é 2.
Do exemplo apresentado, concluímos que

dimN (A) + dimIm(A) = dimV,

ou seja,

N ul(A) + car(A) = Número de colunas.

2.7.2 Matriz de uma transformação linear

Usando matrizes podemos representar as transformações lineares entre espaços de dimensão

finita com dim V = n ≥ 1 e dim W = m ≥ 1.

A transformação T : Kn → Km definida por T (x) = Ax é uma transformação linear.

Assim, se conhecermos os valores que tomam os vetores de uma base de um determinado espaço
vetorial de dimensão finita a transformação linear fica conhecida.

Definição 2.7.12. Seja T : V → V ′ uma transformação linear. Sejam B = (e1 , e2 , · · · , en ) uma

base de V e B ′ = (e′1 , e′2 , · · · , e′m ) uma base de V ′ .
Designamos por matriz de T em relação às bases B e B ′ (por essa ordem) e representamos por

28
Matrizes e Grafos

 
a11 a12 ··· a1n
 
 a21 a22 ··· a2n 
M (T : B, B ) = 
′
 .. .. .. ,

 . . . 
am1 am2 ··· amn

onde



 T (e1 ) = a11 e′1 + a12 e′2 + · · · + am1 e′m


 T (e2 ) = a12 e′1 + a22 e′2 + · · · + am2 e′m
 ..

 .

 ′ ′ ′
T (en ) = a1n e1 + a2n e2 + · · · + amn em

Exemplo 2.7.8. A transformação T : R2 → R3 tal que T ((x, y)) = (2x, x − y, 3y) é linear.
Então vamos determinar a matriz de T em relação às bases B = (1, 0), (1, 1) de R2 e B ′ =
(1, 0, 1), (1, 1, 0), (0, 0, 1) de R3 . Sabemos de antemão que dim V = 2 e dim V ′ = 3. A matriz T
em relação as bases será da forma
 
a11 a12
′  
M (T : B, B ) = a21 a22  .
a31 a32

Mais,

T (e1 ) = T (1, 0) = (2, 1, 0) = a11 (1, 0, 1) + a21 (1, 1, 0) + a31 (0, 0, 1) = (1, 0, 1) + (1, 1, 0) − (0, 0, 1)

T (e2 ) = T (1, 1) = (2, 0, 3) = a12 (1, 0, 1) + a22 (1, 1, 0) + a32 (0, 0, 1) = 2(1, 0, 1) + 0(1, 1, 0) + (0, 0, 1).

Consequentemente,
 
1 2
 
M (T : B, B ′ ) =  1 0 .
−1 1

Observemos que, se T é uma transformação linear e A é a matriz T em relação a certas bases,

então dim im(T ) = car(A).

29
 Matrizes e Grafos

30
Matrizes e Grafos

Capítulo 3

Algumas Aplicações de Matrizes

Neste capítulo apresentamos algumas aplicações da Teoria de Matrizes que realçam a utilidade
desta nas diversas áreas, nomeadamente na Economia, Química, Criptografia e outras. Os exem-
plos que a seguir se apresentam têm como pré-requisitos os conceitos já estudados no capítulo 2
e ilustram, embora de forma rudimentar, a utilidade do cálculo matricial no estudo de conceitos
de outras áreas do saber.

3.1 Aplicação à Economia: Modelo Fechado [de Input-Output] de

Leontief

Este exemplo foi retirado de [2] (páginas 411-412).

O modelo Fechado [de Input-Output] de Leontief, usa a teoria de matrizes para calcular certos
parâmetros que descrevem as inter-relações entre as indústrias, tais como os preços e os níveis
de produção, para a satisfação de um objetivo económico desejado.Os sistemas de equações
lineares e as matrizes, são os pré-requisitos necessários para esta aplicação.

Exemplo 3.1.1. Três proprietários de casas, um Pedreiro, um Eletricista e um Hidráulico, pre-

tendem fazer concertos em suas três casas. Eles concordam trabalhar um total de 10 dias cada
de acordo com a seguinte tabela:

T1 T2 T3
D1 2 1 6
D2 4 5 6
D3 4 4 3

Tabela 3.1: Distribuição dos concertos por casas.

Donde,

T1 é o trabalho executado pelo Pedreiro;

T2 é o trabalho executado pelo Eletricista
T3 é o trabalho executado pelo Hidráulico
D1 são os dias de trabalho na casa do Pedreiro;
D2 são os dias de trabalho na casa do Eletricista;
D3 são os dias de trabalho do Hidráulico.

Para efeitos de impostos, eles devem declarar e pagar um ao outro um salário diário razoável,
mesmo para o trabalho que cada um faz em sua própria casa. Seus salários diários normais
são cerca de 100 Euros, mas eles concordam em ajustar seus respetivos salários diários de tal

31
 Matrizes e Grafos

modo que saiam empatados, ou seja, de tal modo que o total pago por cada um é igual ao total
recebido. Nós podemos colocar

p1 =salário diário do Pedreiro;

P2 =salário diário do Eletricista;
p3 =salário diário do Hidráulico.

Para satisfazer a condição de equilíbrio de que saiam empatados, nós exigimos que
total dos gastos=total do recebido
para cada um dos proprietários pelo período de dez dias. por exemplo, o pedreiro paga um
total de 2p1 + p2 + 6p3 pelos concertos em sua própria casa e recebe um total de 10p1 pelos
concertos que faz nas três casas. Igualando estas expressões nos dá a primeira das três equações
seguintes:

2p1 + p2 + 6p3 = 10p1

4p1 + 5p2 + p3 = 10p2

4p1 + 4p2 + 3p3 = 10p3

Sendo que a segunda e a terceira equação correspondem ás equações de equilíbrio do Eletricista

e do Hidráulico. Dividindo estas equações por 10 e reescrevendo-as em formato matricial,
obtemos
    
0, 2 0, 1 0, 6 p1 p1
    
0, 4 0, 5 0, 1 p2  = p2 
0, 4 0, 4 0, 3 p3 p3

Subtraindo o lado esquerdo do direito, podemos reescrever a equação matricial como um sis-
tema homogêneo
     
0, 8 −0, 1 −0, 6 p1 0
     
−0, 4 0, 5 −0, 1 . p2  = 0
−0, 4 −0, 4 0, 7 p3 0

a solução do sistema homogêneo é

   
p1 31
   
p2  = s 32
p3 36

onde s é uma constante arbitrária. Esta constante é um fator de escala, que os proprietários
podem escolher de acordo com a sua conveniência. por exemplo, eles podem colocar s = 3,
de modo que os correspondentes salários diários, a saber 93 Euros, 96 Euros e 108 euros, são
aproximadamente 100 Euros.

32
Matrizes e Grafos

3.2 Aplicação à Química (Equilibrando equações)

Esta aplicação foi retirada de [11], Páginas 89-91.

Dizemos que uma reação química está equilibrada se aparece o mesmo número de átomos em
cada lado da seta para cada tipo de átomo na reação.

Exemplo 3.2.1. Dada a equação

CH4 + O2 −→ CO2 + H2 O,

a versão equilibrada desta equação química é

CH4 + 2O2 −→ CO2 + 2H2 O

com a qual queremos indicar que combinamos uma molécula de metano com duas de oxigénio
estável para produzir uma molécula de gás carbónico e duas moléculas de água. Poderíamos
perfeitamente multiplicar toda a equação por qualquer inteiro positivo. Por exemplo, multi-
plicando todos os termos por 2 obtém-se a equação química equilibrada

2CH4 + 4O2 −→ 2CO2 + 4H2 O.

Contudo, é convenção padrão utilizar os menores inteiros positivos que equilibram a equação.
A equação acima é suficientemente simples para ser equilibrada por tentativa e erro, mas
equações químicas mais complicadas requerem um método mais sistemático. Existem vários
métodos que podem ser usados, mas apresentamos aqui um que usa sistemas de equações
lineares. Examinemos a equação ora apresentada. Para equilibrar a equação precisamos de
encontrar inteiros x1 , x2 , x3 e x4 , tais que

x1 (CH4 ) + x2 (O2 ) −→ x3 (CO2 ) + x4 (H2 O).

Contudo, para cada um dos átomos da equação, o número de átomos á esquerda deve ser igual
ao número de átomos á direita. Expresso em formato tabular, temos

Lado esquerdo Lado direito

Carbono x1 = x3
Hidrogénio 4x1 = 2x4
Oxigénio 2x2 = 2x3 + x4
de onde obtemos o sistema linear homogéneo


 x − x3 = 0

 1
4x1 − 2x4 = 0 .



2x − 2x − x = 0
2 3 4

A matriz aumentada/ampliada deste sistema é

 
1 0 −1 0 0
 
4 0 0 −2 0
0 2 −2 −1 0

33
 Matrizes e Grafos

e a forma escalonada reduzida por linhas desta matriz é

 
1 0 0 − 12 0
 
0 1 0 −1 0 .
0 0 1 − 12 0

Pelo que a solução geral do sistema é

t t
x1 = , x2 = t, x3 = , x4 = t,
2 2

onde t é arbitrário. Os menores valores inteiros positivos para as incógnitas ocorrem quando
tomamos t = 2, de modo que podemos equilibrar a equação tomando x1 = 1, x2 = 2,x3 = 1,
x4 = 2. Tal vai ao encontro da conclusão acima, pois substituindo esses valores na equação
obtemos
CH4 + O2 −→ 2CO2 + 2H2 O.

Vejamos um outro exemplo:

Exemplo 3.2.2. Equilibre a equação química

HCL + N a3 P O4 =⇒ H3 P O4 + N aCL

[Ácido Clorídrico]+[Fosfato de Sódio]=⇒[Ácido Fosfórico]+[Cloreto de Sódio]

Solução:

Sejam x1 ,x2 , x3 e x4 , inteiros positivos que equilibram a equação

x1 (HCL) + x2 (N a3 P O4 ) =⇒ x3 (H3 P O4 ) + x4 (N aCL)

Igualando o número de átomos de cada tipo de ambos lados, resulta

1x1 =3x3 Hidrogénio (H)

1x1 =1x4 Cloro
3x2 =1x4 Sódio (Na)
1x2 =1x3 Fósforo (P)
4x2 =4x3 Oxigénio (O)

Do que obtemos o sistema linear homogêneo



 x1 − 3x3 = 0





 x − x4 = 0

 1
3x2 − x4 = 0





 x2 − x3 = 0



4x − 4x = 0
2 3

Do sistema linear homogêneo, obtemos a matriz aumentada do sistema

34
Matrizes e Grafos

 
1 0 −3 0 0
 
1 0 0 −1 0
 
0 3 0 −1 0
 
 
0 1 −1 0 0
0 4 −4 0 0

Deixamos a cargo do leitor mostrar que a forma escalonada reduzida da matriz aumentada
deste sistema é:
 
1 0 0 −1 0
 
0 1 0 − 13 0
 
0 0 1 − 13 0
 
 
0 0 0 0 0
0 0 0 0 0

da qual concluímos que a solução geral desse sistema é

x1 = t, x2 = 3t , x3 = 3t ,x4 = t

onde t é arbitrário. Para obter os menores valores inteiros positivos que equilibram a equação,
tomamos t = 3 e resulta x1 = 3,x2 = 1,x3 = 1 e x4 = 3. Substituindo esses valores na equação
dada temos

3HCL + N a3 P O4 =⇒ H3 P O4 + 3N aCL

3.3 O problema de Alocação de Tarefas

O problema de alocação de tarefas é um conjunto de procedimentos que visam encontrar uma
alocação ótima em uma dada matriz-custo. Na prática esta aplicação é utilizada nas empre-
sas para encontrar a melhor distribuição de trabalhadores, jogadores em posições no campo,
máquinas em locais de construção e em muitas outras áreas. Referenciamos para este tema a
consulta de [2].

Esta aplicação podia ser muito mais explorada, mas neste trabalho já não nos foi possível. Isto
porque este tema envolve conceitos da teoria de matrizes e da teoria de grafos, por exemplo:
grafo bipartido, matriz de incidência, árvore de suporte (conceitos introduzidos no capítulo 4
desta dissertação).

O Método de Húngaro

O método húngaro, criado pelos húngaros D. König e E. Everváry, é um procedimento de 5 passos

que a seguir passamos a descrever. Observamos aqui que em substituição dos traços horizontais
e verticais que o procedimento descreve, nós utilizamos cores.

• Subtraia a menor entrada de cada linha de todas as entradas da mesma linha. Dessa forma,
cada linha terá pelo menos uma entrada zero e todas as outras entradas são não negativas.

35
 Matrizes e Grafos

• Subtraia a menor entrada de cada coluna de todas as entradas de mesma coluna. Dessa
forma, cada coluna terá pelo menos uma entrada zero e todas as outras entradas são não
negativas.

• Risque um traço ao longo de linhas e colunas de tal modo que todas as entradas zero da
matriz-custo fiquem riscadas. Para isso, utilize um número mínimo de traços.

• Teste de otimização.

1. Se o número mínimo de traços necessários para cobrir os zeros é n, então uma alo-
cação ótima de zeros é possível e encerramos o procedimento.
2. Se o número mínimo de traços necessários para cobrir os zeros é menor do que n,
então ainda não é possível uma alocação ótima de zeros. Nesse caso, vá para o passo
seguinte.

• Determine a menor entrada não riscada por nenhum traço. Subtraia esta entrada de todas
as entradas não riscadas e depois a some a todas as entradas riscadas tanto horizontais
quanto verticalmente. Retorne ao passo III.

Exemplo 3.3.1. Uma construtora tem quatro escavadeiras em quatro garagens diferentes. As
escavadeiras devem ser transportadas a quatro diferentes locais de construção. As distâncias
entre as escavadeiras e os locais de construção são dadas em km na tabela abaixo:

Local1 Local2 Local3 Local4

Escavadeira 1 90 75 75 80
Escavadeira 2 35 85 55 65
Escavadeira 3 125 95 90 105
Escavadeira 4 45 110 95 115

Tabela 3.2: Escavadeiras e as distâncias em relação aos locais de construção

Como devem ser transportadas as escavadeiras para os locais de construção para minimizar a
distância total percorrida?

• Matriz custo:

 
90 75 75 80
 
 35 85 55 65 
 
125 95 90 105
 
45 110 95 115

• Subtraímos a menor entrada de cada linha a todas entradas da mesma linha.

 
15 0 0 5
 
 0 50 20 30
 
35 5 0 15
 
0 65 50 70

36
Matrizes e Grafos

• Subtraímos a menor entrada de cada coluna a todas entradas da mesma coluna.

 
15 0 0 0
 0 50 20 25
 
 
35 5 0 10
0 65 50 65

• Riscamos as entradas zero com um número mínimo de traços horizontais e verticais.

 
15 0 0 0
 
 0 50 20 25
 
35 5 10
 0 
0 65 50 65

• Como o número de traços é inferior a n, subtraimos a menor entrada não riscada da matriz
a cada uma das entradas não riscadas e somamos às entradas riscadas por dois traços.

 
35 0 0 0
 
 0 30 0 5
 
55 5 0 10
 
0 45 30 45

• Ainda não é possível obter uma solução ótima, visto que o número de traços ainda é
inferior a n.

• Subtraímos a menor entrada não riscada de cada uma das entradas não riscadas e somamos
às duas entradas riscadas por dois traços.

 
40 0 5 0
 
 0 25 0 0
 
55 0 5
 0 
0 40 30 40

• Como as entradas zero estão riscadas com um número mínimo de 4 traços horizontais, a
matriz deve conter uma solução ótima de zeros:

 
40 0 5 0
 0 25 
 0 0
 
55 0 0 5
0 40 30 40

• Escavadeira 1 na construção 4 (80km)

Escavadeira 2 na construção 3 (55 km)

Escavadeira 3 na construção 2 (95km)

Escavadeira 4 na construção 1 (45 km)

• 80km+55km+95km+45km=275km é a menor distância percorrida para minimizar os custos.

37
 Matrizes e Grafos

3.4 Aplicação à Criptografia

A descrição desta secção, bem como os exemplos que se seguem, foram referenciados de [2],
páginas 466-468.

A Criptografia é o estudo de codificação e decodificação de mensagens.

Na linguagem da Criptografia, os códigos são denominados cifras, as mensagens não codificadas
são textos comuns e as mensagens são textos cifrados ou criptogramas. O processo de converter
um texto comum em cifrado é chamado cifrar ou criptografar e o processo inverso de converter
um texto cifrado em comum é chamado decifrar.
As cifras mais simples, denominadas cifras de substituição são as que substituem cada letra do
alfabeto por uma outra letra.
Por exemplo, na cifra de substituição

Comum A B C D E F G H I J K L M
Cifra D E F G H I J K L M N O P
Comum N O P Q R S T U V W X Y Z
Cifra Q R S T U V W X Y Z A B C

Tabela 3.3: Cifras de substituição letra por letra.

a letra de texto A é substituída por D, a letra de texto comum B por E e assim por diante.
Vamos apresentar um exemplo de um sistema poligráfico que consiste em dividir um texto co-
mum em conjunto de n letras, cada um dos quais é substituído por um conjunto de n letras
cifradas. Trata-se do sistema poligráfico chamado cifras de Hill que são baseados em transfor-
mações matriciais.
Vamos supor que cada letra de texto comum e de texto cifrado, excetuando Z, tem um valor
numérico que especifica sua posição no alfabeto padrão como mostra a a tabela.

A B C D E F G H I J K L M
1 2 3 4 5 6 7 8 9 10 11 12 13
N O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 0

Tabela 3.4: Cifras de substituição letra por número.

Para transformar pares sucessivos de texto comum em texto cifrado procedemos da seguinte
maneira:

1. Escolhemos uma matriz 2 × 2

[ ]
a11 a12
, com entradas inteiras para efetuar a codificação.
a21 a22

2. Agrupamos letras sucessivas de texto comum em pares, adicionando uma letra adicional
fictícia para completar o último par se o texto comum tem um número ímpar de letras.
Substituímos cada letra de texto comum por seu valor numérico.

38
Matrizes e Grafos

3. Convertemos cada par sucessivo p1 p2 de letras de texto comum em um vetor-coluna

[ ]
p1
P =
p2

e formamos o produto AP, o correspondente vetor cifrado.

4. Convertemos cada vetor cifrado em seu equivalente alfabético.

Exemplo 3.4.1.

Vamos
[ usar]a matriz
1 2
A= para obter a cifra de Hill da mensagem de texto comum (em inglês)
0 3

IAM HIDIN G

Agrupando o texto em pares temos

IA M H ID IN GG. Para completar o último par adicionamos a letra fictícia G. Usando
a tabela 3.4 ,este agrupamento é equivalente a
9 1 13 8 9 4 9 14 77

Codificamos cada par de letras. Sempre que ocorrer um inteiro maior do que 25, ele será
substituído pelo resto da divisão deste inteiro por 26.
[ ] [ ] [ ]
1 2
9 11
IA → . = (mod 26)
0 3 1 3

[
] [ ] [ ] [ ]
13 1 2
29 3
MH → . = = (mod 26)
0 3 8 24 24

[ ] [ ] [ ]
1 2
9 17
ID → . = (mod 26)
0 3 4 12

[ ] [ ] [ ] [ ]
1 2 9 37 11
IN → . = = (mod 26)
0 3 14 42 16

[ ] [ ] [ ]
1 2
7 21
GG → . = (mod 26)
0 3 7 21

Estes vetores correspondem aos pares de texto cifrado QL, QP e U U respetivamente. Cole-
tando os pares obtemos a mensagem cifrada completa

KC CX QL KP UU

que normalmente seria transmitida como uma única cadeia sem espaços:

KCCXQLKP U U

39
 Matrizes e Grafos

O processo de decodificação ocorre de maneira inversa. Para decodificar a mensagem usamos

a matriz inversa (modulo 26) da matriz codificadora. Vejamos um outro exemplo:

Exemplo 3.4.2.

Decifre
[ a cifra
] de Hill, que foi criptografada pela matriz
5 6
A=
2 3
GT N KGKDU SK

Pela tabela 3.4, o equivalente numérico pelo texto cifrado é

7 20 14 11 7 11 4 21 19 11

Para obter os pares de texto comum, nós multiplicamos cada vetor cifrado pela seguinte matriz
[ ]
1 24
B= ,
8 19

que é a matriz igual à matriz A−1 módulo 26 (isto é, A−1 = B(mod 26)).

Temos,
[ ][ ] [ ] [ ]
1 24 7 487 19
= = (mod 26)
8 19 20 436 20

[ ][ ] [ ] [ ]
1 24 14 278 18
= = (mod 26)
8 19 11 321 9

[ ][ ] [ ] [ ]
1 24 7 271 11
= = (mod 26)
8 19 11 265 5

[ ][ ] [ ] [ ]
1 24 4 508 14
= = (mod 26)
8 19 21 431 15

[ ][ ] [ ] [ ]
1 24 19 283 23
= = (mod 26)
8 19 11 361 23

Pela tabela 3.4, os equivalentes alfabéticos destes vetores são

ST RI KE NO WW

que fornece a mensagem

ST RIKE N OW

40
Matrizes e Grafos

Capítulo 4

Teoria de Grafos

A Teoria de Grafos define grafos como sendo o elemento base do estudo e o grafo é representado
por um conjunto de pontos (os nós ou os vértices), ligados por segmentos de retas (as arestas
ou os arcos). Esta teoria permite a resolução de problemas em várias áreas como por exemplo
a dos transportes, a das telecomunicações e as computacionais.
Neste capítulo, começamos por introduzir conceitos básicos e notações da Teoria de Grafos.
Para um estudo mais aprofundado, podemos consultar as seguintes referências: [12], [1], [9] e
[10]. Este trabalho contém informação também daqui retirada.

4.1 Conceitos e resultados fundamentais

Definição 4.1.1. Designa-se por grafo (não orientado) um terno G = (V (G), E(G), ψG )), onde
V = V (G) é um conjunto não vazio, E = E(G) é um conjunto disjunto de V e ψG é uma função
tal que, para cada e ∈ E, ψG (e) denota um par não ordenado de elementos de V . O conjunto V
designa-se por conjunto dos vértices, E por conjunto das arestas e ψG por função de incidência
do grafo G.

Se a função de incidência originar, para cada e ∈ E, um par ordenado de elementos de V , o

−
→ −
→ −
→
terno tem a seguinte notação G = (V ( G ), E( G ), ψ→
− ) e será designado por grafo orientado (ou
G
digrafo). Aqui, o conjunto E designa-se por conjunto dos arcos.

Neste trabalho, temos como objetivo fazer uma abordagem geral à Teoria de Grafos em que
apenas usaremos grafos não orientados e vamos referir-nos apenas ao termo grafo.

De seguida, iremos apresentar algumas designações usadas na Teoria de Grafos.

Para cada aresta e ∈ E de um grafo G, ela resulta da imagem ψG (e) = uv, onde u, v ∈ V e uv é
um par não ordenado. Neste caso, dizemos que: u e v são vértices extremos de e; a aresta e é
incidente aos seus vértices extremos; u e v são vértices adjacentes.
Ao conjunto dos vértices adjacentes a um determinado vértice w ∈ V chamamos vizinhança de
w.
Quando duas arestas são incidentes ao mesmo vértice, dizemos que estas arestas são adja-
centes.
Se duas ou mais arestas têm os mesmos vértices extremos, então dizemos que são arestas múlti-
plas (ou paralelas).
A uma aresta e de um grafo G chamamos lacete se os vértices extremos coincidem num só
vértice, isto é, φG (e) = uu com u ∈ V

41
 Matrizes e Grafos

Figura 4.1: O primeiro grafo é não orientado e o segundo é orientado.

Na figura anterior, no grafo não orientado temos V = {v1 , v2 , v3 , v4 } e E = {e1 , e2 , e3 , e4 , e5 , e6 }.

Podemos observar neste grafo que: as arestas e4 e e5 são múltiplas; a aresta e6 é um lacete; v1
e v4 são os vértices extremos da aresta e1 , estes vértices são adjacentes e a aresta é incidente
a eles; as arestas e1 e e2 são adjacentes.

Definição 4.1.2. Um grafo diz-se simples se não contém arestas múltiplas nem lacetes.

Quando um grafo simples possui um único vértice, dizemos que o grafo é trivial.

Se os conjuntos V e E forem finitos, então dizemos que o grafo é finito e denotamos por ν(G)
ou ν o número de vértices e por ε(G) ou ε o número de arestas de um grafo G. A ν chamamos
a ordem de G e a ε chamamos a dimensão de G. Caso contrário, G é um grafo infinito.

Definição 4.1.3. Dados dois grafos G e H, arbitrários, dizemos que são iguais se

V (G) = V (H), E(G) = E(H) e φG = φH .

Neste caso, escrevemos G = H.

Definição 4.1.4. Dados dois grafos G e H, arbitrários, dizemos que H é um subgrafo se V (H) ⊆
V (G), E(H) ⊆ E(G) e ψH é a restrição de ψG . Denotamos por H ⊆ G. Se H ⊂ G então H é
subgrafo próprio de G.
O grafo H é um subgrafo abrangente (ou suporte) do grafo G se V (H) = V (G).

Definição 4.1.5. Sejam G um grafo e v um vértice arbitrário de G. O grau (ou valência) de v

é o número de arestas incidentes a v, que denotamos por dG (v) ou, simplesmente, por d(v).
Notemos que os lacetes, caso existam, contam duas vezes.

Exemplo 4.1.1. Observando o grafo não orientado da figura 4.1, temos que

dG (v1 ) = 3, dG (v2 ) = 3, dG (v3 ) = 4 e dG (v4 ) = 2 .

42
Matrizes e Grafos

Teorema 4.1.1. Seja G um grafo com ε arestas e ν vértices.

Designemos os vértices de G por v1 , · · · , vν .
A soma dos graus, de todos os vértices, é o dobro do número de arestas. Ou seja,

∑
n
d(vi ) = 2ε
i=1

Demonstração: Esta demonstração será apresentada mais à frente, na subsecção da Matriz de

Incidência porque assim temos um exemplo de aplicação da matriz de incidência na obtenção
de resultados acerca da estrutura de um grafo e também por ser uma demonstração simples.
□

Tendo em conta o exemplo 4.1.1, podemos verificar que

dG (v1 ) + dG (v2 ) + dG (v3 ) + dG (v4 ) = 3 + 3 + 4 + 2 = 12 = 2 × 6 .

A partir do teorema 4.1.1 obtemos o seguinte resultado:

Teorema 4.1.2. O número de vértices de grau ímpar que existe num grafo é sempre par.

Demonstração: Consideremos separadamente os vértices de grau par e os de grau ímpar.

Temos assim

∑
ν ∑ ∑
d(vi ) = d(vj ) + d(vk ) . (4.1)
i=1 d(vj ) par d(vk ) mpar

A primeira parcela do segundo membro da equação anterior é sempre um número par. A segunda
parcela é um número par se o somatório dos graus ímpares tiver uma quantidade par de parcelas.
Ou seja, o número de vértices com grau ímpar tem de ser par. □

Definição 4.1.6. Seja G um grafo simples. Denotamos por Gc o grafo complementar de G, que
é o grafo simples obtido a partir de G cujo conjunto de vértices coincide e no qual quaisquer
dois vértices são adjacentes se e só se não são adjacentes em G.

Figura 4.2: Os grafos são complementares.

Definição 4.1.7. Sejam G = (V (G), E(G), ψG ) e H = (V (H), E(H), ψH ) dois grafos arbitrários.
Dizemos que são isomorfos, e denota-se por G ∼= H, se existem duas bijeções φ : V (G) → V (H)
e θ : E(G) → E(H) tais que

ψG (e) = uv se e só se ψH (θ(e)) = φ(u)φ(v) .

43
 Matrizes e Grafos

No caso de os grafos serem simples, dizemos que são isomorfos se existe uma bijeção φ : V (G) →
V (H) tal que

uv ∈ E(G) se e só se φ(u)φ(v) ∈ E(H) .

Se um grafo tem cada vértice adjacente a todos os outros, então o grafo é chamado de grafo
completo e denota-se por Kn . Por exemplo:

Figura 4.3: Grafos completos K1 , · · · , K5

Um grafo simples G é chamado de grafo nulo quando não tem arestas, ou seja, E(G) = ∅.

Definição 4.1.8. Um grafo G diz-se bipartido se existe uma partição do seu conjunto de vér-
tices V em X e Y , tal que cada aresta de G tem um dos vértices extremos em X e o outro
vértice extremo em Y . Esta partição do conjunto dos vértices do grafo permite representar o
grafo pelo terno (X, Y, E(G)).
Quando quaisquer vértices x ∈ X e y ∈ Y são tal que xy ∈ E(G), dizemos que G é um grafo
bipartido completo. Adicionalmente, se temos dG (x) = s = #(Y ), ∀x ∈ X e dG (y) = t =
#(X), ∀y ∈ Y , então o grafo G é denotado por Ks,t .

Para ilustrar esta definição, apresentamos os dois exemplos seguintes:

Figura 4.4: Grafos bipartidos.

Definição 4.1.9. Um passeio num grafo G é toda a sequência não vazia

P = v0 e 1 v1 e 2 · · · e k vk

tal que v0 , v1 , · · · , vk ∈ V (G), e1 , e2 , · · · , ek ∈ E(G) e os vértices vi−1 e vi são vértices extremos

da aresta ei , para i = 1, · · · , k. O vértice v0 designa-se por vértice inicial do passeio P , o vértice
vk designa-se por vértice final do passeio e os vértices v1 , · · · , vk−1 designam-se por vértices
intermédios de P . Podemos também dizer que P é um passeio entre os vértices v0 e vk .

44
Matrizes e Grafos

• Se num passeio todas as arestas são distintas, então o passeio designa-se por trajeto.
Adicionalmente, se também todos os vértices são distintos, o passeio designa-se por

caminho.

• Se v0 = vk (k ̸= 0) estamos perante um circuito.

• Um ciclo é um passeio com pelo menos uma aresta, onde não se repetem arestas nem
vértices (com exceção dos vértices terminais do passeio).

• O comprimento de um passeio, ou trajeto, ou caminho é igual ao número de arestas que

o constitui (com eventual repetição) .

Exemplo 4.1.2. Considere o grafo abaixo.

Figura 4.5:

Um passeio é, por exemplo, a sequência v1 , v3 , v5 , v6 , v3 , v2 , v1 que tem comprimento 6. Também

é um trajeto porque não há repetição de arestas.
Um exemplo de caminho é a sequência v1 , v2 , v3 , v5 , v6 , com comprimento 4.

Definição 4.1.10. Um grafo diz-se conexo se entre cada par de vértices existe um caminho
que os une. Caso contrário, o grafo diz-se desconexo.

Observemos que um grafo que possui um único vértice v é conexo, uma vez que podemos con-
siderar a existência de um caminho de comprimento nulo entre v e v.
Sendo o grafo G desconexo, podemos repartir o conjunto dos seus vértices em dois ou mais
subconjuntos disjuntos V1 , V2 , · · · , Vk , tais que ∀u ∈ Vi e ∀v ∈ Vj , com i ̸= j, u e v não são
adjacentes. Portanto, G ficará subdividido em k subgrafos, tal que cada subgrafo é conexo. A
estes subgrafos chamamos componentes conexas de G.

O grafo da Figura 4.5 é conexo (visto que entre cada par de vértices existe sempre um caminho
que os une). Na figura seguinte, apresentamos um grafo desconexo:

45
 Matrizes e Grafos

Figura 4.6: Grafo desconexo com duas componentes.

O grafo G é desconexo e facilmente conseguimos reconhecer as suas componentes conexas

divididos em dois subconjuntos V1 = {v1 , v2 , v3 , v4 , V5 } e V2 = {v6 , v7 , v8 , v9 }. Isto motiva-nos ao
teorema que se segue.

Teorema 4.1.3. Um grafo é desconexo se e só se o seu conjunto de vértices V pode ser dividido
em dois subconjuntos disjuntos não vazios V1 e V2 , tal que não existe aresta em G cujo vértice
extremo está no subconjunto V1 e outro no subconjunto V2 .

Demonstração: Suponha que a partição de V existe. Consideremos dois vértices arbitrários a

e b de G, tal que a ∈ V1 e b ∈ V2 . Nenhum caminho pode existir entre os vértices a e b; de
outra maneira, haveria pelo menos uma aresta com um vértice extremo em V1 e outro em V2 .
Consequentemente, se a partição existe, G não é conexo.
De modo inverso, seja G um grafo desconexo. Considere um vértice a em G. Seja V1 o conjunto
de todos os vértices que estão ligados por caminhos até a. Uma vez que G é desconexo, V1 não
inclui todos vértices de G. Os restantes vértices formaram o conjunto não vazio V2 . Nenhum
vértice em V1 é adjacente a algum em V2 . □

Teorema 4.1.4. Se um grafo G tem exatamente dois vértices de grau ímpar, então existe um
caminho unindo estes dois vértices.

Demonstração: Seja G um grafo com todos os vértices de grau par, exceto v1 e v2 , que são de
grau ímpar. O teorema que também é válido para todas as componentes conexas de um grafo
desconexo, afirma que nenhum grafo pode ter um número ímpar de vértices de grau ímpar. Por-
tanto, no grafo G,os vértices v1 e v2 estão na mesma componente conexa e consequentemente
existe um caminho entre eles. □

Definição 4.1.11. Um grafo simples G diz-se uma floresta se G não contém circuitos.
Uma floresta conexa designa-se por árvore, ou seja, consideramos que uma árvore é uma com-
ponente conexa de uma floresta.

Por exemplo:

46
Matrizes e Grafos

Figura 4.7: Floresta formada por três árvores

Definição 4.1.12. Designamos por árvore abrangente (ou de suporte) de um grafo conexo G
a todo subgrafo abrangente de G que é uma árvore e contém todos os vértices do grafo.

Figura 4.8: Grafo G e três árvores abrangentes de G.

4.2 Grafos e Matrizes

Na secção anterior apresentámos vários conceitos da teoria de grafos onde ilustramos um grafo
G na forma pictórica, como um conjunto de pontos ou nós que chamamos vértices e um con-
junto de retas que ligam esses pontos que chamamos de arestas. Foi muito conveniente para
a visualização, porém não é a única maneira de representarmos um grafo, pois existem infor-
mações que um grafo pode conter que não caberiam num papel. As outras representações estão
no campo computacional.
Uma matriz é uma maneira conveniente e útil para representar um grafo no computador. As
matrizes prestam-se facilmente à manipulação mecânica. Além disso, muitos resultados con-
hecidos da álgebra matricial podem ser aplicados para o estudo das propriedades estruturais
dos grafos.
Em muitas aplicações da teoria de grafos, tais como na análise de um circuito elétrico e Pesquisa
Operacional, as matrizes também acabam sendo um caminho natural de expressar o problema.

4.2.1 Matriz de adjacência

Definição 4.2.1. Dado um grafo G tal que V (G) = {v1 , v2 , · · · , vν }, designa-se por matriz de
adjacência dos vértices G, ou simplesmente, matriz de adjacência de G e denota-se por
AG = (aij ), a matriz de dimensão ν × ν, tal que aij é igual ao número de arestas entre os
vértices vi e vj .
No caso de grafos orientados, aij é igual ao número de arcos com cauda em vi e cabeça em vj .

Exemplo 4.2.1. Vamos determinar a matriz de adjacência do grafo representado na seguinte

figura:

47
 Matrizes e Grafos

Figura 4.9:

Não existe nenhum lacete, ou seja, uma aresta do tipo uu (u ∈ V ), consequentemente o ele-
mento da diagonal principal respetivo é zero. Por não existirem arestas múltiplas, a matriz de
adjacência só tem zeros e uns.

v1 v2 v3 v4 v5
v1 0 1 0 1 1
v2 1 0 1 0 1
A(G) = .
v3 0 1 0 1 1
v4 1 0 1 0 1
v5 1 1 1 1 0

Algumas observações importantes podem ser registadas sobre a matriz de adjacência A(G) de
um grafo G:

1. A matriz A(G) é simétrica em relação à diagonal principal.

2. As entradas da diagonal principal de A(G) são iguais a zero se e só se o grafo não tem
lacetes.

3. Se o grafo não tem lacetes nem arestas múltiplas, o grau de um vértice é igual ao número
de 1′ s nas correspondentes linhas e colunas de A(G).

4. Um grafo G é desconexo e está em duas componentes G1 e G2 se e só se a sua matriz de

adjacência A(G) pode ser representada da seguinte forma (matriz por blocos):

 
..
A(G1 ) . 0
 .. 
A(G) = 
 ··· .

···  .
 .. 
0 . A(G2 )

48
Matrizes e Grafos

Exemplo 4.2.2. Dada a seguinte matriz de adjacência de um grafo:

v1 v2 v3 v4 v5 v6 v7 v8 v9
v1 0 1 1 0 1 0 0 0 0
v2 1 0 1 0 0 0 0 0 0
v3 1 1 0 1 0 0 0 0 0
v4 0 0 1 0 0 0 0 0 0
A(G) =
v5 1 0 0 0 0 0 0 0 0
v6 0 0 0 0 0 0 1 1 1
v7 0 0 0 0 0 1 0 1 1
v8 0 0 0 0 0 1 1 0 0
v9 0 0 0 0 0 1 1 0 0

Esta matriz corresponde ao seguinte grafo:

A matriz de adjacência é um exemplo prático de quando queremos saber sobre a estrutura de

um grafo. O próximo resultado, ilustra esta ideia.

Teorema 4.2.1. Seja G um grafo simples e A(G) a sua matriz de adjacência. O número de
passeios de comprimento K entre os vértices vi e vj de G, Pij (k), é igual à entrada akij da
matriz Ak (G).

Demonstração: Vamos fazer a demonstração por indução sobre k.

Para k = 1 o resultado é verdadeiro, na medida em que só existe um único passeio de compri-
mento 1 entre os vértices vi e vj se existir uma aresta que os ligue e neste caso, por definição
de matriz de adjacência aij = 1 = pij (1).
Admitamos, por hipótese de indução, que para k > 2 o número de passeios de comprimento
k-1 entre os vértices vi e vj em G é igual à entrada ak−1
ij da matriz Ak−1 (G). Vejamos para os
passeios de comprimento k.
Ora, Ak (G) = Ak−1 (G).A(G). Assim, qualquer que sejam i, j ∈ {1, 2, · · · , n} vem que

∑
n ∑
n
akij = ak−1
ir arj = pir (k − 1)prj (1) = pij (k)
r=1 r=1

já que cada passeio de comprimento k − 1 entre os vértices i e j acrescentamos uma aresta,

obtemos passeios de comprimento k.
Logo akij = pij (k), para todo o k ≥ 1. Assim, concluímos a demonstração. □

49
 Matrizes e Grafos

Exemplo 4.2.3. Tendo em conta o grafo representado na figura 4.9 e a sua respetiva matriz de
adjacência, vamos fazer alguns apontamentos em relação aos passeios deste grafo.

 
0 1 0 1 1
 
1 0 1 0 1
 
A(G) = 
0 1 0 1 1
 
1 0 1 0 1
1 1 1 1 0

 
3 1 3 1 2
 
1 3 1 3 2
 
A (G) = 
2
3 1 3 1 2
 
1 3 1 3 2
2 2 2 2 4

A entrada a24 = 3 de A2 (G) dá-nos o número de passeios de comprimento 2 entre os vértices

v2 e v4 . São eles:
v 2 , v 2 v3 , v 3 v4 , v 4

v 2 , v 2 v5 , v 5 v4 , v 4

v 2 , v 2 v1 , v 1 v4 , v 4

Agora com a matriz  

4 8 4 8 8
 
8 4 8 4 8
 
A3 (G) = 
4 8 4 8 8
 
4 8 8 4 8
8 8 8 8 8

e observando a entrada a24 que é igual a 4, esta dá-nos o número de passeios de comprimento
3 entre os vértices v2 e v4 . São eles:

v2 , v 2 v3 , v 3 v5 , v 5 v 4 , v 4

v2 , v 2 v5 , v 5 v3 , v 3 v 4 , v 4

v2 , v 2 v1 , v 1 v5 , v 5 v 4 , v 4

v2 , v 2 v5 , v 5 v1 , v 1 v 4 , v 4

Proposição 4.2.1. (Teste de isomorfismo) Dizemos que dois grafos arbitrários são isomorfos se
é possível ordenar os seus respetivos conjunto de vértices tal que as suas matrizes de adjacência
sejam iguais.

Exemplo 4.2.4. Os grafos da figura abaixo são isomorfos são isomorfos porque ordenando os
vértices v1 , v2 , v3 , v4 e os vértices A, D, C, B, os grafos têm a mesma matriz de adjacência.

50
Matrizes e Grafos

v1 v2 v3 v4
v1 0 1 1 1
A(G) = v2 1 0 1 0
v3 1 1 0 1
v4 1 0 1 0

e
A D C B
A 0 1 1 1
A(H) = D 1 0 1 0
C 1 1 0 1
B 1 0 1 0

Figura 4.10:

O resultado que a seguir apresentamos pode ser usado para calcular o número de árvores
abrangentes, em qualquer grafo conexo simples.

Teorema 4.2.2. (Teorema de Kirchhoff ou Teorema da Matriz Árvore). Seja G um grafo simples
com o conjunto de vértices v1 , v2 , · · · , vν e M = [mij ]ν×ν , tal que mii = d(vi ) e para i ̸= j temos
mij = −1 se vi e vj são adjacentes e mij = 0 se vi e vj não são adjacentes.
Então, o número de árvores abrangentes de G é igual ao complemento algébrico de qualquer
elemento de M . (o conceito de complemento algébrico encontra-se no capítulo 2 secção 2.6).

Vamos omitir a demonstração deste teorema porque envolve conceitos que não foram abordados
neste trabalho, contudo apresentaremos um exemplo que ilustra este resultado.

Exemplo 4.2.5. Consideremos o grafo completo K3 :

Figura 4.11: Grafo completo K3 .

51
 Matrizes e Grafos

Temos que d(v1 ) = 2, d(v2 ) = 2 e d(v3 ) = 2.

A Matriz Árvore associada ao grafo dado é
 
2 −1 −1
 
M = −1 2 −1 .
−1 −1 2

Calculemos o complemento algébrico âij de cada um dos elementos mij de M :

[ ] [ ] [ ]
2 −1 −1 −1 −1 2
â11 = det =3 â12 = det =3 â13 = det =3
−1 2 −1 2 −1 −1
[ ] [ ] [ ]
−1 −1 2 −1 2 −1
â21 = det =3 â22 = det =3 â23 = det =3
−1 2 −1 2 −1 −1
[ ] [ ] [ ]
−1 −1 2 −1 2 −1
â31 = det =3 â32 = det =3 â33 = det = 3.
2 −1 −1 −1 −1 2

Como todos os complementos são iguais a 3, que é o número das árvores abrangentes, portanto
as árvores abrangentes são:

Figura 4.12: Árvores abrangentes do grafo completo k3 .

4.2.2 Matriz de Incidência

Definição 4.2.2. Dado um grafo G, tal que V (G) = {v1 , v2 , · · · , vν } e E(G) = {e1 , e2 , · · · , eε },
designa-se por matriz de incidência aresta vértice de G ou, simplesmente, matriz de incidência
de G, a matriz M (G) = (aij ), 1 ≤ i ≤ ν, 1 ≤ j ≤ ε, tal que


 0, Se ej = vp vq , com i ∈/ {p, q};
mij = 1, se ej = vi vk , com k ̸= i;


2, se ej = vi vi .

−
→
No caso de grafos orientados, sem lacetes, as entradas da matriz de incidência M ( G ) = (mij )
são definidas por


 0, Se ej = vp vq , com i ∈ {p, q};
mij = −1, se ej = vk vi , para algum vértice vk ;


1, se ej = vi vk , para algum vértice vk .

Exemplo 4.2.6.

52
Matrizes e Grafos

Figura 4.13: Grafo G da matriz de Incidência

Uma vez que o grafo representado na figura 4.13 é de ordem ν = 7 e dimensão ε = 12, temos

V (G) = {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 }

E(G) = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 , e11 , e12 } .

As arestas são e1 = v1 v2 , e2 = v2 v5 , e3 = v2 v4 , e4 = v2 v3 , e5 = v4 v5 , e6 = v3 v4 , e7 = v4 v6 ,
e8 = v5 v7 , e9 = v5 v7 , e10 = v6 v7 , e11 = v6 v3 , e12 = v1 v3 .

A matriz de incidência deste grafo é dada por

e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12

v1 1 0 0 0 0 0 0 0 0 0 0 1
v2 1 1 1 1 0 0 0 0 0 0 0 0
v3 0 0 0 1 0 1 0 0 0 0 1 1
M (G) =
v4 0 0 1 0 1 1 1 0 0 0 0 0
v5 0 1 0 0 1 0 0 1 1 0 0 0
v6 0 0 0 0 0 0 1 1 0 1 1 0
v7 0 0 0 0 0 0 0 0 1 1 0 0

−
→
A figura 4.14 mostra um grafo orientado e sua matriz de incidência M ( G ).

Figura 4.14: Grafo orientado e sua matriz de Incidência

53
 Matrizes e Grafos

e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
A 1 0 0 0 0 0 0 0 0 -1
B -1 1 0 0 0 1 0 0 1 0
−
→
M(G) = C 0 -1 1 0 -1 0 -1 0 0 0
D 0 0 -1 1 0 -1 0 0 0 0
E 0 0 0 -1 1 0 0 1 0 0
F 0 0 0 0 0 0 1 -1 -1 1

Dada uma matriz de incidência de um grafo sem lacetes, podemos fazer as seguintes obser-
vações:

1. Se uma aresta é incidente exatamente em dois vértices, cada coluna de M (G) tem exata-
mente dois 1′ s.

2. O número de 1′ s em cada linha é igual ao grau do vértice correspondente.

3. Uma linha com zeros representa um vértice isolado.

4. As arestas paralelas num grafo originam colunas iguais na matriz de incidência.

5. Se um grafo é desconexo e está dividido em duas componentes conexas G1 e G2 , a matriz

de incidência M (G) do grafo G pode ser escrita em forma de bloco diagonal,como

 
..
M (G1 ) . 0 
 .. 
M (G) = 
 ··· . ··· 

 .. 
0 . M (G2 )

onde M (G1 ) e M (G2 ) são as matrizes de incidência correspondentes a G1 e G2 . Esta

observação resulta no facto de que nenhuma aresta em G1 é incidente nos vértices de G2 ,
e vice-versa. Obviamente que esta nota é válida para um grafo desconexo sem nenhum
número de componentes conexas.

6. A permutação de quaisquer linhas ou colunas na matriz de incidência, simplesmente cor-

responde em remarcar os vértices e as arestas no mesmo grafo.

De seguida, vamos demonstrar o teorema 4.1.1, que é uma aplicação onde se usa a matriz de
incidência:

Demonstração: Seja V (G) = {v1 , v2 , · · · , vν } e E(G) = {e1 , e2 , · · · , eε } e seja M (G) = (mij ) a

correspondente matriz de incidência. Logo, a soma da linha correspondente ao vértice v é igual
∑
dG (v) e, como consequência, v∈V dG (v) é igual à soma de todas as entradas da matriz M (G).
Por outro lado, uma vez que a soma das entradas de cada coluna de M (G) é igual a 2, podemos
concluir que a soma de todas as entradas de M (G) é igual a 2ε
□

Este teorema vem reforçar o teorema 4.1, que já foi demonstrado.

54
Matrizes e Grafos

No caso de grafos orientados, podemos também concluir que:

∑ ∑
d+
G (v) = d−
G (v) = |E(G)| = ε .
v∈V (G) v∈V (G)

4.2.3 Espaço vetorial do conjunto de vértices

Nesta abordagem, pretendemos mostrar que uma árvore abrangente de um grafo simples, cor-
responde a uma base do espaço coluna da matriz de incidência de G.

Da Álgebra Linear sabemos que o espaço coluna de uma matriz A ∈ Mm×n (R) é o conjunto dos
vetores coluna que são combinações lineares das colunas de A.

Seja G um grafo simples com n vértices e m arestas e seja {e1 , e2 , · · · , em } e {v1 , v2 , · · · , vn }

ordenações fixas de E(G) e V (G), respetivamente.

Analogamente para o espaço de arestas WE (G), a coleção do subconjunto de vértices de V (G)

sob soma de anel, forma um espaço vetorial no campo infinito Z2 = {0, 1}( módulo 2).

Nesta configuração, M (G) representa a transformação linear do espaço de arestas WE (G) para
o espaço de vértices WV (G) mapeando os vetores caraterísticos do subconjunto de arestas para
os vetores caraterísticos dos subconjuntos de vértices.

Exemplo 4.2.7. Considere o grafo G e a sua correspondente matriz de incidência M(G).

Figura 4.15: Grafo G e sua matriz de incidência

e1 e2 e3 e4 e5
v1 1 0 0 1 1
M (G) = v2 1 1 0 0 0
v3 0 1 1 0 1
v4 0 0 1 1 0

O vetor caraterístico da imagem do subspaço E1 = {e1 , e3 , e5 }, é obtido multiplicando o vetor

55
 Matrizes e Grafos

caraterístico E1 por M (G) (módulo 2), como se segue:

 
  1  
1 0 0 1 1   0
  0  
1 1 0 0 0    
  . 1 = 1 (módulo 2).
0 1 
   
 1 1 0   0
0
0 0 1 1 0 1
1

Portanto, E1 é mapeado para o subconjunto de vértices V1 = {v2 , v4 }. De notar que V1 consiste

nos pontos extremidades do caminho formado pelas arestas de E1 , que é uma árvore abrangente
do grafo G.

Figura 4.16: Árvore abrangente do grafo G

Todo o caminho aberto em G é mapeado para o subconjunto de vértices, que consiste nos
caminhos com vértices iniciais e finais.

4.3 Matriz de circuito e matriz de caminho

Para terminar este capítulo vamos definir dois tipos de matrizes que decorrem da aplicação da
matriz de incidência: a matriz de circuito e a matriz de caminho. Na prática, estas matrizes
são usadas nas redes de telecomunicações e de transportes.

Definição 4.3.1. Seja q o número de diferentes circuitos no grafo G e ε o número de arestas

em G. Assim a matriz de circuito B = [bij ] de G é um q × ε matriz de zeros e uns (mod 2)
definido como se segue
{
1, Se o i-ésimo circuito inclui a j-ésima aresta
bij = .
0, caso contrário

Para salientar o facto de que B é uma matriz de circuito do grafo G, a matriz de circuito
também pode ser escrita como B(G). Vejamos um exemplo a partir do grafo da figura 4.17 e a
sua respetiva matriz de incidência.

e1 e2 e3 e4 e5 e6 e7 e8
v1 0 0 0 1 0 1 0 0
v2 0 0 0 0 1 1 1 1
M (G) = v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
v5 0 0 1 1 0 0 1 0
v6 1 1 0 0 0 0 0 0

56
Matrizes e Grafos

Figura 4.17: Grafo e sua matriz de incidência

O grafo tem quatro circuitos diferentes, que são: {e1 , e2 }, {e3 , e5 , e7 }, {e4 , e6 , e7 } e {e3 , e4 , e6 , e5 }.
Enumerando estes circuitos temos a sequência 1, 2, 3 e 4. Portanto a sua matriz de circuito é do
tipo 4 × 8 com zeros e uns.

e1 e2 e3 e4 e5 e6 e7 e8
1 1 1 0 0 0 0 0 0
B(G) = 2 0 0 1 0 1 0 1 0
3 0 0 0 1 0 1 1 0
4 0 0 1 1 1 1 0 0

As observações seguintes podem ser feitas sobre a matriz B(G) do grafo G:

1. Uma coluna com todas entradas iguais a zero corresponde a aresta que não pertence a
nenhum circuito.

2. Cada linha de B(G) é um vetor circuito.

3. Ao contrário da matriz de incidência, uma matriz de circuito é capaz de representar um

lacete. A correspondente linha terá um único 1.

4. O número de 1′ s numa linha é igual ao número de arestas no circuito correspondente.

5. Se o grafo é desconexo e consiste em dois blocos (ou componentes) G1 e G2 , a matriz de

circuito B(G) pode ser escrita em forma de bloco diagonal, como
 
..
B(G1 ) . 0 
 .. 
B(G) = 
 ··· . ··· 

 .. 
0 . B(G2 )

onde, B(G1 ) e B(G2 ) são matrizes de circuito de G1 e G2 . Esta observação resulta no

facto de que os circuitos em G1 não têm arestas pertencendo em G2 ,e vice-versa.

6. A permutação de quaisquer linhas ou colunas na matriz de circuito simplesmente corre-

sponde em reordenar o circuito e as arestas.

57
 Matrizes e Grafos

Um importante teorema que relaciona a matriz de incidência e a matriz de circuito de um grafo

G sem lacetes é:

Teorema 4.3.1. Seja B(G) e M (G), matriz de circuito e matriz de incidência respetivamente
de um grafo G sem lacetes, cujas colunas estão dispostas usando a mesma ordem das arestas.
Então toda linha de B(G) é ortogonal para toda linha de M (G).

M (G).B T (G) = B(G).M T (G) = 0(mod 2)

Demonstração: Considere um vértice v e um circuito ∁ no grafo G. Ou v está em ∁ ou não está.

Se v não está em ∁, não existe aresta no circuito ∁ que é incidente em v. De outra maneira, se
v está em ∁, o número de arestas no circuito ∁ que são incidentes em v, são exatamente duas.
Com esta observação em mente, considere a i-ésima linha em M (G) e a j-ésima linha de B(G).
Desde que as arestas estejam dispostas na mesma ordem, as entradas diferentes de zero nas
posições correspondentes ocorrem somente se a aresta particular é incidente no i-ésimo vértice
e também está no j-ésimo circuito.
Se o i-ésimo vértice não está no circuito, não existe tal entrada diferente de zero e o produto
interno de duas linhas é zero. Se o i-ésimo vértice está no i-ésimo circuito, há exatamente dois
1′ s na soma de produtos de entradas individuais.
Desde que 1 + 1 = 0 (mod 2), o produto interno de duas linhas arbitrárias, uma de M (G) e outra
de B(G) é zero. Assim fica demonstrado o teorema. □

Exemplo 4.3.1. Multipliquemos a matriz de incidência e a matriz transposta de circuito do

grafo da figura 4.17.  
  1 0 0 0
  
0 0 0 1 0 1 0 0 1 0 0 0
    0 0 0 0

0 1 0 1
 0 0 0 1 1 1   1 0  0 0 0 0
0    
 0 0 0 0 0 0 1  0 0 1 1 
=0 0 0 0
M (G).B T (G) =  . 
    (mod 2).
1 1 1 0 1 0 0 
0 0 1 0 
1 0 0 0 0
    
0 0 0
 0 1 1 0 0 1  0 0 1 1 0 0 0 
0 0
1 1 0 0 0 0 0 0  1 1  0 0 0 0
0 0 0 0

A matriz de circuito de um grafo G, possui uma submatriz que está relacionada com a árvore
abrangente do grafo. Esta árvore forma um circuito chamado de circuito fundamental. É fácil
notar que se adicionarmos uma aresta em dois vértices deste circuito, criamos um novo circuito
o que nos dá a confirmação de que além do circuito fundamental temos outros circuitos que são
obtidos como combinação linear do circuito fundamental.
Numa matriz de circuito, se mantivermos apenas todas as linhas que correspondem ao conjunto
do circuito fundamental e removermos as outras linhas, não perderemos nenhuma informação.
As restantes linhas podem ser reconstituídas a partir das linhas que correspondem ao conjunto
de circuito fundamental. Por exemplo na matriz de circuito do grafo da figura 4.17, a quarta
linha é a soma da segunda linha com a terceira linha (mod 2).
A uma submatriz de uma matriz de circuito em que todas linhas correspondem a um conjunto
de circuitos fundamentais é chamada de matriz fundamental de circuito.
Se n é o número de vértices e ε é o número de arestas num grafo conexo, a matriz fundamental
de circuito é da forma (ε − n + 1) × ε, porque o número de circuitos fundamentais é ε − n + 1.

58
Matrizes e Grafos

A matriz fundamental de circuito denota-se por

Bf (G) = [Iu |Bt ] ,

onde Iu é a matriz identidade de ordem u = ε − n + 1 e Bt é a submatriz u × (n − 1) restante,

que corresponde aos ramos da árvore abrangente.
Na figura 4.18 temos um exemplo de uma árvore abrangente do grafo G (grafo da figura 4.17)
e a respetiva matriz fundamental de circuito.

Figura 4.18: Árvore abrangente e a sua matriz fundamental de circuito.

e1 e3 e4 e2 e5 e6 e7 e8
1 1 0 1 0 0 0 0 0
Bf (G) = 2 0 1 0 0 1 0 1 0
3 0 0 1 0 0 1 1 0
4 0 0 0 0 0 0 0 0

Observamos que durante o processo de escalonamento permutamos as colunas e2 , e3 e e4 .

Definição 4.3.2. A matriz de caminho é definida por um par específico de vértices (x, y) em
um grafo e é denotada por P (x, y). As linhas em P (x, y) correspondem a diferentes caminhos
entre os vértices x e y, e as colunas correspondem as arestas em G, isto é, a matriz de caminho
para os vértices (x, y) é P (x, y) = [Pij ], onde
{
1, Se a j-ésima aresta encontra-se no i-ésimo caminho.
Pij = .
0, caso contrário

Como ilustração, considere todos caminhos entre os vértices v3 e v4 do grafo da figura 4.17.
Existem três caminhos diferentes:{e8 , e5 }, {e8 , e7 , e3 } e {e8 , e6 , e4 , e3 }.Vamos enumerá-los como
1, 2 e 3, respetivamente. Então temos uma matriz de caminhos 3 × 8, P (v3 , v4 ):

e1 e2 e3 e4 e5 e6 e7 e8
1 0 0 0 0 1 0 0 1
P (v3 , v4 ) =
2 0 0 1 0 0 0 1 1
3 0 0 1 1 0 1 0 1

59
 Matrizes e Grafos

Dada uma matriz de caminho de um grafo, podemos fazer as seguintes observações:

1. Uma coluna de 0′ s corresponde a uma aresta que não se encontra em qualquer caminho
entre x e y.

2. Uma coluna de 1′ s corresponde a uma aresta que se encontra em todos caminhos entre x
e y.

3. Não existe uma linha nula, isto é, com todas entradas iguais a zero.

4. A soma de quaisquer duas linhas em P (x, y) corresponde a um circuito.

5. Se as arestas de um grafo conexo estão dispostas na mesma ordem para as colunas da

matriz de incidência M (G) e o caminho P (x, y), então o produto (mod 2)

M (G).P T (x, y) = R

onde a matriz R tem 1′ s em duas linhas x e y e as restantes n − 2 linhas são nulas.

Para consolidarmos a última observação, apresentamos a seguir um exemplo.

Exemplo 4.3.2. Vamos multiplicar a matriz de incidência do grafo da figura 4.17 com a trans-
posta de P (v3 , v4 ).
 
  0 0 0
 
0 0 0 1 0 1 0 0 0 0 0 v1 0 0 0
   
0 1 0 
 0 0 0 1 1 1   1 1 v2 0 0 0
0  
 0 0 0 0 0 0 1 0
 0 1 v3 1 1 1
M (G).P T (v3 , v4 ) =   1 = (mod 2).
1
 1 1 0 1 0 0 0  0 0 v4 1 1 1
0  
 0 1 1 0 0 1 0 0
 0 1 v5 0 0 0
0 
1 1 0 0 0 0 0 0  1 0 v6 0 0 0
1 1 1

60
Matrizes e Grafos

Capítulo 5

Considerações Finais

O estudo sobre Matrizes e sobre Grafos é um campo vasto e não se encerra nesta abordagem.
Na realidade o trabalho feito é uma gota no oceano. O uso das matrizes no estudo dos grafos
tem sido e continua sendo objeto de intensa investigação, a literatura é cada vez mais vasta.
Neste trabalho procurámos, de forma sintética, apresentar os conceitos relacionados com a
Álgebra Matricial em direção às Transformações Lineares. Partimos de definições elementares
e sempre que possível providenciamos exemplos que reforcem as definições e as propriedades.
A teoria de matrizes foi necessária para dar suporte às aplicações e principalmente à Teoria de
Grafos. A partir das matrizes de adjacência e incidência foi possível saber sobre a estrutura de
um grafo e conseguimos investigar resultados.

61
 Matrizes e Grafos

62
Matrizes e Grafos

Bibliografia

[1] D.M. Cardoso, J. Szymanski, M. Rostami, Matemática Discreta. Escolar Editora (2009) 41

[2] A. Rorres, Algebra Linear com Aplicações, John Wiley, 2012. 31, 35, 38

[3] I. Cabral, C. Perdigão,C. Saiago, Álgebra Linear, Escolar editora, 2009.

[4] A.P. Santana J.F. Queiró, Introdução à Álgebra linear, grádiva, 2013. 5

[5] D.C. Lay, S. Lay, J.J. McDonald, Linear Algebra and its Applications, Pearson, 2016. 5

[6] M.A.F. Neves, L. Faria, B. Ribeiro,Mátemática Aplicada às Ciências Sociais, 11ºAno, 1ª

edição, Porto Editora. 3

[7] C.B. Boyer, História da Matemática, Edgard Blucher Ltda, 2003. 1

[8] M.F. Estada, C. C. de Sá, J.F. Queiró, M. Silva, M. J. Costa, História da Matemática, Uni-
versidade Aberta, 2000. 1

[9] J. Grosss, J. Yellen,Graph Theory and its Applications, Gross Yellen, 1998. 41

[10] C. Marques, V. Miranda, J. Mosca, J. Maças , R. P. dos Santos, Cálculo Matricial, Vol III-
Aplicações, Instituto Piaget. 41

[11] H. Anton, R.C. Busby, Álgebra Linear Contemporânea, ARTMED Editora S.A, 2003. 33

[12] N. Deo, Graph Theory with Applications to Engineering and Computer Science, Dover Pub-
lications, 1974. 1, 41

63