15-344/Classnotes for Tuesday September 15

DBN: Classes: 2015-16: 15-344 / Navigation Welcome to Math 344! Edits to the Math 344 web sites no longer count for the purpose of good deed points. # Week of... Notes and Links 1 Sep 14 About This Class, Day One Handout, Tuesday, Hour 3 Handout, Thursday, Tutorial 1 Handout 2 Sep 21 Tuesday, Tutorial 2 Page 1, Tutorial 2 Page 2, Thursday, HW1 3 Sep 28 Tuesday, Class Photo, Tutorial 3 Page 1, Tutorial 3 Page 2, Thursday, HW2 4 Oct 5 Tuesday, Drawing $n$-cubes, Thursday, HW3 5 Oct 12 Tuesday, Tutorial Handout, Thursday, HW4 6 Oct 19 Tuesday, Tutorial Handout, Thursday 7 Oct 26 Term Test on Tuesday, Dijkstra Handout,Thursday,HW5 8 Nov 2 Tuesday, Tutorial Handout, Thursday, HW6, Sunday November 8 is the last day to drop this class 9 Nov 9 Monday-Tuesday is UofT Fall Break, Thursday, HW7 10 Nov 16 Tuesday, Thursday, HW8 11 Nov 23 Tuesday, Thursday, HW9 12 Nov 30 Tuesday, Thursday, HW10 13 Dec 7 Tuesday, FibonacciFormula.pdf, semester ends on Wednesday - no class Thursday F Dec 11-22 The Final Exam Register of Good Deeds Add your name / see who's in!

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} is a set $V=\{a,b,...\}$ (usually finite, "vertices") along with a set $E=\{(ab),(bc),(bd),...\}$ ("edges") of unordered pairs of distinct elements of $V$.

DEFINITION 2 Incident If an edge $e=(ab)\in {E}$, we say that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is incident to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} .

DEFINITION 3 N-valent In a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} , a vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \in{V}} is called bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 0,1,2,.. } .

DEFINITION 4 Edge Cover An edge cover for graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} is a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\subset{V}} such that every edge of $G$ incident to at least one vertex in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} .

DEFINITION 5 Independent Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} be a graph. A subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I\subset{V}} is called independent if whenever Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b\in{I}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (ab)\notin{E}} .

THEOREM 1 Edge covers are complementary to independent sets. In other words, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\subset{V}} is an edge cover if and only if the complementary subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V-C} is an independent set.

Proof Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\rightarrow)} Assume $C$ is an edge cover. I assert that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I = V-C} is independent. Indeed, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=(ab)\in{E}} , then since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is an edge cover, either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in{C} \implies a\notin{I}} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\in{C} \implies b\notin{I}} , which implies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} does not connect any two elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\leftarrow)} Assume $I=V-C$ is independent. Pick any edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e = (ab)\in{E}} . As Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} is independent, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (ab)} does not connect any two members of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} . Hence, either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\notin{I} \implies a\in{C}} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\notin{I} \implies b\in{C}} , which implies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is incident to an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} . 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

• 

  Page 1

• 

  Page 2