Application: directed graphs123412 3 45• Graphs appear in network analysis(e.g. internet) or circuit analysis.• arrow indicates direction of flow• no edges from a node to itself• at most o ne edge between nodesDefinition 1. Let G be a graph with m edges and n n odes.The edge-node incident matrix ofG i s the m × n matrix A withAi,j=−1, if edge i leaves node j,+1, if edge i enter s node j,0, otherwise.Example 2. Give th e edge - n ode i ncidence matrix of our graph.Solution.Meaning of the null spaceThex in Ax is assigning values to ea c h node.You may think of assigning potentials to each node.0 =−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1x1x2x3x4=So: Ax = 0Armin [email protected] our graph: N u l(A) is span ned byThis always happens as long as the graph is c onnected.Example 3. Give a basis for Nul(A) for the following graph.Solution.1234In general:dim Nul(A) isFor large graphs, disconnection may not be apparent visually.But we can always find out by computingdim Nul(A) using Gaussian elimination!Meaning of the left null spaceThey in yTA is assig n ing val ues t o 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=123412 3 45So: ATy = 0This is Kirchhoff’s first law.What is the simples t way to balance current?Armin [email protected] 4. Suppose we did not “se e ” this.Let us solveATy = 0 f or our graph:−1 −1 0 0 01 0 −1 −1 00 1 1 0 −10 0 0 1 1In general:dim Nul(AT) i sMeaning of the column space• FTLA: b is in Col(A)b is orthogonal to Nul(AT)• Just found: Nul(AT) has b asisHence,b is in Col(A) if and only ifx assigns potentials to eac h node.Then:Ax are potential differences.Ax = b is solvable if the potential differences b satisfy theconstraints coming fromNul(AT).123412 3 45So: b is in Col(A)This is Kirchhoff’s s econd law.Armin [email protected] of the row spac e• FTLA: f is in Col(AT)f is orthogonal to Nul(A)• Just found: Nul(A) has basisHence,f is in Col(AT) i f and only ify assigns cu r r ents t o each edge.Then:ATy are the net currents at each node.ATy = f is solvable if the net currents f satisfy theconstraints coming from Nul(A).123412 3 45So: f is in Col(AT)• Recall: linear dependencies among rows ! solutions to yTA = 0• Nul(AT) has basis• A subset of the rows is independen t• A subset of the rows is a basis for Col(AT)Armin [email protected] spanning tree:• includes all nodes (“spans”),• does not contain loops (“tree”).The choice to the right corresponds t ofor basis of the row space of−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1123412 3 45Euler’s formulaLet G be a connected graph.#nodes − #edges + #l oops = 1Here:123412 3 45Proof. Let A be the m × n edge-node incidence matrix of G. Armin
View Full Document
Unlocking...