1.2 Further Concepts for Network Graphs

Note: if you cannot remember the basics of network graphs, revise notes for 1.1 Basics of Network Graphs.

Simple Graph

  • Graphs which do not contain loops or duplicate edges (i.e. there are no two vertices connected directly by more than one edge).
  • Each vertex has a maximum degree of n-1.
  • A simple graph has a maximum number of edges of \frac {n(n-1)}{2}.
  • Graphs which contain loops or duplicate edges are sometimes called multigraphs.

Example

Picture 1

Complete Graph

Read More »1.2 Further Concepts for Network Graphs

1.1 Basics of Network Graphs

Network Graphs

  • A network graph shows the connections between multiple individuals or locations.
  • It consists of a number of dots, known as vertices (singular: vertex), each representing an individual or location, connected by lines, known as edges.
  • If two vertices are connected by an edge, this indicates the two individuals or locations the vertices represent are directly connected.
  • Examples of situations which can be modelled by network graphs include communication networks (showing which individuals can communicate with each other) and transportation networks (showing which towns are connected via roads, train tracks, etc).

Note: vertices are sometimes known as nodes.

Read More »1.1 Basics of Network Graphs