DOC PREVIEW
UIUC MATH 415 - lecture22

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Review• A graph G ca n be encoded by the edge-n ode incidence matrix:123412 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 1x1x2x3x4=−x1+ x2−x1+ x3−x2+ x3−x2+ x4−x3+ x4123412 3 45So: Ax = 0nodes connected by an edge are assigned the same v a lueArmin [email protected] our graph: Nul(A) h as basis1111.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 11234In 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 1y1y2y3y4y5=− y1− y2y1− y3− y4y2+ y3− y5y4+ y5123412 3 45Armin [email protected]: ATy = 0at 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−1100and001−11are 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>RREF1 0 −1 0 10 1 1 0 −10 0 0 1 10 0 0 0 0The parametric solution isy3− y5− y3+ y5y3− y5y5.So, a basis for Nul(AT) is1−1100,−110−11.123412 3 45Observe that these two basis vectors correspond to loops.Note th at we get the “simpler” loop001−11as1−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.1234Example 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 1indeed has Nul(AT) = {0}.1234Example 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).123412 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

UIUC MATH 415 - lecture22

Documents in this Course
disc_1

disc_1

2 pages

Load more
Download lecture22
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view lecture22 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view lecture22 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?