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 is a set (usually finite, "vertices") along with a set ("edges") of unordered pairs of distinct elements of .
DEFINITION 2 Incident If an edge , we say that is incident to
and .
DEFINITION 3 N-valent In a graph , a vertex is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where .
DEFINITION 4 Edge Cover An edge cover for graph is a subset such that every edge of incident to at least one vertex in .
DEFINITION 5 Independent Let be a graph. A subset is called independent if whenever , then .
THEOREM 1 Edge covers are complementary to independent sets. In other words, is an edge cover if and only if the complementary subset is an independent set.
Proof Assume is an edge cover. I assert that is independent. Indeed, if , then since is an edge cover, either or , which implies they are not connected.
