 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

UK - MATH 111 - Study Guide - Final

This preview shows pages 1 - 2 of a 4 page document. to view the rest of the content 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) 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
##### 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
4 Pages 98 Views 78 Unlocks
• Notes, Study Guides, Flashcards + More!
×

I don't want to reset my password

Need help? Contact support

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