Graphs

Question 1

A graph

Answer 1

Has a set of verticies

Has a set of edges

Question 2

An edge

Answer 2

Has a vertex at each end

Question 3

A loop

Answer 3

Where an edge has the same vertex at each end

Question 4

The degree of a vertex

Answer 4

How many edges it has attached to it

Question 5

Simple graph

Answer 5

A graph where there is no loops and each node can only have one edge

Question 6

A walk

Answer 6

A sequence of edges in which the next edge is the beginning of the next

Question 7

A trail

Answer 7

This is a walk but with no edges repeated

Question 8

A path

Answer 8

This is a trail but no vertex are repeated

Question 9

A cycle

Answer 9

This is a closed path (the end of the last edge is the start of the first)

Question 10

A Hamiltonian cycle

Answer 10

This is a cycle which visits every vertex

Question 11

A connected graph

Answer 11

Where there is a path between every pair of vertex

Question 12

A tree

Answer 12

A simple connected graph with no cycles

Question 13

A digraph

Answer 13

A graph in which at least one edge has a direction associated with it

Question 14

A complete graph

Answer 14

A simple graph in which every pair of verticies is connected by an edge

Question 15

An incidence matrix

Answer 15

A way of representing a graph by a matrix

Question 16

Isomorphic graphs

Answer 16

Where two graphs are the same but one is stretched to look different

Question 17

A planar graph

Answer 17

A graph that can be drawn without any edges crossing

Question 18

A bipartite graph

Answer 18

This is a graph where the verticies fall into two sets and in which each edge has a vertex from one set at one end and from the other set from the other end