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
Comp 3 2.5
Graphs and Trees
| Question | Answer |
|---|---|
| Graph | a diagram consisting of circles, called vertices, joined by lines, called edges or arcs; each edge joins exactly two vertices |
| Neighbours | two vertices are neighbours if they are connected by an edge |
| Degree of a vertex | the number of neighbours for that vertex |
| Label or Weighted graph | a graph in which the edges are labelled or given a value called weight |
| Automation | turning an abstraction into a form that can be processed by computer |
| Directed graph or digraph | a diagram consisting of circles, called vertices, joined by directed lines, called edges |
| Simple graph | an undirected graph without multiple edges and in which each edge connects two different vertices |
| Explorer's Problem | the solution finds a route that traverses each arc exactly once before returning to the starting point |
| Traveller's problem | the solution finds a route that visits each vertex exactly once before returning to the starting point |
| Closed path or circuit | a sequence of edges that starts and ends at the same vertex and such that any two successive edges in the sequence share a vertex |
| Cycle | a closed path in which all the edges are different and all the intermediate vertices are different |
| Tree | a connected undirected graph with no cycles |
| Rooted tree | a tree in which one vertex has been designated as the root and every edge is directed away from the root |
Created by:
Masterniket
Popular Computers sets