Results 1 to 3 of 3

Math Help - Isomorphic Graph

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    23

    Isomorphic Graph

    I am home studying graph theory

    I have a definition of Isomorphism as follows.
    G1 = (v1, E1, L1)
    G2 = (V2, E2, L2)

    G1 is isomorphic to G2 if
    1: there is a bijective mapping between V1 and V2
    2: edges between pairs of verticies in G1 must present between the corresponding pair of verties in G2
    3: the lables are preserved by condition 1

    I interpret this as: For every v E V1 maps to a v E V2 + the ordered pairs (a, b) in E1 has an equivalent in E2 + the lables are preserved.

    1: Is that about right?
    2: bijective mapping in general is: f(a) = b - such that 1 element of 'a' maps to one element of 'b' - in graph theory do you need a function of is it just a case of searching the graph and chacking the mapping is correct?

    Regards

    Richard.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I interpret this as: For every v E V1 maps to a v E V2 + the ordered pairs (a, b) in E1 has an equivalent in E2 + the lables are preserved.
    This is correct but not written completely precisely. Formally, this would be: There exists a bijection f: V1 -> V2 such that for every v1, v2 we have (v1, v2) in E1 iff (f(v1), f(v2)) in E2. There should be another condition for labels, but it is not clear from your description what the type of L1 and L2 is: are they sets? functions? I guess, usually labels are identified with nodes.

    in graph theory do you need a function of is it just a case of searching the graph and checking the mapping is correct?
    A mapping is a function. The two things you described are the same thing, one possible written more formally than the other.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 2nd 2011, 06:39 AM
  2. D2n Isomorphic To Dn X Z2
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 19th 2010, 01:27 PM
  3. Graph Proofs- Isomorphic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 8th 2009, 06:17 AM
  4. isomorphic graph, planar graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 09:13 AM
  5. Isomorphic or not?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2008, 05:41 PM

Search Tags


/mathhelpforum @mathhelpforum