Explore BrainMass

Explore BrainMass

    Graph theory: Find matrices representing the linear transformations ∂ and δ.

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Please see attached file for full problem description.

    Let C0 ={SUM (i = 1 to p) εivi│εi is an element of F2, vi is an element of V(G)}
    be the vector space of 0-chains
    and
    Let C1 ={SUM (i = 1 to q) εiei│εi is an element of F2, ei is an element of E(G)}
    be the vector space of 1-chains

    Recall the linear transformations
    boundry ∂ : C1 → C0 defined by ∂(uv) = u + v and
    coboundary δ: C0 → C1 defined by δ(u) = SUM ei, where ei is adjacent to v.

    Let Z(G) = { x an element of C1│∂(x) = 0} be the cycle space of G
    and
    Let B(G) ={ x an element of C1│there exists y an element of C0, x = ∂(y)} be the coboundary space of G.

    a. Find matrices representing the linear transformations ∂ and δ.
    b. Define an inner product on C1 by < x,y > = SUM &#949;i&#951;i, where x = SUM &#949;iei and y = SUM &#951;iei.
    Prove that x is an element of Z(G) iff < x,y > = 0 for all y element of B(G)
    c. Show that the dimensions of B(G) is p - k(G).
    d. Characterize the class of graphs for which B(G) = C1(G)

    © BrainMass Inc. brainmass.com December 24, 2021, 6:54 pm ad1c9bdddf
    https://brainmass.com/math/linear-transformation/graph-theory-representing-linear-transformations-148433

    Attachments

    SOLUTION This solution is FREE courtesy of BrainMass!

    The explanations are in the attached pdf file.

    As required by Brainmass, I past the original text in plain TEXT below.
    You do not have to read it since all you need is in the pdf file.

    =======
    Here is the plain TEXT source

    magnification=magstep1
    baselineskip=12pt
    parindent = 0pt
    parskip = 12pt

    defl{left}
    defr{right}
    defla{langle}
    defra{rangle}
    defp{partial}
    defu{uparrow}
    defd{downarrow}

    centerline{bf Boundary and Coboundary}

    bf (a) rm

    A matrix representing the boundary operator $p$ for a gragh with $p$ vertices and $q$ edges, for $C_0$ and $C_1$ defined on field $F_2={ 0 ~ 1}$, is a $ptimes q$ matrix $M_p$ of $p$ rows and $q$ columns contaning 0s or 1s.
    Each column represents an edge. If this edge connects vertices $i$ and $j$, the column has 1s in the two rows corresponding to vertices $i$ and $j$ and 0s in the rest of its cells.
    The same can be defined by saying that each row represents a vertex with 1s in positions of the edges emerging from this vertex and 0s in the rest of its cells.

    The matrix representing the co-boundary operator $delta$ is a $qtimes p$ matrix $M_delta$ which is the transpose of the boundary matrix:
    $$
    M_delta = M_p^top.
    $$

    bf (b) rm

    Every element of $B(G)$ splits the graph into unconnected parts.
    On the other hand any cycle, that is element of $Z(G)$, is a path returning back to the vertex it started from.
    Therefore, any cycle can contain only an bf even rm number of edges from $B(g)$. Since $1+1=0$, this evenness means that $la x, yra = 0$.

    bf (c) rm

    Let us start from the case of a connected graph, $k(G)=1$.

    Every vertex generates a boundary made of the edges emerging from this vertex and every boundary is a sum of boundaries of separate vertices taken from the set of vertices that generates this boundary.
    Therefore, the dimension of $B(G)$ cannot be larger than $p$.

    Next, we note that every boundary separates a graph into two sets of vertices complementary to each other, and each of these sets generates the same boundary.
    Therefore, the dimension of $B(G)$ cannot be larger than $p-1$.

    Next, let us take an arbitrary vertex and mark it to be excluded from any sets of vertices we may consider at this point. Now, when a boundary splits the graph in two parts, there is only one set of vertices that generates it (the complementary set would have to include the marked forbidden vertex and so is not permitted here).
    Therefore we see that there are at least $p-1$ linearly independent boundaries generated by the unmarked $p-1$ vertices.

    From this we conclude that $dim[B(G)] = p-1$ for a connected graph.

    In an arbitrary graph, the same argument applies to each of its components, and therefore we find that
    $$
    dim[B(G)] = p-k(G).
    $$

    bf (d) rm

    If $B(G) = C_1(G)$, then every single edge is a boundary, therefore the graph has no cycles, therefore the graph is a forest (of trees).
    Conversely, any element of $C_1(G)$ splits the graph into unconnected sets, and so is a boundary. Therefore $B(G) = C_1(G)$ can serve as a definition of a forest.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    © BrainMass Inc. brainmass.com December 24, 2021, 6:54 pm ad1c9bdddf>
    https://brainmass.com/math/linear-transformation/graph-theory-representing-linear-transformations-148433

    Attachments

    ADVERTISEMENT