15-344/Classnotes for Thursday September 17: Difference between revisions
From Drorbn
Jump to navigationJump to search
| Line 4: | Line 4: | ||
(Files not beginning with "15-344" were deleted). |
(Files not beginning with "15-344" were deleted). |
||
== Lecture Notes for September 17 == |
|||
'''DEFINITION 7 Isomorphism''' A graph <math>G_1 = (V_1, E_1)</math> is called ''isomorphic'' to a graph <math>G_2 = (V_2, E_2)</math> whenever |
|||
there exists a bijection <math>\phi:V_1 \rightarrow V_2</math> such that <math>\forall a,b\in V_1</math> we have <math>(ab)\in E_1</math> if and |
|||
only if <math>( \phi (a) \phi (b))\in E_2</math>. <math>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>G \sim G</math> A graph is isomorphic to itself |
|||
2. '''Symmetric:''' <math>G_1 \sim G_2 \implies G_2 \sim G_1 </math> In other words, for every <math>\phi:V_1 \rightarrow V_2</math> we have |
|||
<math>\phi ^{-1} :V_2 \rightarrow V_1</math> |
|||
3. '''Transitive:''' <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math> |
|||
Revision as of 21:28, 17 September 2015
Scanned Lecture Notes for September 17
(Files not beginning with "15-344" were deleted).
Lecture Notes for September 17
DEFINITION 7 Isomorphism A graph is called isomorphic to a graph whenever there exists a bijection such that we have if and only if . 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: A graph is isomorphic to itself
2. Symmetric: In other words, for every we have
3. Transitive:
