Network Definitions

OCR MEI D1 for all those who are with that stupid exam board XD


Nodes and Arcs

Nodes (Vertices)


Arcs (Edges)


1 of 6


  • A set of nodes together with a set of edges
2 of 6

More about Nodes and Arcs

  • An edge has a vertex or node at each end. If the vertex is the same one it is called a loop
  • The degree/order of a vertex is how many lines there are coming off it
  • A simple graph has no loops or double edges
3 of 6

Walks, Trails and Paths

  • A walk is a sequence of edges in which the end of one is the start of another
  • A trail is a walk in which no edge is repeated
  • A path is a trail in which no vertex is repeated
4 of 6

Cycles and Hamilton Cycles

  • A cycle is a closed path where the end node is the start node
  • A Hamilton Cycle is a cycle that visits every node
5 of 6

More on Networks

  • A graph is connected if there exists a path between every pair of nodes
  • A tree is a simple connected graph with no cycles
  • A diagram is a graph with direction
  • A complete graph is a graph which has an edge between every pair of nodes
  • An isomorphic graph is when two graphs can be redrawn to be the same
  • A planar graph can be drawn without any edges crossing
  • A bipartite graph is a graph where the nodes are split into 2 groups and the edges go from one group to the other
6 of 6


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »