# Decision 1- definitions

• Created by: eleanor
• Created on: 20-04-15 09:14
Graph
A graph consists of vertices which are connected by arcs
1 of 13
Path
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
2 of 13
Cycle/Circuit
A closed path so that the end vertex of the last edge is the start vertex of the first edge
3 of 13
Connected Graph
A graph in which there is a path between each pair of vertices
4 of 13
Digraph
A graph which contains directed edges
5 of 13
Tree
A connected graph with no cycles
6 of 13
Spanning tree
A sub-graph which include all the vertices and is also a tree
7 of 13
Minimum Spanning Tree
A spanning tree such thatthetotal length of its arcs is as small as possible
8 of 13
Complete Graph
A graph in which each of the vertices is connected to every other vertex
9 of 13
Bipartite Graph
consists of two sets of vertices X and Y. The edges only join vertices in the X to vertices in Y, not vertices in the same set
10 of 13
Alternating Path
A path from an unmatched vertex in one set to an unmatched in the other set,which alternativly uses arcs not in/in the matching
11 of 13
Matching
The pairing of some or all of the elements if one set X, with a member of Y.
12 of 13
Complete Matching
A matching in which every member of X is paired with a member of Y
13 of 13

## Other cards in this set

### Card 2

Path

#### Back

A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once

Cycle/Circuit

Connected Graph

Digraph