ACMGM079

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

Complete Graph

Read More »1.2 Further Concepts for Network Graphs