Review Sheet for MATH 105 at KU 2
Popular in Course
Popular in Department
This 1 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Review Sheet for MATH 105 at KU 2
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
Math 105 Test 1 Review You will want to bring something to write with a pencil would be a good plan and a calculator No notesbooksfriends will be allowed on the test Chapter 5 Euler Circuits graph vocabulary graph adjacent connected edge degree disconnected vertex oddeven vertex bridge loop path Euler path multiple edge circuit Euler circuit making graphs that represent various situations Euler 3 Theorem 1 If a graph has any odd vertices then it cannot have an Euler circuit If a graph is connected and every vertex is an even vertex then it has at least one Euler circuit and usually more Euler 3 Theorem 2 If a graph has more than two odd vertices then it cannot have an Euler path If a graph is connected and has exactly two odd vertices then it has at least one Euler path and usually more Any such path must start at one of the odd vertices and end at the other one Euler 3 Theorem 3 The sum of the degrees of all the vertices of a graph equals twice the number of edges and therefore is an even number A graph always has an even number of odd vertices Fleury s Algorithm key examples cities with bridges neighborhood routes for mail carriers and security guards unicursal tracings Chapter 6 The Traveling Salesman Problem vocabulary Hamilton circuit complete graph Hamilton path factorial weight Traveling Salesman Problem weighted graph differences and similarities between Hamilton paths and circuits and Euler paths and circuits of Hamiltion circuits in KN Nl of edges in KN NN l 2 Brute Force Algorithm Nearest Neighbor Algorithm Repetitive Nearest Neighbor Algorithm key examples visiting cities running errands