Definitions for D1 Flashcards
(8 cards)
1
Q
What is a graph?
A
A graph consists of points which are connected by lines
2
Q
What is a weighted graph?
A
This is when a graph has a number associated with each edge.
3
Q
What is the degree/valency of a vertex?
A
This is the number of edges incident to it.
4
Q
What is a cycle?
A
A closed path
5
Q
What is a tree?
A
A connected graph with no cycles
6
Q
What is a minimum spanning tree?
A
A spanning tree where the total length of its arcs is as small as possible.
7
Q
What is a bipartite graph?
A
A bipartite graph consists of two sets of vertices, X, and, Y. The edges only join vertices in X to vertices in y, not vertices within a set.
8
Q
What is a matching?
A
A matching is the pairing of some or all of the elements of one set, X, with elements of the second set,Y.
