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;
25 Cards in this Set
- Front
- Back
Graph |
A set of points, some of all of which are connected by a set of lines. |
|
Simple graph |
A graph that has a maximum of one edge connecting any pair of vertices and no vertex connects to itself. |
|
Multigraph |
A graph that has more than one edge connecting any pair of vertices or has a vertex connected to itself by a loop. |
|
Degree |
Number of edged incident on a vertex. |
|
Adjacent |
Vertices that are joined to each other by an edge. |
|
Order |
The number of vertices in a graph. |
|
Size |
The number of edges in a graph. |
|
Connected |
A graph in which every vertex can be reached from every other vertex by a sequence of edges. |
|
Complete |
A graph in which every vertex is adjacent to every other vertex. |
|
Subgraph |
A graph made from a subset of the vertex set and a subset of the edge set of another graph. |
|
Regular |
A graph in which every vertex has the same degree. |
|
Compliment |
The graph whose vertex set is the same as the original graph, but whose edge set is constructed by vertices adjacent if and only if they were not adjacent in the original graph. |
|
Planar |
A graph in which can be drawn on paper without any edges needing to cross. |
|
Bipartite |
A graph whose vertices can be divided into two disjoint sets, with two vertices of the same set never sharing an edge- that is, no two vertices of the same set are adjacent. |
|
Walk |
A finite sequence of steps from vertex to vertex. We begin at the initial vertex and end at the final vertex. |
|
Length |
The number of edges we walk along. |
|
Trail |
A walk where all of the edges are distinct. Vertices may be visited more than once, but once an edge has been used, it cannot he used again. |
|
Path |
A walk in which all of the edges and all of the vertices are distinct (with the possible exception of the final vertex). |
|
Closed |
A path or trail is closed if the initial and final vertices are the same. |
|
Circuit |
A closed trail. |
|
Cycle |
A closed path. |
|
Eulerian trail |
Trail which uses every edge of the graph exactly once. It’s traversable. |
|
Eulerian (circuit) |
Traversable and begins and ends at the same vertex. |
|
Hamiltonian |
Passes through every vertex exactly once, and begins and ends at the same vertex. It’s not important that every edge be used. |
|
Semi-Hamlitonian |
Path that passes through every vertex exactly once but isn’t closed. |