15-344/Classnotes for Tuesday September 15: Difference between revisions
No edit summary |
|||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 35: | Line 35: | ||
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent. |
<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 |
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>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>(\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 |
<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 Notes 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> |
|||
== Handwritten Lecture Notes in PDF == |
|||
[[Media:15-344(lecture1).PDF|MAT344 - Lecture1 (Sep 15)]] |
|||
Latest revision as of 10:33, 7 November 2015
We mostly went over Day One Handout today.
| Dror's notes above / Students' notes below |
Lecture Note for September 15
DEFINITION 1 Graph A graph [math]\displaystyle{ G = (V,E) }[/math] is a set [math]\displaystyle{ V = \{a,b,...\} }[/math] (usually finite, "vertices") along with a set [math]\displaystyle{ E = \{(ab),(bc),(bd),...\} }[/math] ("edges") of unordered pairs of distinct elements of [math]\displaystyle{ V }[/math].
DEFINITION 2 Incident If an edge [math]\displaystyle{ e = (ab)\in{E} }[/math], we say that [math]\displaystyle{ e }[/math] is incident to [math]\displaystyle{ a }[/math]
and [math]\displaystyle{ b }[/math].
DEFINITION 3 N-valent In a graph [math]\displaystyle{ G = (V,E) }[/math], a vertex [math]\displaystyle{ 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]\displaystyle{ n = 0,1,2,.. }[/math].
DEFINITION 4 Edge Cover An edge cover for graph [math]\displaystyle{ G = (V,E) }[/math] is a subset [math]\displaystyle{ C\subset{V} }[/math] such that every edge of [math]\displaystyle{ G }[/math] incident to at least one vertex in [math]\displaystyle{ C }[/math].
DEFINITION 5 Independent Let [math]\displaystyle{ G = (V,E) }[/math] be a graph. A subset [math]\displaystyle{ I\subset{V} }[/math] is called independent if whenever [math]\displaystyle{ a,b\in{I} }[/math], then [math]\displaystyle{ (ab)\notin{E} }[/math].
THEOREM 1 Edge covers are complementary to independent sets. In other words, [math]\displaystyle{ C\subset{V} }[/math] is an edge cover if and only if
the complementary subset [math]\displaystyle{ V-C }[/math] is an independent set.
Proof
[math]\displaystyle{ (\rightarrow) }[/math] Assume [math]\displaystyle{ C }[/math] is an edge cover. I assert that [math]\displaystyle{ I = V-C }[/math] is independent.
Indeed, if [math]\displaystyle{ e=(ab)\in{E} }[/math], then since [math]\displaystyle{ C }[/math] is an edge cover, either [math]\displaystyle{ a\in{C} \implies a\notin{I} }[/math] or
[math]\displaystyle{ b\in{C} \implies b\notin{I} }[/math], which implies [math]\displaystyle{ e }[/math] does not connect any two elements of [math]\displaystyle{ I }[/math].
[math]\displaystyle{ (\leftarrow) }[/math] Assume [math]\displaystyle{ I=V-C }[/math] is independent. Pick any edge [math]\displaystyle{ e = (ab)\in{E} }[/math]. As [math]\displaystyle{ I }[/math] is independent, [math]\displaystyle{ (ab) }[/math] does not connect any two members of [math]\displaystyle{ I }[/math]. Hence, either [math]\displaystyle{ a\notin{I} \implies a\in{C} }[/math] or [math]\displaystyle{ b\notin{I} \implies b\in{C} }[/math], which implies [math]\displaystyle{ e }[/math] is incident to an element of [math]\displaystyle{ 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 Notes for September 15
Page 1
Page 2
Summary
