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