A graphs is called simple if it contains no loops and if there is a maximum of one edge joining any pair of distinct vertices.

A subgraph is a graph made from a subset of the vertices and edges of another graph. For instance, the graph on the right below is a subgraph of the graph on the left.

If it is possible to travel from every vertex to every other vertex by following edges on an undirected graph it is called connected, otherwise it is called disconnected.

If it is possible to travel from every vertex to every other vertex by following edges in the correct direction on a directed graph, the graph is strongly connected.

A simple undirected graph in which every vertex is connected by an edge to every other vertex is called a complete graph. If a complete graph has n vertices we notate it as k_n. The complete graph below is a k₄ graph.

A weighted graph has numbers assigned to its edges. The numbers could represent cost, time, or distance required to travel along that edge. Lengths of edge are not proportional to their weight.

Below is a weighted adjacency table for the weighted graph above.

This summarises the weights on a graph. The “-” symbol indicates that vertices are not adjacent. In a weighted undirected graph, the weighted adjacency table will always be symmetric about the leading diagonal.

For a weighted directed graph as below the weighted adjacency table may not be symmetrical (as shown):

Exercise

Answers