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.
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.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.
A mapping is a function. The two things you described are the same thing, one possible written more formally than the other.in graph theory do you need a function of is it just a case of searching the graph and checking the mapping is correct?