Question

a) Define a simple graph, a multigraph, a pseudograph, a directed graph, and a directed multigraph.

b) Use an example to show how each of the types of the graph in part (a) can be used in modeling. For example, explain how to model different aspects of a computer network or airline routes.

Short answer

a)The following terms simple graph, a multigraph, a pseudograph, a directed graph, and a directed multigraph are defined.

b)The examples to show how each of the types following terms simple graph, a multigraph, a pseudograph, a directed graph, and a directed multigraph can be used in modeling is given below.

Step-by-step solution

a) Step 1: Definitions

Simple Graph

A simple graph is defined as an undirected graph with no multiple edges or loops.

Multigraph

A multigraph is defined as an undirected graph that may contain multiple edges but no loops

Pseudograph

Pseudograph is defined as an undirected graph that may contain multiple edges and loops.

Step 2: Definitions for directed graphs

Directed graphs

Directed graphs are defined as a set of vertices together with a set of directed edges each of which is associated with an ordered pair of vertices.

Directed multigraphs

The directed multigraphs are defined as a graph with directed edges that may contain multiple directed edges

b) Step 3: Examples

Simple Graph

A friends network (Facebook, Instagram, etc)

Multigraph

Bridges between islands (bridges of Konigsberg); since you may have multiple bridges between two islands but not a single bridge to the same island.

Pseudograph

Websites and their hyperlinks; where a website with a hyperlink to itself would be a loop.

Step 4: Examples for directed graphs

For such graphs applications, we take edge lengths as distances and the vertices as places with the lines being links between them:

Directed graph

An airline route

Directed multigraph

A road network