10290703
Description
Flashcards by Ezra Dorland, updated more than 1 year ago
|
Created by Ezra Dorland
over 6 years ago
|
|
| Question | Answer |
| Define Graph | A collection of vertices connected by arcs |
| Define subgraph | A part of a graph |
| What is also a type of subgraph? | One that has all vertices but not all arcs |
| Define cycle | A closed path where the end vertex of the last arc is the start vertex of the first arc |
| Define tree | a connected graph with no cycles |
| Define weight | A property arcs may have e.g. cost, distance |
| Define minimum spanning tree | a sub graph in which all vertices are connected without cycles and have the lowest total weight of any spanning tree |
| What is Kruskal's Algorithm? | Sort all arcs in ascending weight Arc with least weight is start of tree If the next lowest arc does not form a cycle, add it Stop when all vertices are connected |
Want to create your own Flashcards for free with GoConqr? Learn more.