D1 Flashcards Preview

Further Maths Definitions > D1 > Flashcards

Flashcards in D1 Deck (19)
Loading flashcards...
1

What is a graph?

A set of vertices connected by arcs.

2

What is the weight of an arc?

The number/length associated with the arc.

3

What is the degree/valency of a vertex?

The number of arcs connected to it.

4

What is a path?

A sequence of arcs leading from one vertex to another in which no vertex is repeated.

5

What is a cycle?

A closed path between vertexes.

6

When is are two vertices connected?

If there is an arc between them.

7

When is a graph connected?

When all of the vertices are connected.

8

What is a directed edge?

An arc with a direction associated to it.

9

What is a tree?

A connected graph with no cycles.

10

What is a spanning tree?

A subgraph that includes all of the vertices of the graph and is also a tree.

11

What is a complete/connected graph?

A graph in which all of the vertices are connected to each other.

12

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.

13

What is a matching?

The pairing of some elements in a bipartite graph.

14

What is a complete matching?

When all of the elements are paired.

15

What is a subgraph?

A graph whose vertices belong to a larger graph.

16

What is a minimum spanning tree?

A spanning tree such that the total length of its arcs is as small as
possible

17

How do you use Kruskal's Algorithm?

-Choose shortest edge
- Choose next shortest edge that doesn't form cycle. (reject etc)

18

How do you use Prim's Algorithm?

-Choose vertex
- Choose shortest edge from vertex to vertex not in network

19

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.