# Chapter7-Graph theory¶

## Ex7-pg7.18¶

In [1]:
## Graph Theory : example 7.7 : (pg 7.18 & 7.19)
import numpy

##Complete incidence matrix Aa
print("\nAa=");
print numpy.matrix([[1, 0 ,0 ,-1 ,1 ,0 ,0 ,0],[-1, 1, 0 ,0 ,0 ,1 ,0 ,0],[0 ,-1 ,1 ,0 ,0 ,0 ,1 ,0],[0, 0 ,-1, 1 ,0 ,0 ,0, 1],[0 ,0 ,0 ,0 ,-1, -1 ,-1, -1]]);
##eliminating last row from Aa
print("\nA=");
print numpy.matrix([[1, 0 ,0 ,-1, 1 ,0 ,0 ,0],[-1, 1 ,0 ,0 ,0 ,1 ,0 ,0],[0 ,-1, 1, 0, 0 ,0 ,1 ,0],[0, 0, -1, 1 ,0 ,0 ,0 ,1]]);
##Tieset matrix B
print("\ntwigs={1,3,5,7} \nlinks={2,4,6,8} \ntieset 2={2,7,5,1} \ntieset 4={4,5,7,3} \ntieset 6={6,5,1} \ntieset 8={8,7,3}");
## forward direction = 1, reverse direction = -1
print("\nB=");
print numpy.matrix([[1, 1 ,0 ,0 ,-1, 0, 1, 1],[0, 0, 1 ,1 ,1 ,0, -1, 0],[1, 0 ,0 ,0 ,-1, 1, 0, 0],[0, 0 ,1 ,0 ,0 ,0 ,-1, 1]]);
## f-cutset matrix Q
print("\nf-cutset 1={1,6,2} \nf-cutset 3={3,4,8} \nf-cutset 5={5,4,6,2} \nf-cutset 7={7,2,8,4}");
print("\nQ=");
print numpy.matrix([[1 ,-1, 0, 0, 0 ,-1, 0, 0],[0 ,0, 1, -1, 0, 0 ,0 ,-1],[0, 1, 0 ,-1, 1, 1, 0, 0],[0 ,-1, 0, 1, 0 ,0, 1, 1]]);

Aa=
[[ 1  0  0 -1  1  0  0  0]
[-1  1  0  0  0  1  0  0]
[ 0 -1  1  0  0  0  1  0]
[ 0  0 -1  1  0  0  0  1]
[ 0  0  0  0 -1 -1 -1 -1]]

A=
[[ 1  0  0 -1  1  0  0  0]
[-1  1  0  0  0  1  0  0]
[ 0 -1  1  0  0  0  1  0]
[ 0  0 -1  1  0  0  0  1]]

twigs={1,3,5,7}
tieset 2={2,7,5,1}
tieset 4={4,5,7,3}
tieset 6={6,5,1}
tieset 8={8,7,3}

B=
[[ 1  1  0  0 -1  0  1  1]
[ 0  0  1  1  1  0 -1  0]
[ 1  0  0  0 -1  1  0  0]
[ 0  0  1  0  0  0 -1  1]]

f-cutset 1={1,6,2}
f-cutset 3={3,4,8}
f-cutset 5={5,4,6,2}
f-cutset 7={7,2,8,4}

Q=
[[ 1 -1  0  0  0 -1  0  0]
[ 0  0  1 -1  0  0  0 -1]
[ 0  1  0 -1  1  1  0  0]
[ 0 -1  0  1  0  0  1  1]]


## Ex8-pg7.19¶

In [5]:
## Graph Theory : example 7.8 :(pg 7.19 & 7.20)
##Complete Incidence Matrix Aa
import numpy
from numpy import linalg
print("\nAa=");
import numpy
print numpy.matrix([[1 ,0 ,-1 ,1],[-1, 1 ,0 ,0],[0 ,-1 ,1 ,-1]]);
## Reduced Incidence matrix A  (by eliminating last row from Aa)
A=numpy.matrix([[1 ,0, -1, 1],[-1, 1 ,0 ,0]]);
print("\nA=");
print numpy.matrix([[1 ,0 ,-1 ,1],[-1, 1 ,0 ,0]]);
A1=numpy.matrix([[1 ],[0], [-1], [1],[-1], [1] ,[0] ,[0]]);
print("A1")

