D1 Flashcards
What is a graph?
A set of vertices connected by arcs.
What is the weight of an arc?
The number/length associated with the arc.
What is the degree/valency of a vertex?
The number of arcs connected to it.
What is a path?
A sequence of arcs leading from one vertex to another in which no vertex is repeated.
What is a cycle?
A closed path between vertexes.
When is are two vertices connected?
If there is an arc between them.
When is a graph connected?
When all of the vertices are connected.
What is a directed edge?
An arc with a direction associated to it.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
A subgraph that includes all of the vertices of the graph and is also a tree.
What is a complete/connected graph?
A graph in which all of the vertices are connected to each other.
What is a bipartite graph?
A graph consisting of two sets of vertices, X & Y. Arcs can only join between the groups not within them.
What is a matching?
The pairing of some elements in a bipartite graph.
What is a complete matching?
When all of the elements are paired.
What is a subgraph?
A graph whose vertices belong to a larger graph.
What is a minimum spanning tree?
A spanning tree such that the total length of its arcs is as small as
possible
How do you use Kruskal’s Algorithm?
- Choose shortest edge
- Choose next shortest edge that doesn’t form cycle. (reject etc)
How do you use Prim’s Algorithm?
- Choose vertex
- Choose shortest edge from vertex to vertex not in network
Give three differences between Prim’s and Kruskal’s.
- Prim starts with vertex, Kruskal with edge.
- Prim goes along nodes, Kruskal steps independent.
- Prim’s must have connected graph.
