Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
23 Cards in this Set
- Front
- Back
|
Graph
|
Collection of vertices and edges
|
|
|
Adjacent
|
Two vertices connected with an edge.
|
|
|
Degree of vertex
|
Number of edges meeting at the vertex.
|
|
|
Path
|
Open trip along edges of a graph. Starts and ends at different points.
|
|
|
Trip
|
Adjacent edges. Each edge traveled once and only once.
|
|
|
Open
|
Starts and ends at different points.
|
|
|
Lenght of path
|
Number of edges of that path
|
|
|
Circuit
|
A closed path. Starts and ends at the same point.
|
|
|
Connected graph
|
There is a path between any two vertices.
|
|
|
Bridge
|
Edge whose removal maves a connected graph, disconnected.
|
|
|
Euler path
|
Connected graph that travels through all the edges of a graph. Has two odd vertices.
|
|
|
Euler circuit
|
Circuit that travels through every edge of the graph. Starts and ends at the same vertex. No odd vertices.
|
|
|
Euler Circuit Thm
|
1. If Graph is connected and every vertex is even. It has a Euler circuit.
2. If has any odd vertices, it doesn't have a Euler circuit. |
|
|
Euler Path Thm
|
1. Graph is connected and has two odd vertices, it has a Euler path. Must start and end at odd vertices.
2. If it has more than 2 odd vertices, it cant have an Euler path. |
|
|
Eulers sum of Degrees Thm
|
1. Sum is twice the number of edges in graph.
2. Graph always has an even number of odd vertices. |
|
|
Fleury's Algorithm
|
1. Graph is connected.
2. Has all even vertices(euler circuit) or has two odd vertices (euler path) 3. Choose starting vertex or start at odd vertices. 4. Travel the bridges last. 5. Done when all the edges are traveled. |
|
|
Exhaustive route
|
Travels through each edge at least once. Can travel edges more than once.
|
|
|
Semi-eulerization
|
Add edges but leave two verticies odd.
|
|
|
Hamiliton path
|
Path that includes each vertex. Once and only once.
|
|
|
Hamiliton circuit
|
Circuit that includes all the verticies. Once and only once.
|
|
|
Reference point
|
Starting vertex
|
|
|
Complete graph
|
Every pair of vertices is adjacent. Every possible pair of vertices has an edge joining them.
|
|
|
# degress of Kn
|
N(N-1)/2
|