print("\nNumber of possible trees=");##A^T=A'= transpose of A
x=(A*numpy.matrix.transpose(A));
print (x);
alp = numpy.linalg.det(x);

print(alp)

Aa=
[[ 1  0 -1  1]
[-1  1  0  0]
[ 0 -1  1 -1]]

A=
[[ 1  0 -1  1]
[-1  1  0  0]]
A1

Number of possible trees=
[[ 3 -1]
[-1  2]]
5.0


## Ex11-pg7.21¶

In [4]:
# Graph Theory : example 7.11 :(pg 7.21 & 7.22)
import numpy
from numpy import linalg
print ("Aa=[0 -1 1 0 0;0 0 -1 -1 -1;-1 0 0 0 1;1 1 0 1 0]");#Complete incidence matrix
A=numpy.matrix([[0, -1, 1, 0, 0],[0, 0, -1, -1, -1],[-1, 0, 0, 0, 1]]);#Reduced incidence matrix
print("\nNumber of possible trees = |A*A^T|");#A^T=A'=transpose of A
x=(A*numpy.matrix.transpose(A));
print (x);
alp = numpy.linalg.det(x);
print("\n|A*A^T|= ",round(alp));#No. of possible trees
#Tieset Matrix B
print("\ntwigs={3,4,5} \nlinks={1,2} \ntieset 1={1,4,5} \ntieset 2={2,3,4}");
print ("B=[1 0 0 -1 1;0 1 1 -1 0]");
#f-cutset Matrix Q
print("\nf-cutset 3={3,2} \nf-cutset 4={4,2,1} \nf-cutset 5={5,1}");
print ("Q=[0 -1 1 0 0;1 1 0 1 0;-1 0 0 0 1]");

Aa=[0 -1 1 0 0;0 0 -1 -1 -1;-1 0 0 0 1;1 1 0 1 0]

Number of possible trees = |A*A^T|
[[ 2 -1  0]
[-1  3 -1]
[ 0 -1  2]]
('\n|A*A^T|= ', 8.0)

twigs={3,4,5}
tieset 1={1,4,5}
tieset 2={2,3,4}
B=[1 0 0 -1 1;0 1 1 -1 0]

f-cutset 3={3,2}
f-cutset 4={4,2,1}
f-cutset 5={5,1}
Q=[0 -1 1 0 0;1 1 0 1 0;-1 0 0 0 1]


## Ex14-pg7.27¶

In [6]:
##Graph Theory : example 7.14 :(pg 7.37 & 7.38)
##Tieset Matrix B
import numpy
import numpy
from numpy import linalg
print("\ntieset1={1,4,5} \ntieset2={2,4,6} \ntieset={3,5,6} \nB=");
B=numpy.matrix([[1, 0 ,0 ,1 ,1 ,0],[0 ,1 ,0 ,-1, 0, -1],[0, 0 ,1 ,0 ,-1, 1]]);
print(B);
print("\nThe KVL equation in matrix form \nB.Zb.(B^T).Il = B.Vs-B.Zb.Is");
print("\nB.Zb.(B^T).Il = B.Vs \nZb=");##Is=0
import numpy as np
Zb = np.array([1,1,1,2,2,2])
d = np.diag(Zb)
print(d)

print("\n(B^T)=");
Z= numpy.matrix.transpose(B)
print(Z)
Vs=numpy.matrix([[2],[0],[0],[0],[0],[0]]);
print("\nVs=");
print(Vs);
print("\nB.Zb =");
x=numpy.dot(B,Zb);
print(x);

print("\nB.Vs=");
z=numpy.dot(B,Vs);
print(z);
M=numpy.matrix([[5, -2 ,-2],[-2 ,5 ,-2],[-2, -2, 5]]);
H=numpy.linalg.inv(M);
N=([[2],[0],[0]]);
X=numpy.dot(H,N);
print(X);
print("\nIl1=0.857 A \nIl2=0.571 A \nIl3=0.571 A");
print("\nBranch currents:");
P=(Z,X);
print(P);##Currents in amperes

