Difference between revisions of "15-344/Classnotes for Thursday September 17"
(→Scanned Lecture Note for September 17) |
(→Scanned Lecture Note for September 17) |
||
Line 47: | Line 47: | ||
Image:15-344-Sept17-2.jpg|Class notes page 2 | Image:15-344-Sept17-2.jpg|Class notes page 2 | ||
Image:15-344-Sept17-3.jpg|Class notes page 3 | Image:15-344-Sept17-3.jpg|Class notes page 3 | ||
+ | </gallery> | ||
+ | |||
+ | == Scanned Tutorial Notes for September 17 == | ||
+ | |||
+ | <gallery> | ||
+ | 15-344 Tutorial 1.jpg|Page 1 | ||
</gallery> | </gallery> |
Latest revision as of 23:18, 8 October 2015
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 means they are 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:
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
- Complement means
DEFINITION 8 Subgraph A subgraph of a graph is a graph such that and .
- Checking if two graphs are isomorphic is a hard problem