Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
AQA COMP3 Graphs
Definitions about General graph theory not in the Textbook
| Term | Definition |
|---|---|
| Graph | A finite, discrete set of vertices linked by edges |
| Tree | A connected, undirected graph with no cycles |
| Rooted tree | A tree where one vertex is the starting point, and all points use this as a ‘root’ |
| Directed graph | A graph where each edge has a direction (shown by an arrow) |
| Vertex | A point where two edges connect |
| Edge | A line connecting two vertices |
| Neighbours | Adjacent vertices to a vertex |
| Degree (of a vertex) | The number of edges connected to a vertex |
| Weighted graph | A graph where each edge has been given a weight |
| Simple graph | A graph where there are no loops, and no more than 1 edge per vertex. Each edge connects two different vertices. |
| Path | A route that does not have to visit all edges |
| Circuit | A succession of edges that start and end at the same vertex |
| Cycle | A closed path where all the edges and intermediate vertices are different |
| Undirected graph | A graph with no direction (ie an edge can be traversed either way) |
| Explorer’s problem | The solution finds a route that traverses each ‘road’ (edge) exactly once before returning to the start point |
| Traveller’s problem | The solution finds a route that visits each ‘city’ (vertex) exactly once before returning to the start point |
Created by:
joemch
Popular Computers sets