tieset1={1,4,5}
tieset2={2,4,6}
tieset={3,5,6}
B=
[[ 1  0  0  1  1  0]
[ 0  1  0 -1  0 -1]
[ 0  0  1  0 -1  1]]

The KVL equation in matrix form
B.Zb.(B^T).Il = B.Vs-B.Zb.Is

B.Zb.(B^T).Il = B.Vs
Zb=
[[1 0 0 0 0 0]
[0 1 0 0 0 0]
[0 0 1 0 0 0]
[0 0 0 2 0 0]
[0 0 0 0 2 0]
[0 0 0 0 0 2]]

(B^T)=
[[ 1  0  0]
[ 0  1  0]
[ 0  0  1]
[ 1 -1  0]
[ 1  0 -1]
[ 0 -1  1]]

Vs=
[[2]
[0]
[0]
[0]
[0]
[0]]

B.Zb =
[[ 5 -3  1]]

B.Vs=
[[2]
[0]
[0]]

[[ 0.85714286]
[ 0.57142857]
[ 0.57142857]]

Il1=0.857 A
Il2=0.571 A
Il3=0.571 A

Branch currents:
(matrix([[ 1,  0,  0],
[ 0,  1,  0],
[ 0,  0,  1],
[ 1, -1,  0],
[ 1,  0, -1],
[ 0, -1,  1]]), matrix([[ 0.85714286],
[ 0.57142857],
[ 0.57142857]]))


## Ex15-pg7.28¶

In [7]:
##Graph Theory : example 7.15 :(pg 7.38 & 7.39)
##Tieset Matrix B
import numpy
import numpy
from numpy import linalg
print("\ntieset1={1,4,6} \ntieset2={2,5,6} \ntieset={3,5,4} \nB=");
B=numpy.matrix([[1, 0 ,0 ,1 ,0 ,1],[0, 1, 0, 0, 1 ,-1],[0 ,0 ,1 ,-1 ,-1 ,0]]);
print(B);
print("\nThe KVL equation in matrix form \nB.Zb.(B^T).Il = B.Vs-B.Zb.Is");
print("\nB.Zb.(B^T).Il = B.Vs \nZb=");##Is=0
Zb = numpy.array([6,4,3,4,6,2])
d = numpy.diag(Zb)
print(d)
XY=numpy.matrix.transpose(B)
print("\n(B^T)=");
print(XY);
Vs=([[12],[-6],[-8],[0],[0],[0]]);
print("\nVs=");
print(Vs);
print("\nB.Zb=");
x=numpy.dot(B,Zb);
print(x);
print("\nB.Zb.(B^T)=");
#y=numpy.dot(XY,x);
#print(y);
print("\nB.Vs=");
z=numpy.dot(B,Vs);
print(z);
M=numpy.matrix([[12 ,-2 ,-4],[-2, 12, -6],[-4, -6, 12]]);
H=numpy.linalg.inv(M);
N=([[12],[-6],[-8]]);
X=numpy.dot(H,N);
print(X);
print("\nIl1=0.55 A \nIl2=-0.866 A \nIl3=-0.916 A");

tieset1={1,4,6}
tieset2={2,5,6}
tieset={3,5,4}
B=
[[ 1  0  0  1  0  1]
[ 0  1  0  0  1 -1]
[ 0  0  1 -1 -1  0]]

The KVL equation in matrix form
B.Zb.(B^T).Il = B.Vs-B.Zb.Is

B.Zb.(B^T).Il = B.Vs
Zb=
[[6 0 0 0 0 0]
[0 4 0 0 0 0]
[0 0 3 0 0 0]
[0 0 0 4 0 0]
[0 0 0 0 6 0]
[0 0 0 0 0 2]]

(B^T)=
[[ 1  0  0]
[ 0  1  0]
[ 0  0  1]
[ 1  0 -1]
[ 0  1 -1]
[ 1 -1  0]]

Vs=
[[12], [-6], [-8], [0], [0], [0]]

B.Zb=
[[12  8 -7]]

B.Zb.(B^T)=

B.Vs=
[[12]
[-6]
[-8]]

[[ 0.55      ]
[-0.86666667]
[-0.91666667]]

Il1=0.55 A
Il2=-0.866 A
Il3=-0.916 A


