MATRIZES, DETERMINANTES E SISTEMAS LINEARES - REDEFOR

Prévia do material em texto

MA005 - Matrizes, Determinantes e Sistemas Lineares
Mo´dulo III do curso de Matema´tica da Redefor
Aula de exerc´ıcios I
Informalmente, um grafo G e´ um par (V,E) composto de um conjunto de
pontos (tambe´m chamados de ve´rtices) V e outro conjunto de arestas (muitas
vezes representadas por segmentos curvados) E, nos quais pontos podem
estar ligados a outros pontos pelas arestas de E, que por sua vez podem ser
direcionadas ou na˜o. As figuras abaixo, por exemplo, sa˜o representac¸o˜es de
grafos:
Observem que no primeiro grafo ha´ arestas que ligam um ve´rtice a ele
mesmo, no segundo, as arestas indicam sentidos de um ve´rtice a outro, e
no terceiro, todos os ve´rtices esta˜o ligados uns aos outros, mas sem uma
indicac¸a˜o de sentido. Observem ainda que no terceiro grafo acima, toda
aresta liga dois ve´rtices diferentes entre si e que na˜o ha´ duas arestas que
ligam o mesmo par de ve´rtices. Um tal grafo e´ chamado de grafo simples.
Grafos sa˜o estruturas bastante interessantes e contam com diversas aplica-
c¸o˜es, como, por exemplo, no controle do tra´fego urbano em uma cidade, no
escoamento de mercadorias do fabricante de um determinado produto a`s
revendas ou mesmo na distribuic¸a˜o de energia pelas diversas regio˜es de um
pa´ıs.
E´ poss´ıvel e fa´cil representar grafos matricialmente, sendo este o objetivo
desta aula de exerc´ıcios. Por simplicidade, faremos isto apenas para grafos
simples na˜o-direcionados, ou seja, para grafos cujas arestas na˜o conte´m uma
informac¸a˜o de sentido.
Seja, enta˜o, G = (V , E) um grafo simples de n ve´rtices, v1, v2, . . ., vn
e na˜o-direcionado. A matriz de adjaceˆncias A = (aij) do grafo G com
1
respeito aos ve´rtices dados e´ uma matriz de ordem n, cujas entradas sa˜o
assim determinadas:
aij =
{
1, se vi e vjesta˜o ligados por uma aresta de G,
0, caso contra´rio.
Exemplo: Renomeando os ve´rtices do seguinte grafo
de a = v1, b = v2, c = v3 e d = v4, obtemos como matriz de adjaceˆncias para
o grafo que e´ a seguinte: 
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
 .
Exerc´ıcio 1. Desenhe o grafo que corresponde a seguinte matriz de ad-
jaceˆncias: 
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
 ,
com relac¸a˜o aos ve´rtices a = v1, b = v2, c = v3 e d = v4.
Soluc¸a˜o: Consulte a u´ltima pa´gina deste documento para a soluc¸a˜o.
Pode-se perceber que a matriz de adjaceˆncias de um grafo simples e´
sime´trica, ou seja, que aij = aji para todo i e todo j. Isto ocorre sim-
plesmente porque, se um ve´rtice vi esta´ ligado a outro ve´rtice vj por uma
dada aresta, enta˜o vj tambe´m esta´ ligado a vi e, se vi na˜o esta´ ligado a vj,
vj tambe´m na˜o esta´ ligado a vi.
Exerc´ıcio 2. Mostre que as matrizes de adjaceˆncias correspondentes a grafos
simples ainda teˆm todas as suas entradas da diagonal principal nulas.
Soluc¸a˜o: Consulte a u´ltima pa´gina deste documento para a soluc¸a˜o.
2
Matrizes de adjaceˆncias tambe´m podem ser usadas para representar grafos
na˜o-direcionados em que pares de ve´rtices podem estar ligados por mais de
uma aresta, inclusive com arestas ligando ve´rtices a eles mesmos. Quando
isto ocorre, o elemento aij da matriz de adjaceˆncias e´ tomado como sendo o
nu´mero de arestas que ligam os ve´rtices vi e vj.
Exemplo. O grafo
tem 
0 3 0 2
3 0 1 1
0 1 1 2
2 1 2 0

como matriz de adjaceˆncias.
Exerc´ıcio 3. Represente o seguinte grafo
usando uma matriz de adjaceˆncias.
Soluc¸a˜o: Consulte a u´ltima pa´gina deste documento para a soluc¸a˜o.
3
Soluc¸o˜es
Exerc´ıcio 1.
Exerc´ıcio 2. Basta notar que em grafos simples na˜o ha´ arestas ligando um
dado ve´rtice a ele mesmo. Isto necessariamente implica que aii = 0, para
todo i.
Exerc´ıcio 3. 
1 0 2 1
0 1 1 2
2 1 1 0
1 2 0 1

4