Definitions about General graph theory not in the Textbook
Quiz yourself by thinking what should be in
each of the black spaces below before clicking
on it to display the answer.
Help!
|
|
||||
|---|---|---|---|---|---|
| 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
🗑
|
Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
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
Created by:
joemch
Popular Computers sets