## Ex19-pg7.34¶

In [12]:
##Graph Theory : example 7.19
import math
import numpy
from numpy import linalg
Q=numpy.matrix([[1, -1, 0, 0],[0 ,-1 ,1 ,1]]);
print("\nQ=");
print(Q);
print("\nThe KCL equation in matrix form is given by");
print("\nQ.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs");
print("\nQ.Yb.(Q^T).Vl=Q.Is");##Vs=0
Yb=numpy.array([5,5,5,10]);
d=numpy.diag(Yb)
Is=numpy.matrix([[-10],[0],[0],[0]]);
print("\nYb=");
print(d);
print("\n(Q^T)=");
ZZ=numpy.matrix.transpose(Q)
print(ZZ);
print("\nIs=");
print(Is);##current entering into nodes is taken as negative
x=numpy.dot(Q,Yb);
print("\nQ.Yb=");
print(x);
#y=numpy.dot(x[0],ZZ);
print("\nQ.Yb.(Q^T)=");
#print(y);
z=numpy.dot(Q,Is);
print("\nQ.Is=");
print(z);
M=numpy.matrix([[10, 5],[5, 20]]);
P=numpy.linalg.inv(M);
N=numpy.matrix([[-10],[0]]);
X=numpy.dot(P,N);
print(X);
print("\nvl1=-1.14 V \nvl2=0.28 V");

Q=
[[ 1 -1  0  0]
[ 0 -1  1  1]]

The KCL equation in matrix form is given by

Q.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs

Q.Yb.(Q^T).Vl=Q.Is

Yb=
[[ 5  0  0  0]
[ 0  5  0  0]
[ 0  0  5  0]
[ 0  0  0 10]]

(Q^T)=
[[ 1  0]
[-1 -1]
[ 0  1]
[ 0  1]]

Is=
[[-10]
[  0]
[  0]
[  0]]

Q.Yb=
[[ 0 10]]

Q.Yb.(Q^T)=

Q.Is=
[[-10]
[  0]]

[[-1.14285714]
[ 0.28571429]]

vl1=-1.14 V
vl2=0.28 V


## Ex20-pg7.35¶

In [9]:
##Graph Theory : example 7.20 :(pg 7.35 & 7.36)
import numpy
from numpy import linalg
print("\nf-cutset1={1,4,5,6} \nf-cutset2={2,4,5} \nf-cutset3={3,4,6}");
Q=numpy.matrix([[1, 0 ,0 ,-1, -1, 1],[0 ,1 ,0 ,-1, -1 ,0],[0 ,0, 1, -1 ,0 ,1]]);
print("\nQ=");
print(Q);
print("\nThe KCL equation in matrix form is given by");
print("\nQ.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs");
print("\nQ.Yb.(Q^T).Vl=Q.Is");##Is=0
Yb=numpy.array([0.2,0.2,0.2,0.1,0.5,0.1]);
yz=numpy.diag(Yb)
Vs=numpy.matrix([[910],[0],[0],[0],[0],[0]]);
Is=numpy.matrix([[0],[0],[0],[0],[0],[0]]);
print("\nyz=");
print(yz);
print("\nVs=");
print(Vs);
print("\nIs=");
print(Is);
x=numpy.dot(Q,yz);
print("\nQ.Yb=");
print(x);
z=numpy.dot(x,Vs);
print("\nQ.Yb.Vs=");
print(z);
print("\nQ.Is=");
u=numpy.dot(Q,Is);
print(u);
v=(u-z);
print("\nQ.Is-Q.Yb.Vs=");
print(v);
M=([[0.9, 0.6, 0.2],[0.6, 0.8, 0.1],[0.2 ,0.1 ,0.3]]);
P=numpy.linalg.inv(M);
N=([[-182],[0],[0]]);
X=numpy.dot(P,N);
print(X);
print("\nvl1=-460 V \nvl2=320 V \nvl3=200 V");

f-cutset1={1,4,5,6}
f-cutset2={2,4,5}
f-cutset3={3,4,6}

Q=
[[ 1  0  0 -1 -1  1]
[ 0  1  0 -1 -1  0]
[ 0  0  1 -1  0  1]]

The KCL equation in matrix form is given by

Q.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs

