Graphs and networks

Question 1

a walk

Answer 1

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

Question 2

Path

Answer 2

A walk in which no vertex is visited more than once

Question 3

Cycle

Answer 3

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

Question 4

Order/Degree/Valency

Answer 4

The number of edges incident to a vertex

Question 5

Vertices

Answer 5

A singular point on a graph where edges can meet

Question 6

Arcs

Answer 6

A link between two vertices (or the same one) that can be traversed

Question 7

Simple Graph

Answer 7

There are no loops and at most one edge connecting any pair of vertices

Question 8

Sub Graph

Answer 8

A graph where all the vertices and edges belong to the original graph
- A part of it essentially

Question 9

Connected graph

Answer 9

a graph in which all of the vertices are connected by edges

Question 10

Euler’s Handshaking Lemma (2 points)

Answer 10

• In any undirected graph, the sum of the degrees of the vertices is equal to 2 times the number of edges.
• The number of odd nodes must be even for this to be true

Question 11

Loop

Answer 11

An edge that starts and finishes at the same vertex

Question 12

Network/weighted graph

Answer 12

• graph with numbers associated with each edge (its weight)

Question 13

Hamiltonian Cycle

Answer 13

A cycle that includes every vertex

Question 14

Planar Graph

Answer 14

One that can be drawn in a plane such that no two edges meet except at a vertex (no crossing edges)

Question 15

Spanning tree

Answer 15

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

Question 16

Isomorphic graphs

Answer 16

Graphs which show the same information but which may be drawn differently

Question 17

Complete graph

Answer 17

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

Question 18

Adjacency Matrix

Answer 18

Each entry describes the number of arcs joining the corresponding vertex. (a vertex degree table)

Question 19

Distance matrix

Answer 19

The entries represent the weight of each arc, not the number of arcs

Question 20

Eulerian graph

Answer 20

A graph in which all of the vertices have even degree

Question 21

Semi-Eulerian graph

Answer 21

A graph in which all of the vertices except 2 have even degree and the other two are odd

Question 22

A trail

Answer 22

a walk in which no edge is visited more than once

Question 23

tree

Answer 23

a connected graph with no cycles

Question 24

digraph

Answer 24

a graph where some or all of the edges have a specific direction

Question 25

Planarity algorithm

Answer 25

May be applied to any graph that contains a hamiltonian cycle. It provides a method of redrawing a graph to become clear if it is planar or not