15-344/Classnotes for Thursday September 17
Scanned Lecture Notes for September 17
(Files not beginning with "15-344" were deleted).
Lecture Notes for September 17
DEFINITION 7 Isomorphism A graph [math]\displaystyle{ G_1 = (V_1, E_1) }[/math] is called isomorphic to a graph [math]\displaystyle{ G_2 = (V_2, E_2) }[/math] whenever there exists a bijection [math]\displaystyle{ \phi:V_1 \rightarrow V_2 }[/math] such that [math]\displaystyle{ \forall a,b\in V_1 }[/math] we have [math]\displaystyle{ (ab)\in E_1 }[/math] if and only if [math]\displaystyle{ ( \phi (a) \phi (b))\in E_2 }[/math]. [math]\displaystyle{ G_1\sim G_2 }[/math] means they are isomorphic to each other.
- A bijection is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection
- Isomorphism does not mean two things are identical but mathematically the same.
The relationship of isomorphisms:
1. Reflexive: [math]\displaystyle{ G \sim G }[/math] A graph is isomorphic to itself
2. Symmetric: [math]\displaystyle{ G_1 \sim G_2 \implies G_2 \sim G_1 }[/math] In other words, for every [math]\displaystyle{ \phi:V_1 \rightarrow V_2 }[/math] we have [math]\displaystyle{ \phi ^{-1} :V_2 \rightarrow V_1 }[/math]
3. Transitive: [math]\displaystyle{ G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 }[/math]
