15-344/Classnotes for Tuesday September 15: Difference between revisions
(Created page with "{{15-344/Navigation}} We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today. {{15-344:Dror/Students Divider}}") |
No edit summary |
||
| Line 4: | Line 4: | ||
{{15-344:Dror/Students Divider}} |
{{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 they are not connected. |
|||
Revision as of 21:34, 15 September 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 they are not connected.