Q.Yb.(Q^T).Vl=Q.Is

yz=
[[ 0.2  0.   0.   0.   0.   0. ]
[ 0.   0.2  0.   0.   0.   0. ]
[ 0.   0.   0.2  0.   0.   0. ]
[ 0.   0.   0.   0.1  0.   0. ]
[ 0.   0.   0.   0.   0.5  0. ]
[ 0.   0.   0.   0.   0.   0.1]]

Vs=
[[910]
[  0]
[  0]
[  0]
[  0]
[  0]]

Is=
[[0]
[0]
[0]
[0]
[0]
[0]]

Q.Yb=
[[ 0.2  0.   0.  -0.1 -0.5  0.1]
[ 0.   0.2  0.  -0.1 -0.5  0. ]
[ 0.   0.   0.2 -0.1  0.   0.1]]

Q.Yb.Vs=
[[ 182.]
[   0.]
[   0.]]

Q.Is=
[[0]
[0]
[0]]

Q.Is-Q.Yb.Vs=
[[-182.]
[   0.]
[   0.]]

[[-460.]
[ 320.]
[ 200.]]

vl1=-460 V
vl2=320 V
vl3=200 V


## Ex21-pg7.36¶

In [11]:
##Graph Theory : example 7.21 :(pg 7.38 & 7.39)
import numpy
from numpy import linalg
print("\ntwigs={1,2} \nf-cutset1={1,4} \nf-cutset2={2,3}");
Q=numpy.matrix([[1, 0, 0 ,-1],[0 ,1 ,-1, 0]]);
print("\nQ=");
print(Q);
print("\nThe KCL equation in matrix form is given by");
print("\nQ.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs");
ZZ=numpy.matrix.transpose(Q)

yxx=numpy.array([0.25,0.5,0.25,0.5]);
Yb=numpy.diag(yxx)
Vs=numpy.matrix([[1],[1],[0],[0]]);
Is=numpy.matrix([[0],[0],[0.5],[-0.5]]);
print("\nYb=");
print(Yb);
print("\n(Q^T)=");
print(ZZ);
print("\nVs=");
print(Vs);
print("\nIs=");
print(Is);
x=numpy.dot(Q,Yb);
print("\nQ.Yb=");
print(x);
y=numpy.dot(x,ZZ);
print("\nQ.Yb.(Q^T)=");
print(y);
print("\nQ.Is=");
u=numpy.dot(Q,Is);
print(Q*Is);
z=numpy.dot(x,Vs);
print("\nQ.Yb.Vs=");
print(z);
v=(u-z);
print("\nQ.Is-Q.Yb.Vs=");
print(v);
M=([[0.75, 0],[0 ,0.75]]);
P=numpy.linalg.inv(M);
N=([[0.25],[-1]]);
X=numpy.dot(P,N);
print(X);
print("\nvl1=0.33 V \nvl2=-1.33 V");
vl2=-1.33;
v=1.+vl2;
print"%s %.2f %s"%("\nV=",v,"");

twigs={1,2}
f-cutset1={1,4}
f-cutset2={2,3}

Q=
[[ 1  0  0 -1]
[ 0  1 -1  0]]

The KCL equation in matrix form is given by

Q.Yb.(Q^T).Vl=Q.Is-Q.Yb.Vs

Yb=
[[ 0.25  0.    0.    0.  ]
[ 0.    0.5   0.    0.  ]
[ 0.    0.    0.25  0.  ]
[ 0.    0.    0.    0.5 ]]

(Q^T)=
[[ 1  0]
[ 0  1]
[ 0 -1]
[-1  0]]

Vs=
[[1]
[1]
[0]
[0]]

Is=
[[ 0. ]
[ 0. ]
[ 0.5]
[-0.5]]

Q.Yb=
[[ 0.25  0.    0.   -0.5 ]
[ 0.    0.5  -0.25  0.  ]]

Q.Yb.(Q^T)=
[[ 0.75  0.  ]
[ 0.    0.75]]

Q.Is=
[[ 0.5]
[-0.5]]

Q.Yb.Vs=
[[ 0.25]
[ 0.5 ]]

Q.Is-Q.Yb.Vs=
[[ 0.25]
[-1.  ]]