08 - Grafo

Prévia do material em texto

GRAFO
RESUMO TEÓRICO
G(VE) UNIÃO DE UM CONJUNTO FINITO NÃO VAZIOG(V,E), UNIÃO DE UM CONJUNTO FINITO NÃO-VAZIO
DE VÉRTICES “V” AUM CONJUNTO DEARESTAS “E”.
ARESTAS:
ÃSÃO OS ELEMENTOS DE “E”.
VÉRTICES:VÉRTICES:
SÃO OS ELEMENTOS DE “V”.
AS ARESTAS DE “E” SÃO LIMITADAS POR DOIS
É
SÃO OS ELEMENTOS DE V .
VÉRTICES ADJACENTES DE “V” EM SEUS
EXTREMOS, UM VÉRTICE EM CADAEXTREMIDADE.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 1
GRAFO
RESUMO TEÓRICO
UMA ARESTA É DITA INCIDENTE A AMBOS OSUMA ARESTA É DITA INCIDENTE A AMBOS OS
VÉRTICES DE SEUS EXTREMOS.
DUAS OU MAIS ARESTAS SÃO CHAMADAS
ADJACENTES SE POSSUEM UM EXTREMO COMUMADJACENTES SE POSSUEM UM EXTREMO COMUM.
O LAÇO É FORMADO POR UMA ARESTA COMO ÇO O O O U S CO
EXTREMIDADES COMUM. (EXTENSÃO DA
DEFINIÇÃO).Ç )
ARESTA PARALELAS SÃO AS QUE POSSUEM O
É ÃMESMO PAR DE VÉRTICES EXTREMOS. (EXTENSÃO
DADEFINIÇÃO).
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 2
GRAFO
RESUMO TEÓRICO
O GRAU DE UM VÉRTICE É DADO PELO NÚMERO DE
VÉRTICES ADJACENTES.
UM GRAFO É REGULAR DE GRAU “R”, QUANDO
É ÍTODOS OS SEUS VÉRTICES POSSUÍREM O MESMO
GRAU “R”.
UM CONJUNTO DE VÉRTICES QUE DEFINE UM
CONJUNTO DE ARESTAS ADJACENTES DUAS A DUAS
É DENOMINADO CAMINHO DE UM VÉRTICE A
à ÉOUTRO. DIZ ENTÃO QUE UM VÉRTICE ALCANÇA OU
ATINGE O OUTRO.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 3
GRAFO
RESUMO TEÓRICO
UM CAMINHO COM “K” VÉRTICES É FORMADO PORUM CAMINHO COM K VÉRTICES É FORMADO POR
“K-1” ARESTAS. ESTE VALOR É DENOMINADO
COMPRIMENTO DO CAMINHOCOMPRIMENTO DO CAMINHO.
SE TODOS OS VÉRTICES DO CAMINHO FOREM
ÜÊDISTINTOS A SEQÜÊNCIA RECEBE O NOME DE
CAMINHO SIMPLES OU ELEMENTAR.
SE AS ARESTA DE UM CAMINHO FOREM DISTINTAS A
SEQÜÊNCIADENOMINA-SE TRAJETOSEQÜÊNCIADENOMINA-SE TRAJETO.
CICLO É UM CAMINHO DE COMPRIMENTO MAIOR
É ÓDO QUE “1” CUJO VÉRTICE ALCANÇA ELE PRÓPRIO.
SE O CAMINHO É SIMPLES O CICLO TAMBÉM O É.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 4
GRAFO
RESUMO TEÓRICO
ÉUM GRAFO QUE NÃO POSSUI CICLOS SIMPLES É
ACÍCLICO.
UM GRAFO É CONEXO QUANDO EXISTE CAMINHO
ÉENTRE CADA PAR DE VÉRTICES DE “V”, CASO
CONTRÁRIO O GRAFO É DESCONEXO.
A DISTÂNCIA ENTRE DOIS VÉRTICES DE UM GRAFO
É O O CA O OS S OSÉ OMENOR CAMINHO ENTRE OS MESMOS.
ÉUM GRAFO É COMPLETO QUANDO EXISTE UMA
ARESTAENTRE CADA PAR DE VÉRTICES.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 5
GRAFO
RESUMO TEÓRICO
UM GRAFO PODE SER VISUALIZADO ATRAVÉS DE
UMA REPRESENTAÇÃO GEOMÉTRICA, NA QUAL,UMA REPRESENTAÇÃO GEOMÉTRICA, NA QUAL,
SEUS VÉRTICES CORRESPONDEM A PONTOS
DISTINTOS, EM POSIÇÕES ARBITRÁRIAS E AS SUAS, Ç
ARRESTAS SÃO ASSOCIADAS LINHAS ARBITRÁRIAS,
CADAUMAUNINDO DOIS VÉRTICES ADJACENTES.
REDE OUMALHA:REDE OU MALHA:
É G A O CO OÉ UM GRAFO CONEXO.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 6
GRAFO
RESUMO TEÓRICO
.
. .
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 7
GRAFO
RESUMO TEÓRICO
EXEMPLOS:
REDE ELÉTRICA, OS NÓS SÃO AS SUBESTAÇÕES
OU BIFURCAÇÕES E OS RAMOS SÃO AS LINHASOU BIFURCAÇÕES E OS RAMOS SÃO AS LINHAS
DE TRANSMISSÃO.
REDE DE ESGOTOS OS NÓS SÃO ASREDE DE ESGOTOS, OS NÓS SÃO AS
CONECÇÕES E OS RAMOS SÃO AS
TUBULAÇÕESTUBULAÇÕES.
TRÁFEGO DE VEÍCULOS URBANOS, OS NÓS SÃO
ÃAS ESQUINAS E OS RAMOS SÃOAS RUAS.
NA CONSTRUÇÃO CIVIL, OS NÓS SÃO AS
INTERSEÇÕES DAS VIGAS E OS RAMOS SÃO AS
VIGAS.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 8
GRAFO
RESUMO TEÓRICO
UM GRAFO É DENOMINADO ROTULADO EMUM GRAFO É DENOMINADO ROTULADO EM
VÉRTICES (OU ARESTAS) QUANDO O CADA VÉRTICE
(OU ARESTA) ESTIVER RESPECTIVAMENTE
É
(OU ARESTA) ESTIVER RESPECTIVAMENTE
ASSOCIADO UM CONJUNTO DENOMINADO RÓTULO.
QUANDO ATRIBUI-SE VALORES AOS VÉRTICES E/OU
ÀSARESTAS, TEMOS UM GRAFO VALORADO.
PODE SER ATRIBUÍDO O SENTIDO DE PERCURSO AS
RESTAS, NESTE CASO O GRAFO É CHAMADO DERESTAS, NESTE CASO O GRAFO É CHAMADO DE
DÍGRAFO.
à ÉAS ARESTAS COM SENTIDO DUPLO NÃO É PRECISO
ESPECIFICA-LOS.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 9
GRAFO
RESUMO TEÓRICO
A 3 10A
C
D
F
3
5
7 8
64 10
E1 2
7 8
9
O G A O AC A S 8 (O O) CA OS
B
NO GRAFO ACIMA, EXISTEM 8 (OITO) CAMINHOS
SIMPLES ENTRE OS VÉRTICES “A” E “C”.
ÃOS CAMINHOS SÃO COMPOSTOS PELAS SEGUINTES
ARESTAS:
(3), (4-5-6), (4-5-8-9-2), (4-7--8-6), (4-7-9-2), (1-2), (1-9-8-6) E
(1-9-7-5-6).
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 10
GRAFO
RESUMO TEÓRICO
A
CF
3
5 64 10
A S É CA
C
D
E
F
1 2
5
7 8
64
MATRIZ SIMÉTRICA.
FEDCBA
E1 2
9
⎥⎥
⎤
⎢⎢
⎡
090201
004310
PARA UM DÍGRAFO, A B
AB
⎥⎥
⎥
⎢⎢
⎢
6000123
090201,MATRIZ PODE SER
ASSIMÉTRICA. C
B
⎥⎥
⎥
⎢⎢
⎢
807090
570004SUBSTITUINDO 1 (UM), AOS
VALORES DIFERENTES DE E
D
⎥⎥
⎥
⎦⎢⎢
⎢
⎣ 085600
807090
ZERO, A MATRIZ É
CHAMADA INCIDÊNCIA. F
E
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 11
GRAFO
APLICAÇÃO – sistema de equações
equ. ele. x1 ⇒ a11.x1 + a12.x2 + a13.x3 + a14.x4 = b1
equ. ele. x2
equ ele x ⇒
⇒ a21.x1
a x
+
+
a22.x2
a x
+
+
a23.x3
a x
+
+
a24.x4
a x
=
=
q 1 11 1 12 2 13 3 14 4 1
b2
bequ. ele. x3
equ. ele. x4
⇒
⇒
a31.x1
a41.x1
+
+
a32.x2
a42.x2
+
+
a33.x3
a43.x3
+
+
a34.x4
a44.x4
=
=
b3
b4
Relação entre elementos
⎨⎧ Relação própria do elemento xi, se i = j.⎩⎨
Obs : A equação i relaciona o elemento próprio x com as relações
aij Relação mutua entre os elementos xi e xj, se i ≠ j.
Obs.: A equação i relaciona o elemento próprio xi, com as relações
mútuas com todos os outros elementos adjacentes, j ≠ i.
Na engenharia a maioria dos sistemas analisados é esparso MaisNa engenharia, a maioria dos sistemas analisados é esparso. Mais
de 2/3 dos elementos, da matriz dos coeficientes, são nulos e não
necessitam ser armazenados. Existem poucas ligações mútuas.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 12
GRAFO
APLICAÇÃO – sistema de equações
Relação própria do elementos xip p i
Se aii = 0 ⇒ xi
S ≠ 0
Elemento da diagonal nulo
E i l ã ó i
Relação mútua entre elementos xi, xj, (i ≠ j)
Se aii ≠ 0 ⇒ aijxi Existe relação própria
a
Se aij = aji = 0 ⇒ xi xj Elementos mutuamente independentes
aji
Se aij ≠ 0 e aji = 0 ⇒ xi xj
aij Matriz dos coeficientes é assimétrica
Se 0 ≠ aij ≠ aji ≠ 0 ⇒
aji
aij
xi xj Matriz incidência é simétrica
aij
Se aij = aji ≠ 0 ⇒ xi xj
aij Matriz dos coeficientes é simétrica
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 13
i j
GRAFO
APLICAÇÃO – sistema de equações
Ordenação das equações
As equações devem ser postas em linhas. na mesma ordem em que os elementos ficaram
nas colunas, ou seja, os elementos próprio têm que ficar na diagonal principal.
equ. ele. x1
equ. ele. x4
⇒
⇒
a11.x1
a41.x1
+
+
a12.x2
a42.x2
+
+
a13.x3
a43.x3
+
+
a14.x4
a44.x4
=
=
b1
b4⎪⎪⎨
⎧
equ ele x
equ. ele. x3
q 4
⇒
⇒ a x
a31.x1
41 1
+
+
a x
a32.x2
42 2
+
+
a x
a33.x3
43 3
+
+
a x
a34.x4
44 4
=
=
b
b3
4
⎪⎪⎩
⎪⎨Certo
equ. ele. x2 ⇒ a21.x1 + a22.x2+ a23.x3 +a24.x4 = b2⎩
equ. ele. x1
l
⇒ a11.x1 + a12.x2 + a13.x3 + a14.x4 = b1
b⎪⎪
⎧
equ. ele. x3
equ. ele. x4
⇒
⇒
a31.x1
a41.x1
+
+
a32.x2
a42.x2
+
+
a33.x3
a43.x3
+
+
a34.x4
a44.x4
=
=
b3
b4Errado
⎪⎪
⎪⎪⎨
equ. ele. x2 ⇒ a21.x1 + a22.x2 + a23.x3 + a24.x4 = b2⎪⎩
Para o segundo conjunto, a ordem certa é: eq. ele. x1eq. ele. x2eq. ele. x3eq. ele. x4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 14
GRAFO
APLICAÇÃO – sistema de equações
Sistema - 1
equ. ele. x2 ⇒ a21.x1 + a22.x2 + 0.x3 + 0.x4 =
equ. ele. x1 ⇒ a11.x1 + a12.x2 + a13.x3 + a14.x4 = b1
b2equ. ele. x2
equ. ele. x3
equ ele x⇒
⇒
⇒
a21.x1
a31.x1
a x
+
+
a22.x2
0.x2
0 x
+
+
0.x3
a33.x3
0 x
+
+
0.x4
0.x4
a x
=
=
b2
b3
b
Grafo do Sistema - 1
equ. ele. x4 ⇒ a41.x1 + 0.x2 + 0.x3 + a44.x4 = b4
b
a22
x2 b2
a33
a13 = a31 x1 x3b1 b3
a44
a33
a11
x4 b4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 15
4 4
GRAFO
APLICAÇÃO – sistema de equações
Triangularização de Gauss aplicado ao elemento x1
2221
14131211
00aa
aaaa
2423
#
22
14131211
0 aaa
aaaa
2
1
x
x
2
1
b
b
2
1
x
x
#
2
1
b
b
4441
3331
2221
00
00
aa
aa
#
444342
34
#
3332
242322
0
0
aaa
aaa⇒
4
3
2
x
x
=
4
3
2
b
b
.
4
3
2
x
x
=.
#
4
#
3
2
b
b
4441 00 aa
Grafo do Sistema - 1
4443424x 4b 4x 4b
bxb
Sem os elementos próprios
a13
b2
a23 = a32 a2
x2
a22
x2 b2
a13
a13⇒
# - Modificado
b1 b3
a = a
24 = a
42
x1 x3
a33
a13 = a31 x1 x3b1 b3
# Modificado
Sublinhado – novo
Tracejado - eliminado b4
a34 = a43
x4
a44
a33
a11
x4 b4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 16
j4 4
GRAFO
APLICAÇÃO – sistema de equações
Reordenação do grafo
a33
x3 b3
33
a24 = a42 x4 x2b4 b2
a11
a22
a44
b
Sistema – 2 (sistema reordenado)
x1 b1
equ. ele. x1
equ. ele. x2
⇒
⇒
a11.x1
0.x1
+
+
0.x2
a22.x2
+
+
0.x3
0.x3
+
+
a14.x4
a24.x4
=
=
b1
b2
equ. ele. x3
equ. ele. x4
⇒
⇒
0.x1
a41.x1
+
+
0.x2
a42.x2
+
+
a33.x3
a43.x3
+
+
a34.x4
a44.x4
=
=
b3
b4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 17
GRAFO
APLICAÇÃO – sistema de equações
Triangularização de Gauss aplicado ao elemento x1
2422
1411
00
00
aa
aa
2422
1411
00
00
aa
aa
2
1
x
x
2
1
b
b
2
1
x
x
2
1
b
b
44434241
3433
2422
00
aaaa
aa
#
444342
3433
2422
0
00
aaa
aa⇒
4
3
2
x
x
=
4
3
2
b
b
.
4
3
2
x
x
=.
#
4
3
2
b
b
44434241
Grafo do Sistema - 2
4443424 4 4 4
x b x b
a33
a = a
x3 b3
a33
x3
a = a
b3
⇒
# - Modificadoaa22
a24 = a42 x4 x2b4 b2
aa22
x4 x2
a24 = a42 b4 b2
Sublinhado – novo
Tracejado - eliminado
a1122a44
x1 b1
a1122a44
b1x1 b1
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 18
GRAFO
APLICAÇÃO – conclusão
O processo de triangularização de Gauss aplicado ao sistema 1 resulta nop g p
aparecimento de seis (06) novos elementos diferentes de zero (0) e
modificação de seis (06) valores, na primeira eliminação; Na segunda
eliminação resulta na modificação de seis (06) valores e na última eliminaçãoeliminação resulta na modificação de seis (06) valores e na última eliminação
resulta na modificação de dois (02) valores, ou seja, resulta no aparecimento
seis (06) novos elementos diferentes de zero (0) e modificação de catorze( ) ( )
(14) valores.
O processo de triangularização de Gauss aplicado ao sistema 2 resulta na
modificação de seis (06) valores, até terminar o processo, sem o
aparecimento de qualquer novo elemento diferente de zero (0).
f li i d ( ) l l i dNo grafo, a eliminação de um (01) elemento, relacionado mutuamente com
mais de um (01) elemento, resulta no aparecimento de novas ligações,
quando não existir ligação direta entre estes elementos mutuamentequando não existir ligação direta entre estes elementos mutuamente
relacionado ao elemento eliminado, ou seja, surgem elementos não nulos na
matriz de coeficiente.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 19
GRAFO
APLICAÇÃO – conclusão
No Sistema – 1 o elemento x1 é relacionado mutuamente com os elementos1
x2, x3 e x4. A sua eliminação interrompe os caminhos entre seus elementos
vizinhos, x2-x1-x3, x2-x1-x4, x3-x1-x2, x3-x1-x4, x4-x1-x2 e x4-x1-x3, então, os
novos elementos a a a a a e a estabelecem estas ligaçõesnovos elementos a23, a24, a32, a34, a42 e a43 estabelecem estas ligações.
No Sistema – 2, o elemento 1 é relacionado mutuamente somente com o
elementos 4, logo, a sua eliminação não resultará em nenhuma nova ligação.elementos 4, logo, a sua eliminação não resultará em nenhuma nova ligação.
No método de eliminação de Gauss utiliza-se os elementos de maior valor
absoluto como pivô, para reduzir a propagação de erro, isto é aplicável
quando a matriz de coeficientes ´tem poucos elementos nulos, porém, na
grande maioria dos problemas de engenharia a diagonal é predominante e a
matriz é esparsa nestes casos adota se a ordenação que produza a menormatriz é esparsa, nestes casos, adota-se a ordenação que produza a menor
quantidade de novos elementos não nulos e em conseqüência menor
propagação de erro.
A utilização da ordenação dos elementos estabelecida no Sistema – 2, resulta
na menor propagação de erro e no menor tempo de processamento.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 20
GRAFO
EXERCÍCIO - 01
Rotular os vértices do grafo dado pela representação geométrica a seguir.
Grafo rotulado
x1 x2 x3 x4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 21
GRAFO
EXERCÍCIO - 02
Construir a matiz incidência do grafo rotulado do EXERCÍCIO – 01.
x1 x2 x3 x4
4321 xxxx
1x 0011
2
1
x
x
1110
0111
4
3
x
x
1100
1110
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 22
GRAFO
EXERCÍCIO - 03
Construir, em forma de tabela, o grafo rotulado do EXERCÍCIO – 01.
x1 x2 x3 x4
Vértices
Arestas
Vértices
Arestas
x3 x3
es s
De Para
a33x1 x1 a11
es s
De Para
3 3
x3 x4
33
a34a12
1 1
x1 x2
11
x4 x4 a44x2 x2
x3 x2
a22
a32
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 23
3 2 32
GRAFO
EXERCÍCIO - 04
Construir, em forma gráfica, o grafo valorado definido na tabela do
Í
Vértices
Arestas
Vértices
Arestas
EXERCÍCIO – 03.
x3 x3
Arestas
De Para
a33x1 x1 a11
Arestas
De Para
x3 x3
x3 x4
a33
a34a12
x1 x1
x1 x2
a11
x4 x4 a44x2 x2
x3 x2
a22
a32x3 x2 a32
a12 = a21 a23 = a32 a34 = a43a12 a21 x1 x2
a23 a32 x3
a34 a43 x4
a11 a22 a33 a44
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 24
GRAFO
EXERCÍCIO - 05
Incluir, as condições de operação, no sistema definido pelo grafo obtido no
ÍEXERCÍCIO – 04.
a12 = a21 x1 x2
a23 = a32 x3
a34 = a43 x41 2 3 4
a11 a22 a33 a44
b1 b2 b
3
b4
a12 = a21 a23 = a32 a34 = a433a12 a21 x1 x2
a23 a32 x3
a34 a43 x4
a11 a22 a33 a44
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 25
GRAFO
EXERCÍCIO - 06
Elaborar um sistema de equações lineares que possa ser representado pelo
Íseguinte grafo obtido no EXERCÍCIO – 05.
b1 b2 b
3
b4
a12 = a21 a23 = a32 a34 = a43312 21 x1 x2
23 32 x3
34 43 x4
a11 a22 a33 a44
232221
1211
0
00
aaa
aa
2
1
x
x
2
1
b
b
4443
343332
00
0
aa
aaa
4
3
x
x
=
4
3
b
b
.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 26
GRAFO
EXERCÍCIO - 07
Rotular os vértices do grafo dado pela representação geométrica a seguir.
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 27
GRAFO
EXERCÍCIO - 07
Grafo rotulado
x1,1 x1,2 x1,3 x1,4
x2,1 x2,2 x2,3 x2,4
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 28
GRAFO
EXERCÍCIO - 08
Construir a matiz incidência do grafo rotulado do EXERCÍCIO – 07.
x1,1 x1,2 x1,3 x1,4
x2,1 x2,2 x2,3 x2,4
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 29
GRAFO
EXERCÍCIO – 08-A (Organizado por linha)
321
4,33,32,31,34,23,22,21,24,13,12,11,1
432143214321
xxxxxxxxxxxx
2,1
1,1
3
2
1
1
x
x
000001001110
000000100111
000000010011
12
4,1
3,1
1
4
3
xx
x
000100110001
000010001100
000001001110
3,2
2,2
1,2
3
2
2
x
x
010011100100
001001110010
1,3
4,2
2
1
4
x
x
x
011100100000
001100010000
100011001000
4,3
3,3
2,3
4
3
2
3
x
x
x
110010000000
111001000000
011100100000
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 30
4,3
GRAFO
4321
EXERCÍCIO – 08-B (Organizado por coluna)
4,34,24,13,33,23,12,32,22,11,31,21,1
321321321321
xxxxxxxxxxxx
1,2
1,1
3
2
1
1 x
x
000000100110
000000010111
000000001011
22
2,1
1,3
2
1
2
3
x
x
x
000010111010
000001011001
000000100110
3,1
2,3
2,2
1
3
x
x
001011001000
000100110100
41
3,3
3,2
1
3
23
x
x
x
011001000000
100110100000
010111010000
4,3
4,2
4,1
3
2
1
4
x
x
x
110100000000
111010000000
011001000000
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 31
,
GRAFO
EXERCÍCIO - 09
Construir, em forma de tabela, o grafo rotulado do EXERCÍCIO – 07.
x1,1 x1,2 x1,3 x1,4
x2,1 x2,2 x2,3 x2,4
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 32
GRAFO
EXERCÍCIO - 09
Vértices
A t
Vértices
A t
Vértices
A t
x1 1 x1 1 a1111
Arestas
De Para
Arestas
De Para
a2212x2 2 x1 2
Arestas
De Para
x3 1 x2 1 a3121
a1112
x1,1 x1,1
x1,1 x1,2
x x
a1111
a
a2212x2,2 x1,2
x2,2 x2,1
x x
a2221
a
x3,1 x2,1
x3,1 x3,1
a3121
a3131
x x ax1,1 x2,1
x1,2 x1,2
a1121
a1212
x2,2 x2,2 a2222
x2,2 x2,3 a2223
x3,1 x3,2
x3,2 x3,2
a3132
a3232
x1,3 x1,2
x1,3 x1,3
a1312
a1313
x2,2 x3,2
x2,3 x2,3
a2232
a2323
x3,3 x2,3
x3,3 x3,2
a3323
a3332
x1,3 x1,4
x1,3 x2,3
a1314
a1323
x2,4 x1,4
x2,4 x2,3
a2414
a2423
x3,3 x3,3 a3333
x3,3 x3,4 a3334
x1,4 x1,4 a1414
x2 1 x2 1 a2121 a2434x2 4 x3 4
x2,4 x2,4 a2424 x3,4 x3,4 a3434
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 33
2,1 2,1 2121 24342,4 3,4
GRAFO
EXERCÍCIO - 10
Construir, em forma gráfica, o grafo valorado definido na tabela do
ÍEXERCÍCIO – 09.
Vértices
Arestas
D P
Vértices
Arestas
D P
Vértices
Arestas
D P
x1,1 x1,1 a1111
De Para De Para
a2212x2,2 x1,2
De Para
x3,1 x2,1 a3121
a1112x1,1 x1,2
x1,1 x2,1
x x
a1121
a
x2,2 x2,1
x2,2 x2,2
a2221
a2222
x x a
x3,1 x3,1 a3131
x3,1 x3,2
x x
a3132
ax1,2 x1,2 a1212
x1,3 x1,2
x x
a1312
a
x2,2 x2,3
x2,2 x3,2
x x
a2223
a2232
a
x3,2 x3,2
x3,3 x2,3
x x
a3232
a3323
ax1,3 x1,3
x1,3 x1,4
x1 3 x2 3
a1313
a1314
a1323
x2,3 x2,3
x2,4 x1,4
x2 4 x2 3
a2323
a2414
a2423
x3,3 x3,2
x3,3 x3,3
a3332
a3333
x3 3 x3 4 a3334x1,3 x2,3
x1,4 x1,4
a1323
a1414
x2 1 x2 1 a2121
x2,4 x2,3 a2423
a2434x2 4 x3 4
x2,4 x2,4 a2424
x3,3 x3,4 a3334
x3,4 x3,4 a3434
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 34
2,1 2,1 2121 24342,4 3,4
GRAFO
EXERCÍCIO - 10
Grafo valorado, no caso de substituição das incógnitas por valores numéricos.
a1112 = a1211 a1213 = a1312 a1314 = a1413
a1111 a1212 a1313 a1414
a1121 = a2111 a1222 = a2212 a1323 = a2313 a1424 = a2414 
a1112 a1211 a1213 a1312 a1314 a1413 
x1,1 x1,2 x1,3 x1,4
a2121 a2222 a2323 a2424
a2122 = a2221 a2223 = a2322 a2324 = a2423 
x2,1 x2,2 x2,3 x2,4
a2131 = a3121 a2232 = a3222 a2333 = a3323 a2434 = a3424 
a2121 a2222 a2323 a2424
a3131 a3232 a3333 a3434
a3132 = a3231 a3233 = a3332 a3334 = a3433 
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 35
GRAFO
EXERCÍCIO - 11
Incluir, as condições de operação, no sistema definido pelo grafo obtido no
ÍEXERCÍCIO – 10.
a1112 = a1211 a1213 = a1312 a1314 = a1413
a1111 a1212 a1313 a1414
a1121 = a2111 a1222 = a2212 a1323 = a2313 a1424 = a2414 
a1112 a1211 a1213 a1312 a1314 a1413 
x1,1 x1,2 x1,3 x1,4
a2121 a2222 a2323 a2424
a2122 = a2221 a2223 = a2322 a2324 = a2423 
x2,1 x2,2 x2,3 x2,4
a2131 = a3121 a2232 = a3222 a2333 = a3323 a2434 = a3424 
a2121 a2222 a2323 a2424
a3131 a3232 a3333 a3434
a3132 = a3231 a3233 = a3332 a3334 = a3433 
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 36
GRAFO
Rotulando as ligações
EXERCÍCIO - 11
a1112 = a1211 a1213 = a1312 a1314 = a1413
b11 b12 b14a1111 a1212 a1313 a1414
b13
a1121 = a2111 a1222 = a2212 a1323 = a2313 a1424 = a2414 
a1112 a1211 a1213 a1312 a1314 a1413 
x1,1 x1,2 x1,3 x1,4
b23b21 b22 b24a2121 a2222 a2323 a2424
a2122 = a2221 a2223 = a2322 a2324 = a2423 
x2,1 x2,2 x2,3 x2,4
a2131 = a3121 a2232 = a3222 a2333 = a3323 a2434 = a3424 
b23b21 b22 b24a2121 a2222 a2323 a2424
b31 b32 b34b33a3131 a3232 a3333 a3434
a3132 = a3231 a3233 = a3332 a3334 = a3433 
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 37
GRAFO
EXERCÍCIO - 12
Elaborar um sistema de equações lineares que possa ser representado pelo
Íseguinte grafo obtido no EXERCÍCIO – 11.
a1112 = a1211 a1213 = a1312 a1314 = a1413
b11 b12 b14a1111 a1212 a1313 a1414b13a1112 = a1211 a1213 = a1312 a1314 = a1413
b11 b12 b14a1111 a1212 a1313 a1414
b13
a1121 = a2111 a1222 = a2212 a1323 = a2313 a1424 = a2414 
a1112 a1211 a1213 a1312 a1314 a1413 
x1,1 x1,2 x1,3 x1,4
a1121 = a2111 a1222 = a2212 a1323 = a2313 a1424 = a2414 
a1112 a1211 a1213 a1312 a1314 a1413 
x1,1 x1,2 x1,3 x1,4
b23b21 b22 b24a2121 a2222 a2323 a2424
a2122 = a2221 a2223 = a2322 a2324 = a2423 
x2,1 x2,2 x2,3 x2,4
b23b21 b22 b24a2121 a2222 a2323 a2424
a2122 = a2221 a2223 = a2322 a2324 = a2423 
x2,1 x2,2 x2,3 x2,4
a2131 = a3121 a2232 = a3222 a2333 = a3323 a2434 = a3424 
b23b21 b22 b24a2121 a2222 a2323 a2424
a2131 = a3121 a2232 = a3222 a2333 = a3323 a2434 = a3424 
b23b21 b22 b24a2121 a2222 a2323 a2424
b31 b32 b34b33a3131 a3232 a3333 a3434
a3132 = a3231 a3233 = a3332 a3334 = a3433 
x3,1 x3,2 x3,3 x3,4
b31 b32 b34b33a3131 a3232 a3333 a3434
a3132 = a3231 a3233 = a3332 a3334 = a3433 
x3,1 x3,2 x3,3 x3,4
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 38
GRAFO
EXERCÍCIO 12 A (organizado por linha)
Escrevendo as equações
EXERCÍCIO – 12-A (organizado por linha)
11x
2li htR l ã1li hdó iR l ã
14
13
12
x
x
x
= 12
11
b
b
b
.Equações da linha - 1
444 8444 76 2linhaaparamutuaRelação444 8444 76 1linhadaprópriaRelação
1222121312121211
112111121111
0000
0000
00000
aaaa
aaa
24
23
22
21
x
x
x
x
14
13
b
bq ç
142414141413
1323131413131312
00000
0000
aaa
aaaa
12
11
x
x
24
21
14
13
x
x
x
x
21
b
b
444 8444 76 3linhaaparamutuaRelação444 8444 76 2linhadaprópriaRelação444 8444 76 1linhaaparamutuaRelação
2131212221212111
0000000
00000000
aaaaa
aaaa
31
24
23
22
x
x
x
x =
24
23
22
b
b
b.Equações da linha - 2
2434242424232414
23332324232323222313
22322223222222212211
00000000
0000000
0000000
aaaa
aaaaa
aaaaa
21x
34
33
32
x
x
x
24
23
22
21
x
x
x
x
= 12
11
b
b
.Equações da linha 3
444 8444 76 3linhadaprópriaRelação444 8444 76 2linhaaparamutuaRelação
3233323232313222
313231313121
0000
00000
aaaa
aaa
33
32
31
x
x
x
x
=
14
13
b
bEquações da linha - 3
343434333424
3334333333323323
00000
0000
aaa
aaaa
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 39
34x
GRAFO
EXERCÍCIO 12 A (organizado por linha)
Resultado
EXERCÍCIO – 12-A (organizado por linha)
112111121111
00000000
000000000
aaaa
aaa 11
x
x 11
b
b
142414141413
1323131413131312
1222121312121211
000000000
00000000
00000000
aaa
aaaa
aaaa
14
13
12
x
x
x
14
13
12
b
b
b
2232222322222221221
213121222121211
142414141413
000000000000000
000000000
aaaaa
aaaa
aaa
22
21
14
x
x
x
22
21
14
b
b
b
243424242423241
2332232423232322231
33
00000000
0000000
aaaa
aaaaa
24
23
x
x
=
24
23
b
b
.
323332323231322
31323131312
00000000
00000000
000000000
aaaa
aaa
32
31
x
x
32
31
b
b
b
34343433342
333433333332332
000000000
00000000
aaa
aaaa
34
33
x
x
34
33
b
b
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 40
GRAFO
EXERCÍCIO 12 B (organizado por coluna)
Escrevendo as equações
EXERCÍCIO – 12-B (organizado por coluna)
2colunaaparamutuaRelação1colunadaprópriaRelação
Equações da coluna - 1
12
31
21
11
x
x
x
x
= 21
11
b
b
b.
444 8444 76 2colunaaparamutuaRelação444 8444 76 1colunadaprópriaRelação
2122213121212111
111211211111
000
00
000
aaaa
aaa
31
21
11
x
x
x
b
444 8444 76 3colunaaparamutuaRelação444 8444 76 2colunadaprópriaRelação444 8444 76 1colunaaparamutuaRelação
00000
32
22
x
x 31b313231313121 000 aaa
Equações da coluna - 2
23
13
32
22
12
x
x
x
x
x
=
32
22
12
b
b
b.
3233323232223231
22232232222222122221
1213122212121211
00000
0000
00000
aaaa
aaaaa
aaaa
33
23
x
x
13
32
22
12
x
x
x
x
13b
444 8444 76 4colunaaparamutuaRelação444 8444 76 3colunadaprópriaRelação444 8444 76 2colunaaparamutuaRelação
1213122212121211 00000 aaaa
Equações da coluna - 3
34
24
14
33
23
x
x
x
x
x =
33
23
b
b.
3233323232223231
22232232222222122221
00000
0000
aaaa
aaaaa
x444 8444 76 4colunadaprópriaRelação444 8444 76 3colunaaparamutuaRelação
Equações da coluna - 4
34
42
41
33
23
13
x
x
x
x
x
=
34
24
14
b
b
b
8686
434343424333
4243424242414232
414241414131
000
00
000
aaa
aaaa
aaa .
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 41
43x
GRAFO
EXERCÍCIO 12 B (organizado por coluna)
Resultado
EXERCÍCIO – 12-B (organizado por coluna)
112111211111
00000000
000000000
aaaa
aaa 11
x
x 11
b
b
1213122212121211
313231313121
2122213121212111
00000000
000000000
00000000
aaaa
aaa
aaaa
12
31
21
x
x
x
12
31
21
b
b
b
3233323232223231
22232232222222122221
1213122212121211
00000000
0000000
00000000
aaaa
aaaaa
aaaa
32
22
12
x
x
x
32
22
12
b
b
b
23242333232323132322
1314132313131312
3 333 333 3
0000000
00000000
aaaaa
aaaa
23
13
x
x
=
23
13
3
b
b
.
142414141413
3334313333233332
00000000
000000000
00000000
aaa
aaaa
14
33
x
x
14
33
b
b
b
343434243433
2434242424142423
000000000
00000000
aaa
aaaa
34
24
x
x
34
24
b
b
COMPUTAÇÃO NA ENGENHARIA QUÍMICA - EQ 246PhDs 42