adjacency

  1. U

    Graph from Adjacency Matrix

    Denote the vertices of G G1, G2, G3, does the 2 in the matrix just means there's 2 paths of length 1 from G2 to G1? ie, look like this: thx
  2. A

    Minimum spanning tree recursive algorithm using only adjacency list

    Looking for some help with starting points more so than solutions here. How can I go about proving 1, 2, and 3? I don't understand exactly what S is? Just an array of all e_{v} basically? Additionally I don't understand G vs. G_{S}? Design and analyze a minimum spanning tree recursive algorithm...
  3. U

    Adjacency Matrix

    First note that my book uses the convention that for an adjacency matrix, say we have row i and column j where i = j, then the entry is twice the number of loops incident on i. In other words, if there is a loop on a vertex we put 2 as the matrix entry instead of 1. Now my book says "If A is...
  4. R

    Adjacency Matrix

    Hi all; I need the proof of the folowing Theorem: If X is the adjacency matrix of a graph G with n vertices, and Y=X+X^2+X^3+....+X^{n-1}, then G is disconnected if and only if there exist at least one entry in matrix Y that is zero. Best Wishes
  5. M

    Question about adjacency in K-maps?

    I am looking at some k-maps and puzzled about grouping the adjacent cells. Pretend this is a 4 variable k-map of F(A,B,C,D) (sorry, I don't know of a better way to display them): 1100 1001 1001 1100 I see 3 groups: 1100 1001 1001 1100 1100 1001 1001 1100 1100 1001 1001 1100 Are these 3...
  6. S

    how do I find number of vertices given adjacency matrix

    If I am given the adjacency matrix \left[ {\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ \end{array} } \right] then how do I find the number of vertices to determine if it's strongly connected? I guess this example could...
  7. S

    adjacency matrices

    I was just wondering if what i have done is correct, i have my doubts as other graphs i have seen have not looked like this, with all connections being two way http://img23.imageshack.us/img23/5682/adjacencymatrix.jpg Ive written it on paper so here is a an image ive made on paint...
  8. H

    Adjacency Matrix / Multiplication Table

    Hi guys I'm stuck on these questions. I've done the first part of question 1 but I don't get the x^2 = 3 bit. I've done 2. a) and c) but don't get b). Can someone help me understand it? I don't want someone to do the questions lol I just don't get how to do it! :)
  9. S

    adjacency matrix...graph!?

    Iv attached the question as an image as well as the graph that i drew from the adjacency matrix... How would i go about calculating A (squared)??? Help would be very much appreciated!
  10. S

    Adjacency matrix...(graphs!)

    Hi, Im abit confused with the attached question: i have drawn a graph which doesnt look like a graph at all??!...is it correct that the graph isnt connected??!?!:confused: Any help would greatly be appreciated!