Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 143 views

    Linear Algebra and Graphs

    Uploaded by

    tanna88
    1. A graph can be used to model relationships between objects. It consists of vertices (nodes) connected by edges. The graphs discussed are directed graphs where each edge goes from one vertex to another. 2. A graph's incidence matrix encodes the connections between its vertices and edges. Each row corresponds to an edge and each column to a vertex. The (i,j) entry indicates whether the i-th edge contains the j-th vertex. 3. Performing elimination on a graph's incidence matrix yields a sequence of matrices corresponding to modified graphs at each step, with the final result revealing properties of the original graph connections.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Linear Algebra and Graphs

    Uploaded by

    tanna88
    143 views3 pages
    1. A graph can be used to model relationships between objects. It consists of vertices (nodes) connected by edges. The graphs discussed are directed graphs where each edge goes from one vertex to another. 2. A graph's incidence matrix encodes the connections between its vertices and edges. Each row corresponds to an edge and each column to a vertex. The (i,j) entry indicates whether the i-th edge contains the j-th vertex. 3. Performing elimination on a graph's incidence matrix yields a sequence of matrices corresponding to modified graphs at each step, with the final result revealing properties of the original graph connections.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. A graph can be used to model relationships between objects. It consists of vertices (nodes) connected by edges. The graphs discussed are directed graphs where each edge goes from one vertex to another. 2. A graph's incidence matrix encodes the connections between its vertices and edges. Each row corresponds to an edge and each column to a vertex. The (i,j) entry indicates whether the i-th edge contains the j-th vertex. 3. Performing elimination on a graph's incidence matrix yields a sequence of matrices corresponding to modified graphs at each step, with the final result revealing properties of the original graph connections.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    143 views3 pages

    Linear Algebra and Graphs

    Uploaded by

    tanna88
    1. A graph can be used to model relationships between objects. It consists of vertices (nodes) connected by edges. The graphs discussed are directed graphs where each edge goes from one vertex to another. 2. A graph's incidence matrix encodes the connections between its vertices and edges. Each row corresponds to an edge and each column to a vertex. The (i,j) entry indicates whether the i-th edge contains the j-th vertex. 3. Performing elimination on a graph's incidence matrix yields a sequence of matrices corresponding to modified graphs at each step, with the final result revealing properties of the original graph connections.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    1

    Linear Algebra and Graph Theory

    For any situation in which the pairwise connections between items


    are of interest, a graph is a suitable model: think of transportation
    networks joining cities, electrical circuitry in a computer, or social
    networks on (or off) the internet. Mathematically, a graph is a set of
    points (called nodes or vertices) and a set of edges (called edges) that
    join pairs of vertices. In a complete graph there is an edge joining every
    pair of vertices. At the other end of the spectrum are trees in which a
    particular vertex is joined to at most two others. The graphs we will
    study are directed graphs, meaning that each edge goes from one of its
    vertices to the other. In this case we represent edges by arrows. Here
    are a couple of examples.
    .
    Given a directed graph, we can associate to it an incidence matrix
    (call it A). The incidence matrix is m-by-n with m = #edges and n =
    #vertices: information about a particular vertex is contained in a row
    of the matrix, information about an edge in one of its columns. The
    (i, j) entry in the incidence matrix is given by the following formula: Figure 1: Two graphs and their inci-
     dence matrices
    0

     i f the ith edge does not contain jth vertex
    Aij = −1 i f the ith edge emanates f rom the jth vertex



    +1 i f the ith edge terminates at the jth vertex
    Since each edge has two vertices, each row of the incidence matrix
    has two nonzero entries: −1 in the column corresponding to the ver-
    tex at the tail of the arrow that represents that edge and +1 in the
    column corresponding to the vertex at the tip of the arrow represent-
    ing that edge. Note that the incidence matrix contains all the infor-
    mation there is about how the vertices of the graph are connected.
    Knowing how to process matrices, our job is to figure out what the
    processing can do to or tell about the graph.
    Observation_1 Given the graph, we can construct its incidence ma-
    trix. Once we decide which is the first vertex, which is the second,
    . . . and which edge is first, second, etc., the incidence matrix is
    unique to the graph. Construct the the incidence matrix for the
    graphs on the worksheet.

    Question: The choices are related to permutation matrices P multi-


    plying A on the left or on the right. Do you see why? What’s the
    correspondence between vertices/edges and left/right?

    Observation_2 Given the incidence matrix, we can construct the


    graph to which it belongs. The number of columns is the num-
    ber of vertices and the information in each row of the matrix al-
    lows construction of the directed edges. Thus the correspondence
    2

    between graphs and incidence matrices is exact. Construct the


    graphs associated to the incidence matrices you’ve been given.
    Illustrate the effect of a permutation on the appearance of graph 3.

    Observation_3 There’s not much to say about the rows of the inci-
    dence matrix (two nonzero entries, one −1 and one +1). Note that
    if �1 is the column vector of all ones, then A · �1 = �0 (how many
    ones in �1? how many zeros are in that zero vector?). In contrast
    to its rows, a column of the incidence matrix might have several
    nonzero entries. What does the number of +1 entries signify about
    a particular vertex? What about the number of −1 entries?

    Observation_4 How many graphs are possible given n vertices?


    Let’s stipulate that at most one directed edge can join a given pair
    of vertices. With n vertices, there are (n2 ) = 2!(nn!−2)! = 12 n(n − 1)
    possible pairs of vertices (i.e. possible edges). With respect to
    graphs, there are three possibilities for each edge:

    1. The edge is included in the graph and oriented from the smaller
    numbered vertex to the larger.

    2. The edge is included in the graph, but oriented in the opposite


    direction.

    3. The edge is not included in the graph.

    With three possibilities for each of (n2 ) edges, the number of directed
    n
    graphs with no more than one edge joining a pair of vertices is 3( 2 ) .
    At one extreme in the pantheon of graphs we have the
    complete graphs on n vertices, in which every pair of vertices is
    joined with an edge. At the other extreme, a connected graph must
    on n vertices have at least n − 1 edges as illustrated in Figure 1.
    Figure 2: A complete graph on 4 ver-
    Question: Count the net number of edges going into vertex 3 of
    tices and its incidence matrix
    the graph in figure 2. How could you count net number of edges
    going into a particular vertex (#in − #out) using a matrix multi-
    plication? Suppose you are a vertex on Facebook; what’s being
    counted here? Can you think of another setting in which the net
    number of edges into a vertex might be a useful thing to know?

    Question: Suppose you’d like to add a single edge to your graph, an


    edge that goes from one of the vertices to itself. This sort of messes
    up the incidence matrix (why?). Think of an easy � modification
    � of
    −1 1
    the graph that yields a “submatrix” of the form . Find
    1 −1
    this submatrix in example graph 5.
    3

    � �
    −1 1
    Question: In terms of Facebook, what would the submatrix
    1 −1
     
    −1 0 1
     
    mean? How about a submatrix that looks like this  1 −1 0 ?
    0 1 −1

    Observation_5 I suppose we should start talking about “the Face-


    book matrix”. Help me to make that idea precise: what are the
    vertices? What do the (directed) edges mean? How would you in-
    terpret the statement “Any friend of Nicholas Nickleby is a friend
    of mine” as a statement about connections in the Facebook graph?
    How are these connections reflected in the incidence matrix?

    Question: What about the “Six Degrees of Separation” game? See,


    for example, http://en.wikipedia.org/wiki/Six_degrees_of_separation

    Question: If I am separated from myself by 6 degrees, is there some


    sort of submatrix involved? More importantly, what would this say
    about my social life?

    Observation_6 Time to move from submatrices to the entire inci-


    dence matrix of the graph. The basic matrix operation we have is
    elimination. Justify the following claim: The elimination matrices
    involved when working with the incidence matrix of a graph have
    only zeros, ones, and minus ones as entries.

    Question Perform elimination on the incidence matrix in example


    graph 5. Is it generally true that each matrix during the elimina-
    tion process, I mean the EA’s, has only zeros, ones, and minus
    ones as entries?

    Question The defining property for an incidence matrix is having


    one −1 and one +1 in each row. Ignoring any rows of zeros, does
    elimination preserve this property?

    Question Cool! This means that at each step of the elimination we


    have an incidence matrix, and hence a new graph! Trace through
    the graphs involved in example graph 5. Describe what is happen-
    ing at each stage of the process. What is the end result? Try your
    hand at this process a second time using example graph 6.

    Observation_7 During elimination, certain things disappear. We


    should be able to describe what is disappearing in some sensible
    way. Perhaps we can even predict beforehand what will disappear
    and what will remain once elimination is complete. Do you have
    any conjectures along these lines? Seems this would make a nice
    HW project. Additional HW is given on the sheet of examples.

    You might also like