15-344/Classnotes for Tuesday September 15 - Revision history

Com138 at 15:33, 7 November 2015

2015-11-07T15:33:48Z

← Older revision		Revision as of 11:33, 7 November 2015
Line 50:		Line 50:
	Image:15-344_Note_1.jpg\|Summary		Image:15-344_Note_1.jpg\|Summary
	</gallery>		</gallery>



			== Handwritten Lecture Notes in PDF ==
			[[Media:15-344(lecture1).PDF\|MAT344 - Lecture1 (Sep 15)]]

2015-09-23T03:57:54Z

← Older revision		Revision as of 23:57, 22 September 2015
Line 43:		Line 43:
	all edges in a graph are matched.		all edges in a graph are matched.

	== Scanned Lecture ~~Note~~ for September 15 ==		== Scanned Lecture Notes for September 15 ==

	<gallery>		<gallery>

2015-09-19T18:36:33Z

2015-09-19T18:36:04Z

2015-09-18T15:04:48Z

← Older revision	Revision as of 11:04, 18 September 2015
(No difference)

2015-09-18T01:03:46Z

Lecture Note for September 15

← Older revision		Revision as of 21:03, 17 September 2015
Line 40:		Line 40:
	<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 Note for September 15 ==		== Scanned Lecture Note for September 15 ==

2015-09-16T13:07:32Z

Lecture Note for September 15

← Older revision		Revision as of 09:07, 16 September 2015
Line 39:		Line 39:
	<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


			== Scanned Lecture Note for September 15 ==

			<gallery>
			Image:15-344-Sept15-1.jpg\|Page 1
			Image:15-344-Sept15-2.jpg\|Page 2
			</gallery>

2015-09-16T02:49:18Z

Lecture Note for September 15

← Older revision		Revision as of 22:49, 15 September 2015
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,

2015-09-16T02:49:04Z

Lecture Note for September 15

← Older revision		Revision as of 22:49, 15 September 2015
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>~~a,b~~</math> ~~are~~ not ~~connected.~~		<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,

2015-09-16T02:44:43Z

Lecture Note for September 15

← Older revision		Revision as of 22:44, 15 September 2015
Line 38:		Line 38:

	<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>~~a,b~~</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