Exploring Discrete Mathematics through Graph Theory
Delve into the world of discrete mathematics with a focus on graph theory. Learn about graphs, their properties, and essential theorems. Discover how graphs model relations in various applications like network routing, GPS guidance, and chemical reaction simulations. Explore graph terminology, theorems, and fundamental principles such as the sum of degrees in undirected graphs. Engage with intriguing problems and concepts that showcase the beauty and utility of discrete mathematics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Creative Commons License CSE 20 Discrete Mathematics Dr. Cynthia Bailey Lee Dr. Shachar Lovett Peer Instruction in Discrete Mathematics by Cynthia Leeis licensed under a Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.
2 Today s Topics: 1. Graphs 2. Some theorems on graphs
3 Graphs Model relations between pairs of objects Basic ingredient in many algorithms: Network routing, GPS guidance, Simulation of chemical reactions,
4 San diego road graph
5 Graph terminology The fruits are the A. Graphs B. Vertices C. Edges D. Loops E. None/other/more than one
6 Graph terminology The arrows are the A. Graphs B. Vertices C. Edges D. Loops E. None/other/more than one
7 Graph terminology Is this graph A. Undirected B. Directed C. Both D. Neither E. None/other/more than one
8 Graph terminology Which of the following is not a correct graph A. B. C. D. None/other/more than one
9 Our first graph theorem We already saw a theorem about graphs! Recall: in any group of 6 people, either there are 3 that form a club, or 3 that are strangers Any graph with 6 vertices contains either a triangle (3 vertices all connected) or an empty triangle (3 vertices not connected)
10 Our second graph theorem Let G be an undirected graph Degree of a vertex number of edges adjacent to it (e.g. touch it) Denote it by degree(v) Theorem: in any undirected graph, the sum of all the degrees is even Try and prove yourself first
11 Our second graph theorem Theorem: in any undirected graph, the sum of all the degrees is even Proof: Consider pairs (v,e) with v a vertex and e an edge adjacent to it. Create a list of all such pairs. How many elements this list has? We calculate it in two ways 1. Each vertex v has degree(v) edges adjacent to it, so this list has sum of degrees many elements 2. Each edge has 2 vertices adjacent to it, so this list has twice the number of edges many elements So, sum of degrees = twice the number of edges, hence it must be even. QED.
12 Eulerian graphs Let G be an undirected graph A graph is Eulerian if it can drawn without lifting the pen and without repeating edges Is this graph Eulerian? A. Yes B. No
13 Eulerian graphs Let G be an undirected graph A graph is Eulerian if it can drawn without lifting the pen and without repeating edges What about this graph A. Yes B. No
14 Eulerian graphs How can we check if a graph is Eulerian? A. Check all possible paths B. Stare and guess C. Be brave and do some math
15 Eulerian graphs Degree of a vertex: number of edges adjacent to it Euler s theorem: a graph is Eulerian iff the number of vertices with odd degrees is either 0 or 2 (eg all vertices or all but two have even degrees) Does it work for and ?
16 Proving Euler s theorem Euler s theorem gives a necessary and sufficient condition for a graph to be Eulerian All degrees are even Two degrees odd, rest are even Will prove in class that this is necessary Take-home challenge: prove that this is also sufficient
17 Proving Euler s theorem: necessary part Euler s theorem (necessary part): If a graph G is Eulerian then all degrees are even; or two degrees are odd and rest are even Try to prove it first yourself
18 Proving Euler s theorem: necessary part Proof of Euler s theorem (necessary part): Let G be a graph with an Euler path: v1,v2,v3, .,vk where (vi,vi+1) are edges in G; vertices may appear more than once; and each edge of G is accounted for exactly once. The degree of a vertex of G is the number of edges it has. For any internal vertex in the path (eg not v1 or vk), we count 2 edges in the path (one going in and one going out). So, any vertex which is not v1 or vk must have an even degree. If v1 vk then both have odd degrees. If v1=vk is the same vertex this is also has even degree. QED.
19 Proof by contradiction Another example (student self-study)
20 Example 2 A number x is rational if x=a/b for integers a,b. E.g. 3=3/1, 1/2, -3/4, 0=0/1 A number is irrational if it is not rational E.g (proved in textbook) 2 Theorem: If x2 is irrational then x is irrational.
21 Example 2 Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume that A. There exists x where both x,x2 are rational B. There exists x where both x,x2 are irrational C. There exists x where x is rational and x2 irrational D. There exists x where x is irrational and x2 rational E. None/other/more than one
22 Example 2 Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume that there exists x where x is rational and x2 irrational. Try by yourself first
23 Example 2 Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume that there exists x where x is rational and x2 irrational. Since x is rational x=a/b where a,b are integers. But then x2=a2/b2. Both a2,b2 are also integers and hence x2 is rational. A contracition.
24 Example 3 Theorem: is irrational Proof (by contradiction). + 2 3 THIS ONE IS MORE TRICKY. TRY BY YOURSELF FIRST IN GROUPS.
25 Example 3 + Theorem: is irrational Proof (by contradiction). Assume not. Then there exist integers a,b such that / 3 2 a b = + 2 3 b = + 2 2 = + + 2 2 2 Squaring gives So also is rational since 6 / ( 2 3) 6 3 a = 2 2 2 6 ( 5 ) / 2 . a b b [So, to finish the proof it is sufficient to show that is irrational. ] 6
26 Example 3 Theorem: is irrational Proof (by contradiction). is rational is rational. 2 3 + + 2 3 6 =c/d for positive integers c,d. Assume that d is minimal such that c/d= Squaring gives c2/d2=6. So c2=6d2 must be divisible by 2. Which means c is divisible by 2. Which means c2 is divisible by 4. But 6 is not divisible by 4, so d2 must be divisible by 2. Which means d is divisible by 2. So both c,d are divisible by 2. Which means that (c/2) and (d/2) are both integers, and (c/2) / (d/2) = Contradiction to the minimality of d. 6 6 6
