15-344/Classnotes for Thursday September 17 - Revision history

Roroyap: /* Scanned Lecture Note for September 17 */

2015-10-09T03:18:47Z

Scanned Lecture Note for September 17

← Older revision		Revision as of 23:18, 8 October 2015
Line 47:		Line 47:
	Image:15-344-Sept17-2.jpg\|Class notes page 2		Image:15-344-Sept17-2.jpg\|Class notes page 2
	Image:15-344-Sept17-3.jpg\|Class notes page 3		Image:15-344-Sept17-3.jpg\|Class notes page 3
			</gallery>

			== Scanned Tutorial Notes for September 17 ==

			<gallery>
			15-344 Tutorial 1.jpg\|Page 1
	</gallery>		</gallery>

LizElle: /* Scanned Lecture Note for September 17 */

2015-09-19T23:48:54Z

Scanned Lecture Note for September 17

← Older revision		Revision as of 19:48, 19 September 2015
Line 44:		Line 44:
	<gallery>		<gallery>
	Image:15-344_Note_2.jpg\|Answers of sample question		Image:15-344_Note_2.jpg\|Answers of sample question
			Image:15-344-Sept17-1.jpg\|Class notes page 1
			Image:15-344-Sept17-2.jpg\|Class notes page 2
			Image:15-344-Sept17-3.jpg\|Class notes page 3
	</gallery>		</gallery>

Mi.liu at 18:44, 19 September 2015

2015-09-19T18:44:04Z

← Older revision		Revision as of 14:44, 19 September 2015
Line 37:		Line 37:

	*Checking if two graphs are isomorphic is a hard problem		*Checking if two graphs are isomorphic is a hard problem



	== Scanned Lecture Note for September 17 ==		== Scanned Lecture Note for September 17 ==

Mi.liu at 18:43, 19 September 2015

2015-09-19T18:43:31Z

@@ Line 1: / Line 1: @@
 {{15-344/Navigation}}
 == Lecture Notes for September 17 ==
 '''DEFINITION 7 Isomorphism''' A graph <math>G_1 = (V_1, E_1)</math> is called ''isomorphic'' to a graph <math>G_2 = (V_2, E_2)</math> whenever
@@ Line 43: / Line 37: @@
 *Checking if two graphs are isomorphic is a hard problem

ChrisKim: /* Lecture Notes for September 17 */

2015-09-18T01:52:52Z

Lecture Notes for September 17

← Older revision		Revision as of 21:52, 17 September 2015
Line 41:		Line 41:
	'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and		'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and
	<math>E'\subset E</math>.		<math>E'\subset E</math>.

			*Checking if two graphs are isomorphic is a hard problem

ChrisKim: /* Lecture Notes for September 17 */

2015-09-18T01:44:27Z

Lecture Notes for September 17

← Older revision		Revision as of 21:44, 17 September 2015
Line 38:		Line 38:

	*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math>		*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math>

			'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and
			<math>E'\subset E</math>.

ChrisKim: /* Lecture Notes for September 17 */

2015-09-18T01:38:29Z

Lecture Notes for September 17

@@ Line 13: / Line 13: @@
 *A ''bijection'' is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection
-*Isomorphism does not mean two things are identical but mathematically the same.
+*Isomorphism does not mean two things are identical but means they are mathematically the same.
 The relationship of isomorphisms:
@@ Line 23: / Line 23: @@
 . '''Transitive:'''  <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math>

ChrisKim: /* Scanned Lecture Notes for September 17 */

2015-09-18T01:28:38Z

Scanned Lecture Notes for September 17

← Older revision		Revision as of 21:28, 17 September 2015
Line 4:		Line 4:

	(Files not beginning with "15-344" were deleted).		(Files not beginning with "15-344" were deleted).


			== Lecture Notes for September 17 ==
			'''DEFINITION 7 Isomorphism''' A graph <math>G_1 = (V_1, E_1)</math> is called ''isomorphic'' to a graph <math>G_2 = (V_2, E_2)</math> whenever
			there exists a bijection <math>\phi:V_1 \rightarrow V_2</math> such that <math>\forall a,b\in V_1</math> we have <math>(ab)\in E_1</math> if and
			only if <math>( \phi (a) \phi (b))\in E_2</math>. <math>G_1\sim G_2</math> means they are isomorphic to each other.

			*A ''bijection'' is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

			*Isomorphism does not mean two things are identical but mathematically the same.

			The relationship of isomorphisms:

			1. '''Reflexive''': <math>G \sim G</math> A graph is isomorphic to itself

			2. '''Symmetric:''' <math>G_1 \sim G_2 \implies G_2 \sim G_1 </math> In other words, for every <math>\phi:V_1 \rightarrow V_2</math> we have
			<math>\phi ^{-1} :V_2 \rightarrow V_1</math>

			3. '''Transitive:''' <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math>

Drorbn: /* Scanned Lecture Notes for September 17 */

2015-09-17T23:56:46Z

Scanned Lecture Notes for September 17

← Older revision		Revision as of 19:56, 17 September 2015
Line 3:		Line 3:
	== Scanned Lecture Notes for September 17 ==		== Scanned Lecture Notes for September 17 ==

			(Files not beginning with "15-344" were deleted).
	<gallery>
	Image:Pg001.jpg\|Page 1
	Image:Pg002.jpg\|Page 2
	Image:Pg003.jpg\|Page 3
	</gallery>

LizElle: Created page with "{{15-344/Navigation}} == Scanned Lecture Notes for September 17 == Image:Pg001.jpg|Page 1 Image:Pg002.jpg|Page 2 Image:Pg003.jpg|Page 3 "

2015-09-17T19:36:23Z

Created page with "{{15-344/Navigation}} == Scanned Lecture Notes for September 17 == <gallery> Image:Pg001.jpg|Page 1 Image:Pg002.jpg|Page 2 Image:Pg003.jpg|Page 3 </gallery>"

New page

{{15-344/Navigation}}

== Scanned Lecture Notes for September 17 ==

<gallery>
Image:Pg001.jpg|Page 1
Image:Pg002.jpg|Page 2
Image:Pg003.jpg|Page 3
</gallery>