D1 Definitions

Question 1

Tree

Answer 1

A tree is a connected graph with no cycles

Question 2

Minimum Spanning Tree

Answer 2

A minimum spanning tree is a tree that contains all vertices and the total length of its arcs (weight of the tree) is as small as possible.

Question 3

Bipartite Graph

Answer 3

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.

Question 4

Matching

Answer 4

A Matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y.

Question 5

Degree/Valency

Answer 5

The degree/valency of a vertex is the number of edges incident to it.

Question 6

Path

Answer 6

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.

Question 7

Graph

Answer 7

A graph consists of points, called vertices or nodes, which are connected by lines, called edges or arcs

Question 8

Subgraph

Answer 8

A subgraph is a graph, each of whose vertices and edges belong to the original graph

Question 9

Weighted Graph/Network

Answer 9

If a graph has a number associated with each edge (usually called its weight) then the graph is called a
weighted graph or network.

Question 10

Cycle

Answer 10

A cycle or circuit is a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.

Question 11

Connected Graph

Answer 11

Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.

Question 12

Directed Edges/Digraph

Answer 12

If the edges of a graph have a direction associated with them, they are known as directed edges and the graph is known as a digraph.

Question 13

Spanning Tree

Answer 13

A spanning tree of a graph is a subgraph which includes all the vertices of the original graph and is also a tree.

Question 14

Complete Graph

Answer 14

A graph in which each of the total number of vertices is connected to every other vertex is called a complete graph.

Question 15

Complete Matching

Answer 15

If every member of X is paired with a member of Y the matching is said to be a complete matching.

Question 16

Eulerian

Answer 16

If all the valencies in a graph are even, then the graph is Eulerian.

Question 17

Semi-Eularian

Answer 17

If precisely two valencies are odd, and all the rest are even, then the graph is semi-Eulerian.

Question 18

Traversable

Answer 18

A graph is traversable if it is possible to traverse (travel along) every arc just one without taking your pen from the paper.
A graph is traversable if all the valencies are even.
A graph is semi-traversable if it has precisely two odd valencies.
A graph is not traversable if it has more than two odd valencies.