15-344/Classnotes for Thursday September 17: Difference between revisions
| Line 38: | Line 38: | ||
*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math> |
*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math> |
||
'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and |
|||
<math>E'\subset E</math>. |
|||
Revision as of 20:44, 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]
DEFINITION 8 Subgraph A subgraph of a graph [math]\displaystyle{ G = (V,E) }[/math] is a graph [math]\displaystyle{ G' = (V',E') }[/math] such that [math]\displaystyle{ V'\subset V }[/math] and [math]\displaystyle{ E'\subset E }[/math].
