Chapter 5 Terms Flashcards
The Konigsberg Puzzle
- Unsolvable bridge puzzle
Think of graphs as __________.
- Connections
Graph Theory
- Illustrates and analyzes connections
Graph
- A set of points and line segments that connect the vertices
Vertices
- The points on a graph
Edges
- The line segments that connect the vertices
Null Graph
- Vertices are totally disconnected . . .
Connected Graph
- Where each vertices is touching another one .-.-.
Not Connected Graph
- Each vertical is touching another but they are not connected . .-. .-.
A Complete Graph
- Every possible edge is drawn
To See if Graphs Are Equivalent
- Count the vertices
- Count the edges
- Write down the names of the connections
Path
- Movement from one vertex to another via edges
Closed Path
- When a path ends where it started
- AKA: circuit
Euler Circuit
- A circuit that uses every edge but never the same edge twice
Degree
- The number of edges coming from a vertex
An euler circuit is possible if…
- The no. of edges coming from every vertex is even
Euler Path
- A route that uses every edge but you do not have to end up where you started
- Will start and end at the ODD verticals
A euler path is possible if…
- If two (and only two) verticals are odd
Hamiltonian Circuit
- The path that visits each vertex once and returns to the starting vertex, without visiting any vertex twice
A Hamiltonian circuit exists if…
- Every vertex has a degree of at least n/2
- “n” = the number of verticals
Weighted Graph
- A graph in which each edge is associated with a value
Shortcut algorithms only apply to…
- Complete graphs
The Greedy Algorithm Steps
- Choose a vertex and travel across the connecting edge with the smallest weight
- Reach the next vertex and travel to an unvisited one by using the edge with the smallest weight
- Continue
- Get to every vertex once
- Return to where you started
Edge-Picking Algorithm Steps
- Mark edge of smallest weight
- Mark edge of next smallest weight
- Do not complete a circuit
- Do not mark an edge more that twice
- Continue until you cannot make any edges
Planar Graph
- A graph that can be drawn so that no edges intersect each other
Planar Drawing
- A graph that is drawn in such a way that no edges touch
Steps to Identify a Planar Graph
- Name the vertices
- Find a Hamiltonian Path
- Make a basic loop of these vertices
- Draw in the remaining edges
* If all else fails, guess and check
Steps to Identify a Non-planar Graph
- Name the vertices
- Find a Hamiltonian Path
- Make a basic loop of these vertices
- Draw in the remaining edges
* If all else fails, guess and check
Euler’s Formula
v + f = e + 2
Steps to Determine How Many Colors Are Needed to Color in a Graph
- Create a graph
- Erase the boundaries
- Determine the number of colors needed so that no boundaries share a color
Ever PLANAR graph is 4-colorable
- Well, that’s a cool fact!
What do these words mean:
- 2-colorable
- 3-colorable
- 4-colorable
- If the map uses 2 colors
- If the map uses 3 colors
- If the map uses 4 colors
Chromatic Number
- The number of colors needed for a non-planar graph
A graph is 2-colorable if…
- It has no circuits that consist of an odd number of vertices
