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;
48 Cards in this Set
- Front
- Back
A graph with no odd vertices has a...
|
Euler circuit
|
|
A graph with exactly 2 odd vertices has a...
|
Euler path
|
|
A graph where every vertex has a degree of at least n/2 has a...
|
Hamilton circuit
|
|
The number of edges that touch a vertex
|
Degree
|
|
Edges that share a vertex
|
Adjacent Edges
|
|
Vertices that share an edge
|
Adjacent Vertices
|
|
A point where two edges intersect
|
Vertex
|
|
A connection between two vertices
|
Edge
|
|
A graph were there is a path from any one vertex to any other vertex
|
Connected graph
|
|
A graph where every vertex is adjacent to every other vertex
|
Complete graph
|
|
A graph with directed edges
|
Digraph
|
|
Two or more edges adjacent to the same pair of vertices
|
Multiple Edges
|
|
A edge that makes a vertex adjacent to itself
|
Loop
|
|
A graph with loops or multiple edges
|
Multigraph
|
|
A matrix that describes the connections from each vertex to every vertex
|
Adjacency Matrix
|
|
A graph with 3 or more odd vertices has...
|
Nothing Euler
|
|
Travel every edge of the graph once and only once and return to starting vertex
|
Euler circuit
|
|
Travel every edge of the graph once and only once but start and stop at different vertices
|
Euler path
|
|
Travel to every vertex of the graph once and only once and return to starting vertex
|
Hamilton circuit
|
|
Travel every vertex of the graph once and only once but start and stop at different vertices
|
Hamilton path
|
|
Any part of a graph
|
Subgraph
|
|
Every graph must have an _______ number of odd vertices
|
Even
|
|
The sum of all the vertex degrees for a graph must be ________
|
Even
|
|
Adding an edge to a graph raises the sum of the vertex degrees by ______
|
Two
|
|
A complete diagraph can be called a
|
Tournament
|
|
Duplicating multiple edges in a graph to make a Euler circuit
|
Eulerize
|
|
A vertex with a positive in-degree and zero out-degree
|
Receiver
|
|
A vertex with positive out-degree and zero in-degree
|
Transmitter
|
|
The number of directed edges leaving from a vertex
|
Outdegree
|
|
The number of directed edges leading into a vertex
|
Indegree
|
|
The minimum amount of time required for a task to be ready to begin
|
Earliest Start Time
|
|
The longest path through a project digraph
|
Critical Path
|
|
A sequence of vertices in a project digraph where any delay for any vertex would increase the project completion time
|
Critical Path
|
|
To find the EST, ______ from the start of the graph. If there are multiple routes, choose the ______ number.
|
Add, Higher
|
|
Any graph with numbers on the edges
|
Weighted graph
|
|
The minimum number of colors needed to color a graph
|
Chromatic Number
|
|
Two graphs that share the same relationships between vertices and edges, but look different
|
Isomorphic
|
|
Always an even number and equal to twice the number of edges (2E)
|
Sum of Degrees (SOD)
|
|
A sub graph that only contains the relationships between vertices and edges that do not exist in the parent graph.
|
Complement Graph
|
|
A graph that can be drawn with no edges crossing.
|
Planar Graph
|
|
A graph that can separate the vertices into two groups, where each group of vertices is only adjacent to the other group
|
Bipartite Graph
|
|
A method which produces a quick and reasonable solution
|
Heuristic Method
|
|
Connected graph with no cycles
|
Tree
|
|
Any path that can begin and end at the same vertex
|
Cycle
|
|
Set of multiple tree graphs
|
Forest
|
|
A vertex with degree 1 in a tree
|
Leaf
|
|
A chosen vertex where all edges are directed away from it.
|
Root
|
|
A connected subgraph of a parent graph, that contains every vertex from the parent graph
|
Spanning Tree
|