chapter 2;networks and paths

Question 1

what is a network diagram

Answer 1

a graph of vertices connected by lines

Question 2

what is a vertex

Answer 2

a dot in the diagram which lines of pathways intersect or branch

Question 3

what is an edge

Answer 3

line that connects vertices

Question 4

what is a degree

Answer 4

number of edges that are connected to the dot

Question 5

directed edge

Answer 5

has an arrow and travel only possible in the direction of the arrow

Question 6

undirected edge

Answer 6

all edges undirected, travel is possible in both directions

Question 7

simple network

Answer 7

no multiple edges or loops

Question 8

weighted edge

Answer 8

an edge that has a weight or number assigned to it which has numerical value

Question 9

what is a walk

Answer 9

connected sequence of edges showing a route between vertices where the edges and vertices may be visited multiple times

Question 10

what is a trail

Answer 10

walk with no repeated edges

Question 11

what is a path

Answer 11

walk with no repeated vertices

Question 12

what is a circuit

Answer 12

walk with no repeated edges and starts and ends at the same vertex

Question 13

what is a cycle

Answer 13

walk with no repeated vertices that starts and ends at the same vertex

Question 14

traversable graph

Answer 14

trail that includes every edge

Question 15

non-traversable graph

Answer 15

impossible to find a trail

Question 16

connected graph

Answer 16

every vertex in the graph is accessible from every other vertex in the graph along a path formed by edges of the graph

Question 17

isomorphic graph

Answer 17

same numbers of edges and vertices, corresponding vertices have the same degree and the edges connect to the same vertices

Question 18

weighted graph

Answer 18

weighted edges or an edge with numbers assigned to it that implies it has numerical value (cost, distance, time)

Question 19

eulerian trail

Answer 19

uses every edge of the graph, starts and ends at different vertices

Question 20

eulerian circuit

Answer 20

uses every edge exactly once, starts and ends at the same vertex

Question 21

Hamiltonian path

Answer 21

passes through every vertex once only

Question 22

Hamiltonian cycle

Answer 22

starts and finishes at the same vertex

Question 23

minimum spanning tree

Answer 23

minimum length, connects all vertices together with the minimum total weighting for the edges

Question 24

shortest path

Answer 24

between two vertices in a network is the path where the sum of the weights of its edges minimised