Limited time offer 20% OFF StudySoup Subscription details

UK - MATH 111 - Study Guide - Final

Created by: Brooke Humphreys Elite Notetaker

UK - MATH 111 - Study Guide - Final

This preview shows pages 1 - 2 of a 4 page document. to view the rest of the content
background image Graph Theory Key Terms: Graph: a set of points and lines (the lines connect between the points) Vertices: points on a graph Edges: lines on a graph Loop: an edge that connects to the same vertex on both ends (forming a loop) Multiple Edges: when more than one edge connects to the same two vertices (bending one edge) Simple Graph: a graph that does NOT include any loops or multiple edges Path: the edges that connect vertices that can be recorded and numbered  Circuit: a path that begins and ends at the same vertex Euler Path: a path that uses every edge in the graph without repeating any edges Euler Circuit: a path that uses every edge in the graph without repeating any edges, AND starts 
and ends at the same vertex
Connected Graph: a path can be found between any pair of vertices in the graph Component: a group of vertices that form a single “piece” of the graph because they are all 
connected by edges and paths
Degree of a Vertex: the number of edges attached to a single vertex (loops count twice because 
it connects to the same vertex twice)
Degree List: a list of numbers which lists the degrees of each vertex from smallest to largest v: stands for the number of vertices Order: another word for the number of vertices e: stands for the number of edges Euler path: uses every edge exactly once Euler circuit: uses every edge exactly once, and ends on the same vertex the path started on Hamilton path: uses every vertex exactly once Hamilton cycle: uses every vertex exactly once, and ends on the same vertex the path started on Bipartite Graph: vertices are parallel on opposite sides, and vertices on the same side do not 
connect (there should be no edges between the vertices located on the left, or vice versa)
background image Weight: the number listed on an edge Vertex coloring: Any two vertices that share an edge MUST receive different colors Chromatic number: the fewest number of colors needed to vertex color the graph Edge Coloring: Any two edges that share a vertex MUST be different colors Equation: Using Degrees to Count Edges: add up the degrees of each vertex and then divide by two (gives you the number of edges)  Algorithms for Weight 1. Best Neighbor Algorithm a. Start at a given vertex b. Choose the least weight edge that connects to that vertex
c. Repeat this step until you are back at the original vertex, unless the edge with the 
least weight forms a non­Hamilton cycle (doesn’t end at the same vertex) i. If there is a least weight edge that forms a non­Hamilton cycle, you would  choose the next smallest edge d. Finally, the weight of the Hamilton cycle can be found by listing the weights of  the edges used in the graph and then adding them up 2. Least Weight Algorithm a. List all weights in increasing order b. Begin to use the vertices, starting with the least weights
c. Include the least weight edges, unless it forms a non­Hamilton cycle OR it forms 
a degree 3 vertex i. If a vertex has two edges already connecting to it, then another edge  cannot be connected to that vertex (would form a degree 3 vertex) d. Finally, the weight of the Hamilton cycle can be found by listing the weights of  the edges used in the graph and then adding them up Predicting an Euler Path / Euler Circuit

This is the end of the preview. Please to view the rest of the content
Join more than 18,000+ college students at University of Kentucky who use StudySoup to get ahead
School: University of Kentucky
Department: Applied Mathematics
Course: Intro to Comtemp Math
Professor: Robert Denomme
Term: Fall 2018
Tags: Eulerpath, Eulercircuit, hamiltonpath, hamiltoncircuit, degrees, and vertices
Name: MA111 Final Study Guide
Description: Graph Theory: Includes Euler paths, Euler circuits, Degrees, Vertex Coloring, Hamilton paths, Hamilton circuits, Algorithms for weight, and other important information on the topic
Uploaded: 12/06/2018
4 Pages 98 Views 78 Unlocks
  • Better Grades Guarantee
  • 24/7 Homework help
  • Notes, Study Guides, Flashcards + More!
Join StudySoup for FREE
Get Full Access to UK - Study Guide - Final
Join with Email
Already have an account? Login here
×
Log in to StudySoup
Get Full Access to UK - Study Guide - Final

Forgot password? Reset password here

Reset your password

I don't want to reset my password

Need help? Contact support

Need an Account? Is not associated with an account
Sign up
We're here to help

Having trouble accessing your account? Let us help you, contact support at +1(510) 944-1054 or support@studysoup.com

Got it, thanks!
Password Reset Request Sent An email has been sent to the email address associated to your account. Follow the link in the email to reset your password. If you're having trouble finding our email please check your spam folder
Got it, thanks!
Already have an Account? Is already in use
Log in
Incorrect Password The password used to log in with this account is incorrect
Try Again

Forgot password? Reset it here