15-344/Classnotes for Thursday September 17: Difference between revisions
| Line 13: | Line 13: | ||
*A ''bijection'' is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection |
*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. |
*Isomorphism does not mean two things are identical but means they are mathematically the same. |
||
The relationship of isomorphisms: |
The relationship of isomorphisms: |
||
| Line 23: | Line 23: | ||
3. '''Transitive:''' <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math> |
3. '''Transitive:''' <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math> |
||
CLAIM If two graphs are isomorphic, then they have: |
|||
1. same number of vertices |
|||
2. same number of edges |
|||
3. vertex degrees (valencies) are the same between the two. For example, if one graph has 3 vertices of degree 2, and 2 vertices of degree 1, |
|||
then the other graph should have the same |
|||
4. same number of subgraphs |
|||
5. same number of complements denoted by <math>G^c = (V,E^c)</math> |
|||
*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math> |
|||
Revision as of 20:38, 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 [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 means they are 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]
CLAIM If two graphs are isomorphic, then they have:
1. same number of vertices
2. same number of edges
3. vertex degrees (valencies) are the same between the two. For example, if one graph has 3 vertices of degree 2, and 2 vertices of degree 1, then the other graph should have the same
4. same number of subgraphs
5. same number of complements denoted by [math]\displaystyle{ G^c = (V,E^c) }[/math]
- Complement means [math]\displaystyle{ (ab)\in E^c \Longleftrightarrow (ab)\notin E }[/math]
