Drorbn - User contributions [en]

15-344/Classnotes for Thursday September 17

2015-09-19T18:44:04Z

Mi.liu:

{{15-344/Navigation}}
== 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 means they are 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>

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>

'''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>.

*Checking if two graphs are isomorphic is a hard problem

== Scanned Lecture Note for September 17 ==

<gallery>
Image:15-344_Note_2.jpg|Answers of sample question
</gallery>

15-344/Classnotes for Thursday September 17

2015-09-19T18:43:31Z

Mi.liu:

File:15-344 Note 2.jpg

2015-09-19T18:40:11Z

Mi.liu:

15-344/Classnotes for Tuesday September 15

2015-09-19T18:36:33Z

Mi.liu:

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>e</math> does not connect any two elements of <math>I</math>.

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect any two members of <math>I</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

'''DEFINITION 6''' '''Matching''' is a subset of edges of a graph where no two edges share a common vertex. A matching is said to be perfect if
all edges in a graph are matched.

== Scanned Lecture Note for September 15 ==

<gallery>
Image:15-344-Sept15-1.jpg|Page 1
Image:15-344-Sept15-2.jpg|Page 2
Image:15-344_Note_1.jpg|Summary
</gallery>

15-344/Classnotes for Tuesday September 15

2015-09-19T18:36:04Z

Mi.liu:

File:15-344 Note 1.jpg

2015-09-19T15:12:39Z

Mi.liu: