Graphs and networks

Question 1

What is a graph?

Answer 1

Points (vertices or nodes) which are connected by lines (edges or arcs).
If a graph has a number associated with each edge, then the graph is a weighted graph or network.

Question 2

What is a subgraph?

Answer 2

A graph consisting of edges and nodes belonging to the original graph.

Question 3

What is the degree/valency/order of a vertex?

Answer 3

The number of edges incident to it.

Question 4

What is a walk?

Answer 4

A route through a graph along edges from one vertex to the next.

Question 5

What is a path?

Answer 5

A walk in which no vertex is visited more than once.

Question 6

What is a trail?

Answer 6

A walk in which no edge is visited more than once.

Question 7

What is a cycle?

Answer 7

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

Question 8

What is a hamiltonian cycle?

Answer 8

A cycle that includes every vertex.

Question 9

What is a connected graph?

Answer 9

A graph in which all vertices are connected.

Question 10

What is a loop?

Answer 10

An edge that starts and finishes at the same vertex.

Question 11

What is a simple graph?

Answer 11

A graph in which there are no loops and at most one edge connecting any pair of vertices.

Question 12

What is a digraph?

Answer 12

A graph in which edges have a direction associated with them.

Question 13

What is Euler’s handshaking lemma?

Answer 13

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges.

Question 14

What is a tree?

Answer 14

A connected graph with no cycles.

Question 15

What is a spanning tree?

Answer 15

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

Question 16

What is a complete graph?

Answer 16

A graph in which every vertex is directly connected by a single edge to each of the other vertices.

Question 17

What are isomorphic graphs?

Answer 17

Graphs which show the same information drawn differently.

Question 18

What do the numbers in adjacency matrices show?

Answer 18

The number of arcs joining the corresponding vertices. Put 0 where the headings are the same, unless there is a loop in which case you should put 2.

Question 19

What do the numbers in a distance matrix show?

Answer 19

The weight of each arc between corresponding vertices. Put dashes through the leading diagonal.

Question 20

What is a planar graph?

Answer 20

A graph that can be drawn in a plane such that no two edges meet except at a vertex.

Question 21

How do you execute the planarity algorithm?

Answer 21

1. identify a hamiltonian cycle
2. draw a polygon with vertices labelled to match the ones in the hamiltonian cycle
3. draw edges inside the polygon to match the edges of the original graph
4. make a list of all the edges inside the polygon
5. chose an unlabelled edge and label it I. If all edges are now labelled the graph is planar
6. look at the unlabelled edges that cross the edge just labelled, if none of them cross each other give them all the opposite label. If any of these edges cross each other the graph is non planar.