2.1 Introduction to Walks

Walks

  • A walk is a sequence of edges linking connected vertices in a graph.
  • Walks can have repeated vertices and edges.
  • Walks can be denoted in a written form by listing the vertices, in order, with a dash between each.
  • Walks are shown graphically as a continuous line along each relevant edge. Arrows are placed along the line to show direction.

Example

The walk A-C-D-A-C is shown in the below graph:

Connected Graph

Read More »2.1 Introduction to Walks

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