network concepts

Question 1

what is a network?

Answer 1

a network is a term to describe a group or system of interconnected objects. it consists of vertices and edges. the edges indicate a path or route between two vertices.

Question 2

what is a vertex on a network?

Answer 2

a vertex is a point (or dot) at which lines intersect or branch

Question 3

what is an edge on a network?

Answer 3

an edge is a line that connects vertices

Question 4

what is a loop in a network?

Answer 4

a loop starts and ends at the same vertex, counting as one edge but contributing two to the degree of the vertex

Question 5

what is a directed edge in a network?

Answer 5

a directed edge, also called an arc, has an arrow which indicates the only way in which travel can be directed

Question 6

what is an undirected edge in a network?

Answer 6

an undirected edge does not have an arrow, therefore meaning that travel can be directed either way along the edge

Question 7

what is a directed network?

Answer 7

a directed network is a network in which all of the edges are directed, and travel can only happen in the way that the edges indicate

Question 8

what is an undirected network?

Answer 8

an undirected network is a network in which the edges are not directed, and travel can happen in any direction

Question 9

what is the degree of a vertex in a network?

Answer 9

the degree of a vertex in a network corresponds to the number of edges that connect to a vertex

Question 10

what is a walk in a network?

Answer 10

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

Question 11

what is a trail in a network?

Answer 11

a trail in a network is a walk with no repeated edges

Question 12

what is a path in a network?

Answer 12

a path in a network is a walk with no repeated vertices

Question 13

what is a circuit in a network?

Answer 13

a circuit in a network, also called a closed trail, is a walk with no repeated edges that starts and ends at the same vertex

Question 14

what is a cycle in a network?

Answer 14

a cycle in a network is a walk with no repeated vertices that starts and ends at the same vertex

Question 15

what is a connected graph?

Answer 15

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

Question 16

what are isomorphic graphs?

Answer 16

two graphs are isomorphic (equivalent) if:
* they have the same number of edges and vertices
* corresponding vertices have the same degree and the edges connect to the same vertices

Question 17

what is a weighted graph?

Answer 17

a weighted graph is a network that has weighted edges, meaning edges with numbers assigned that imply some numerical value such as cost, distance or time

Question 18

what is a tree on a network?

Answer 18

a tree is a connected graph that contains no cycles, multiple edges or loops

Question 19

what is a spanning tree on a network?

Answer 19

a spanning tree is a tree that connects all of the vertices on a graph

Question 20

what is a minimum spanning tree on a network?

Answer 20

a minimum spanning tree is a spanning tree that takes up the minimum length possible on a network, whilst connecting all of the vertices

Question 21

what is Prim’s algorithm?

Answer 21

Prim’s algorithm is a set of rules to determine a minimum spanning tree for a graph:
1. choose a starting vertex
2. inspect the edges starting from the starting vertex and choose the one with the lowest weight
3. inspect all of the edges starting from both of the vertices you have in the tree so far; choose each edge with the lowest weight, ignoring edges that would connect the tree back to itself
4. repeat step 3 until all of the vertices are connected

Question 22

what is the shortest path in a network?

Answer 22

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