15-344/Classnotes for Tuesday September 15: Difference between revisions
No edit summary |
|||
| (10 intermediate revisions by 4 users not shown) | |||
| Line 26: | Line 26: | ||
'''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>. |
'''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 |
'''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 |
||
| Line 34: | 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> |
<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 <math> |
<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 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 does not connect any two elements of .
Assume is independent. Pick any edge . As is independent, does not connect any two members of . Hence, either or , which implies is incident to an element of . 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
