17950423
Description
Flashcards by Nathanael Jenkins, updated more than 1 year ago
|
Created by Nathanael Jenkins
over 6 years ago
|
|
| Question | Answer |
| Graph | A finite set of points connected by lines |
| Edge | Joins one vertex to another, or starts and ends at the same vertex (a loop) |
| Simple | No loops or multiple edges |
| Connected | Every vertex is connected by a single edge or sequence of edges to every other vertex |
| Disconnected | Can be separated into two separate 'pieces' |
| Complete | Every vertex is connected to every other vertex by one edge -- Denoted K |
| Subgraph | Part of a graph which is itself a graph |
| Planar | A graph which can be drawn without any edges crossing over |
| Degree (Vertex) | The number of edges which start or finish at a vertex (count loops twice) |
| Handshaking Theorem | Σ(degrees of vertices) = 2 (number of edges) |
| Digraph | A graph whose edges have a direction |
| Bipartite | A graph with two discrete sets of vertices, with no edges connective vertices in the same set |
| Complete Bipartite | A bipartite graph in which every vertex in one set is connected to every vertex in the other set by one edge -- Denoted K |
| Isomorphic | Identical graphs which have been drawn in different orientations |
| Walk | A sequence of edges and vertices in which the end of one edge is the beginning of the next |
| Trail | A walk with no repeated edges (in either direction) |
| Path | A walk with no repeated vertices (except that the first may be the last) |
| Cycle | A closed walk, trail or path -- Finishes at the same vertex where it started |
| Eulerian Trail | Crosses every edge of a graph exactly once -- Has no vertices with an odd degree |
| Semi-Eulerian | Has only two odd vertices; only transversible if you start and finish at the odd vertices |
| Hamiltonian Cycle | A closed path which passes through every vertex of a graph |
| Tree | A connected graph which contains no cycles |
| Spanning Tree | A subgraph which includes all vertices of the original graph, and is also a tree |
Want to create your own Flashcards for free with GoConqr? Learn more.