Results 1 to 5 of 5

Math Help - logic sets question 2

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    29

    logic sets question 2

    can anyone do this question/
    Attached Thumbnails Attached Thumbnails logic sets question 2-2.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,740
    Thanks
    645
    Hello, srk619!

    I can get you started . . .


    Draw the graph with adjacency matrix: . \begin{bmatrix}0&1&1&0&0&0 \\ 1&0&1&0&0&0 \\ 1&1&0&1&0&0 \\ 0&0&1&0&1&1 \\ 0&0&0&1&0&1 \\ 0&0&0&1&1&0 \end{bmatrix}

    . . . . \begin{array}{ccccc} & & \boxed{2} \\ & ^{\nearrow}_{\swarrow} & & ^{\searrow}_{\nwarrow} \\ \boxed{1} & \leftrightarrow & \leftrightarrow & \leftrightarrow & \boxed{3} \\  & & & & \uparrow\downarrow \\ \boxed{6} & \leftrightarrow & \leftrightarrow & \leftrightarrow & \boxed{4} \\ & ^{\nwarrow}_{\searrow} & & ^{\swarrow}_{\nearrow} \\ & & \boxed{5}  \end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    29
    is that the graph
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    29
    what do you do now i dont understand it
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2009
    From
    Cairo
    Posts
    5
    Hello srk619,


    (a)


    In an adjacency matrix, the rows and columns of the matrix represent the nodes of the graph
    , and the value of the matrix element at row i and column j represents the edges. If it's 1 means there is an edge from node i to node j.


    Now, there could be two possibilities, the graph could be directed ( the edges have arrows on them to represent direction) or undirected (edges have no arrows).


    Let's assume the nodes are numbered starting from 1
    i.e. row 1 of matrix represents node 1
    row 2 of matrix represents node 2, and so on till,
    row 6 of matrix represents node 6


    the same can be said about the columns


    column 1 of matrix represents node 1
    column 2 of matrix represents node 2, and so on till,
    column 6 of matrix represents node 6


    Thus, If the graph is directed, and according to the posted adjacency matrix,


    - a Zero at row 1,column 1 means there is no edge from node 1 to itself


    - a One at row 2,column 1 means there is an edge directed from node2 to node1


    - a One at row 1,column 2 means there is an edge directed from node1 to node2


    So, basically, the row represents the starting point(node) of the edge, and the column represents the ending point (node) of the edge, if there is a One in the matrix,


    So continuing in this manner the graph will be

    logic sets question 2-directed.bmp

    but what if the graph is undirected (edges have no arrows), i.e. both nodes can be considered as both starting and ending points, so to indicate this, we should put a One in both directions
    for all edges.


    for ex in an undirected graph, if there is an edge between node 1 and node2, we should put a One
    at row1, column2 , and a One at row2, column1


    So, if it happens that there was a One in a certain direction , but a Zero in the opposite direction, it means that this graph is directed.


    And if it happens that for all edges, there is an edge in both directions, We can't tell Whether the graph is directed or undirected. (It depends on the assumptions of the problem) which is the case in this problem.


    To check that a graph could be undirected, you can take the transpose of the matrix
    Transpose is to exchange the rows and the columns,
    for ex: row 1 becomes column 1, and column 1 becomes row 1
    if the matrix transpose is equal to the original matrix, then the graph could be undirected
    which is the case in this problem


    So if the problem assumption was undirected graph, the graph will be

    logic sets question 2-undirected.bmp


    b)


    “It is not difficult to prove by mathematical induction that the number of different paths of length k>0 from the ith verterx to the jth vertex of a graph (undirected or directed) equals the (i, j)th element of A to the power of k, where A is the adjacency matrix of the graph” Introduction to The Design and Analysis of Algoritms, 2nd Edition, Anany Levitin


    So Here are the steps of the solution:



    1. Compute A^2,
      A^2 = A.A = [ 2 1 1 1 0 0 ]

    [ 1 2 1 1 0 0 ]
    [ 1 1 3 0 1 1 ]
    [ 1 1 0 3 1 1 ]
    [ 0 0 1 1 2 1 ]
    [ 0 0 1 1 1 2 ]


    so the entry at row1, coumn3 is equal to 1, so there is one path
    You can verify this by looking at graph, you will find this is the path 1,2,3




    c)

    I am not sure what is the adjacency matrix connectivity algorithm, but you can do a Depth-First Search (DFS ) or Breadth-First Search (BFS) , and after the algorithm halts, check whether all nodes will have been visited. If they have, the graph is connected; otherwise, it's not connected


    Hope this helps
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with sets and logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2011, 02:56 PM
  2. Question about Sets and Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 29th 2010, 12:56 PM
  3. logic and sets help!!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 24th 2008, 12:30 AM
  4. logic sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2008, 10:04 AM
  5. Sets and Logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 23rd 2008, 05:15 PM

Search Tags


/mathhelpforum @mathhelpforum