Networking Definitions

Question 1

ADJACENCY MATRIX

Answer 1

A square matrix showing the number of edges joining each pair of vertices in a graph

Question 2

ADJACENT VERTICES

Answer 2

vertices that are joined by an edge

Question 3

BRIDGES

Answer 3

an edge in a connected graph that, if removed, leaves the graph disconnected

Question 4

CIRCUIT

Answer 4

is a walk that has no repeated edges and starts and ends at the same vertex

Question 5

CLOSED SEQUENCE

Answer 5

a sequence that starts and finishes at the same vertex

Question 6

CONNECTED GRAPHS

Answer 6

is when there is a path between every pair of vertices

Question 7

CYCLE

Answer 7

is a walk that has no repeated vertices and starts and ends at the same vertex

Question 8

DEGREE

Answer 8

the number of edges attached to a vertex. A loop counts as degree of 2

Question 9

EDGE

Answer 9

a line joining one vertex to another or itself (loop)

Question 10

EULERIAN CIRCUIT

Answer 10

is an Euler trail that starts and finishes at the same vertex. It must have an even degree at every vertex

Question 11

EULERIAN TRAIL

Answer 11

passes along every edge once, starting at one vertex and finishing at another. A network must be connected and have exactly two vertices of odd degree, with the remaining vertices having even degree

Question 12

EULERS FORMULA

Answer 12

is V + F = E + 2 relates the number of vertices, faces and edges in a connected graph

Question 13

FACE

Answer 13

area in a graph that can only be reached by crossing an edge. The area surrounding a graph is a face

Question 14

HAMILTONIAN CYCLE

Answer 14

a Hamilton path that starts and finishes at the same vertex

Question 15

HAMILTONIAN PATH

Answer 15

passes through every VERTEX once, it may not use all edges

Question 16

ISOLATED VERTEX

Answer 16

a vertex with no edges incident to it - ie a vertex on its own.

Question 17

ISOMORPHIC GRAPHS

Answer 17

can look different but be the same. They have the same number of edges and vertices. Corresponding vertices have the same degree and the edges connect the same vertices

Question 18

LOOP

Answer 18

an edge in a graph that joins a vertex to itself. Degree = 2. Edge = 1

Question 19

MINIMUM SPANNING TREE

Answer 19

spanning tree of minimum length. For a given connected graph, there may be more than one minimum spanning tree

Question 20

MULTIPLE EDGES

Answer 20

more than one edge connects the same two vertices in a graph

Question 21

NETWORK

Answer 21

a weighted graph in which the weights are physical quantities (e.g. distance, time, cost)

Question 22

OPEN SEQUENCE

Answer 22

a sequence that does not start and finish at the same vertex

Question 23

PATH

Answer 23

is a walk with no repeated vertices or edges

Question 24

PLANAR GRAPH

Answer 24

graph that can be drawn in such a way that no two edges intersect, except at the vertices.

Question 25

PRIMS ALGORITHM

Answer 25

used to determine a minimum spanning tree in a connected graph.

Question 26

SIMPLE GRAPH

Answer 26

a graph with no loops or multiple edges.

Question 27

SPANNING TREE

Answer 27

a subgraph of a connected graph that contains ALL the vertices of the original graph, but without any multiple edges, circuits or loops.

Question 28

SUBGRAPH

Answer 28

part of a graph that is also a graph in its own right

Question 29

TRAIL

Answer 29

is a walk with no repeated edges

Question 30

TRAVERSABLE GRAPHS

Answer 30

a path through the network along the edges, using each edge only once

Question 31

TREE

Answer 31

a connected graph with no circuits, multiple edges or loops. If n vertices then (n - 1) edges.

Question 32

VERTICES

Answer 32

the dots in a graph

Question 33

WALKS

Answer 33

a sequence of edges, linking successive vertices, which connects two different vertices in a graph

Question 34

WEIGHTED GRAPHS

Answer 34

a graph in which a number representing the size of some quantity is associated with each edge