Review• A graph G ca n be encoded by the edge-n ode incidence matrix:123412 3 45A =−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1◦ each column represents a node◦ each row represents an edge• If G has m edges and n nodes, then A is the m × n matrix withAi,j=−1, if edge i leaves node j ,+1, if edge i enters node j,0, otherwise.Meaning of t he null spaceThex in Ax is assigning value s to each node.You may think of assigning potential s to each node.−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1x1x2x3x4=−x1+ x2−x1+ x3−x2+ x3−x2+ x4−x3+ x4123412 3 45So: Ax = 0nodes connected by an edge are assigned the same v a lueArmin [email protected] our graph: Nul(A) h as basis1111.This always happens as long as the graph is connected .Example 1. Give a basis for N u l(A) for the following graph.Solution. If Ax = 0 then x1= x3(connected by edge) and x2= x4(connected by edge).Nul(A) has the basis:1010,0101.Just to make sure: the edge-node incide n c e matrix is:A =−1 0 1 00 −1 0 11234In general:dim Nul(A) is the number of connected subgr aphs.For l arge graphs, disconnection may not be apparent visually.But we can always find out by computi ngdim Nul(A) using Gaussian eliminat ion!Meaning of t he left null sp aceThe y in yTA is assigning v alues to each edge.You may think of assigning currents to each edge.A =−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1, AT=−1 −1 0 0 01 0 −1 − 1 00 1 1 0 −10 0 0 1 1−1 −1 0 0 01 0 −1 −1 00 1 1 0 −10 0 0 1 1y1y2y3y4y5=− y1− y2y1− y3− y4y2+ y3− y5y4+ y5123412 3 45Armin [email protected]: ATy = 0at each node, (directed) values assigned to edges add to zeroWhen thinking of current s, this is Kirchhoff’s first law.(at each n ode, incoming and outgoing currents balance)What is the simplest way to balance current?Assign the current in a loop!Here, we have two loops:edge1, edge3, −edge2and edge3, edge5, −edge4.Correspondingly,1−1100and001−11are in Nul(AT). Check!Example 2. Suppose we did not “se e” this.Let us solveATy = 0 for our graph :−1 −1 0 0 01 0 −1 −1 00 1 1 0 −10 0 0 1 1>RREF1 0 −1 0 10 1 1 0 −10 0 0 1 10 0 0 0 0The parametric solution isy3− y5− y3+ y5y3− y5y5.So, a basis for Nul(AT) is1−1100,−110−11.123412 3 45Observe that these two basis vectors correspond to loops.Note th at we get the “simpler” loop001−11as1−1100+−110−11.In general:dim Nul(AT) is the number of (ind ependen t) loops.For l arge graphs, we now have a nice way to computationally find all loops.Armin [email protected] ce problemsExample 3. Give a basis for N u l(AT) for th e following graph.1234Example 4. Consider the gra ph with edge-node incidence matrixA =1 −1 0 0−1 0 1 00 −1 1 00 1 0 −1.(a) Draw the corresponding directed graph with numbered e dges and nodes.(b) Give a basis for Nul(A) and Nul(AT) using properties of the graph.Armin [email protected] to practice problem sExample 5. Give a basis for N u l(AT) for th e following graph.Solution. This graph contains no loops,so Nul(AT) = {0}.Nul(AT) has the empty set as basis (no b asis vectors needed ).For comparison: the edge-node incidence mat rixA =−1 0 1 00 −1 0 1indeed has Nul(AT) = {0}.1234Example 6. Consider the graph with edge-node incidencematrixA =1 −1 0 0−1 0 1 00 −1 1 00 1 0 −1.Give a basis forNul(A) and Nul(AT).123412 3 4Solution.If Ax = 0, then x1= x2= x3= x4(all connected by edges).Nul(A) has the basis:1111.The graph is connected, so on ly 1 connected subgraph and dim Nul(A) = 1.The graph has one loop: edge1, edge2, −edge3Assign values y1= 1, y2= 1, y3= −1 along the edges of that loop.Nul(AT) has the basis:11−10.The graph has 1 loop, so dim Nul(AT) = 1.Armin
View Full Document