Drawing a Network Diagram Revision Notes for HSC SSCE Mathematics Standard

Drawing a Network Diagram

Introduction to network diagrams

Network diagrams are visual representations used to show connections between different objects or people. In everyday life, we encounter many situations involving connections:

Towns are connected by roads
Computers are connected to the internet
Families are connected to each other through relationships
Social media users are connected through their networks

When constructing a network diagram, we use vertices (points) to represent objects or people, and edges (lines) to represent the connections between them. These graphs can be either connected or not connected, depending on whether all parts of the network can reach each other.

infoNote

Network diagrams are powerful tools for modeling real-world scenarios. They help us visualize complex relationships and solve practical problems like finding the shortest route between locations or understanding social connections.

Connected graphs

What is a connected graph?

A connected graph is one where you can travel from any vertex to any other vertex by following the edges of the graph. This means every vertex in the graph is accessible from every other vertex, either through a direct connection or by passing through other vertices along the way.

Think of it this way: if you start at any point in a connected graph, you should be able to reach every other point by following the paths (edges) available to you.

Examples of connected graphs

The following three graphs are all examples of connected graphs:

In each of these graphs, starting from any vertex (such as vertex $A$ ), you can find a path along the edges to reach every other vertex in the graph. The graphs may look different, but they all have this important property of being connected.

Examples of non-connected graphs

In contrast, the following three graphs are not connected:

These graphs are not connected because there is no path along the edges that allows you to travel from some vertices to others. For example, in each graph, starting at vertex $A$ , you cannot reach every other vertex by following the edges.

infoNote

Quick Test for Connectivity: Pick any vertex in the graph and ask yourself: "Can I travel from here to every other vertex by following the edges?" If the answer is yes, the graph is connected. If there's even one vertex you cannot reach, the graph is not connected.

Formal definition

chatImportant

CONNECTED GRAPH

A graph is connected if every vertex in the graph is accessible from every other vertex in the graph along a path formed by the edges of the graph.

Isomorphic graphs

Understanding isomorphic graphs

Different looking graphs can actually contain the same structural information. When this happens, we say that these graphs are equivalent or isomorphic.

The key idea is that isomorphic graphs have the same pattern of connections, even though they might be drawn differently. It's like having the same network, just arranged in different visual layouts.

Examples of isomorphic graphs

The following three graphs look quite different from each other, but they are actually isomorphic:

Each of these graphs has:

The same number of edges ( $5$ )
The same number of vertices ( $4$ )
Corresponding vertices with the same degree
Edges that connect vertices in the same way (e.g., $A$ to $C$ , $A$ to $D$ , $B$ to $C$ , $B$ to $D$ , and $D$ to $C$ )

Examples of non-isomorphic graphs

However, just because graphs have the same numbers of vertices and edges doesn't automatically make them isomorphic. Consider these three graphs:

Although these graphs have the same numbers of edges and vertices, they are not isomorphic. This is because corresponding vertices do not have the same degree, and the edges do not connect the same vertices in each graph.

infoNote

Checking for Isomorphism - A Three-Step Process:

Count vertices and edges (must be equal)
Check that corresponding vertices have the same degree
Verify that edges connect to the same vertices

All three conditions must be satisfied for graphs to be isomorphic!

Formal definition

chatImportant

ISOMORPHIC GRAPHS

Two graphs are isomorphic (equivalent) if:

They have the same numbers of edges and vertices
Corresponding vertices have the same degree and the edges connect to the same vertices

Worked example: Identifying an isomorphic graph

lightbulbExample

Worked Example 3: Identifying an isomorphic graph

Question: Which of the following graphs is not isomorphic to the other three graphs?

Solution:

Step 1: Check that each graph has the same number of vertices and edges.

Every graph has five vertices and seven edges.

Step 2: Check that corresponding vertices have the same degree.

In Graph $2$ , vertex $B$ has degree $2$ and $C$ has degree $3$ . However, in all the other graphs, $B$ has degree $3$ and $C$ has degree $2$ .

Step 3: Check that edges connect to the same vertices.

In graphs $1$ , $3$ and $4$ , the edges are:

$A–B$ , $A–D$ , $A–E$ , $B–C$ , $B–E$ , $C–D$ and $D–E$

These graphs are isomorphic to each other.

Graph $2$ does not have edge $B–E$ and does have edge $C–E$ , which does not appear in the other graphs. This confirms that it is not isomorphic to the others.

Answer: Graph $2$ cannot be isomorphic to any of the other graphs shown.

Weighted graphs

What is a weighted graph?

The edges of graphs represent connections between vertices. Sometimes, we have additional numerical information about these connections that we want to include in our diagram.

A weighted edge is an edge that has a number associated with it. This number represents some numerical value such as:

Distance between locations
Time taken to travel between points
Cost of travelling along that route

Graphs that have numbers associated with each edge are called weighted graphs.

Practical applications

Consider a road network connecting several towns. The weighted graph can show:

Towns as vertices
Roads as edges
Distances along roads as weights (numbers on the edges)

This type of diagram helps us answer questions like "What is the shortest distance between two towns?" or "What is the quickest route to take?"

For example, this weighted graph shows towns connected by roads:

The numbers on the edges represent the distances (in kilometres) along the roads. While it's easy to find the distance between directly connected towns (like Town $A$ to Town $B$ ), we need to calculate the total distance when travelling through multiple towns (such as from Town $F$ to Town $C$ ).

infoNote

Real-World Applications of Weighted Graphs:

Weighted graphs are incredibly useful in practical situations:

GPS navigation systems use them to find shortest routes
Delivery companies use them to optimize routes and minimize costs
Airlines use them to schedule flights and minimize travel time
Network engineers use them to design efficient communication networks

Formal definition

chatImportant

WEIGHTED GRAPH

A weighted graph is a network diagram that has weighted edges, or edges with numbers assigned to them that represent some numerical value such as cost, distance or time.

Worked example: Solving a practical network problem

lightbulbExample

Worked Example 4: Solving a practical network problem

Question: The network diagram below models the tracks in a forest connecting:

A suspension bridge ( $B$ )
A waterfall ( $W$ )
A very old tree ( $T$ )
A fern gully ( $F$ )

Walkers can enter or leave the forest through either gate $1$ ( $G_1$ ) or gate $2$ ( $G_2$ ). The numbers on the edges represent the times (in minutes) taken to walk directly between these places.

a) How long does it take to walk from the bridge directly to the fern gully?

b) How long does it take to walk from the old tree to the fern gully via the waterfall and the bridge?

Solution:

Part a:

Identify the edge that directly links the bridge with the fern gully and read off the time.

The edge is $B–F$ .

The time taken is $12$ minutes.

Part b:

Identify the path that links the old tree to the fern gully, visiting the waterfall and the bridge on the way.

The path is $T–W–B–F$ .

Add up the times along this path:

$\text{Time} = 10 + 9 + 12 = 31$

The time taken is $31$ minutes.

Remember!

bookmarkSummary

Key Points to Remember:

A connected graph allows you to travel from any vertex to any other vertex by following the edges. If you cannot reach all vertices from a starting point, the graph is not connected.
Isomorphic graphs look different but have the same structure. To check if two graphs are isomorphic, verify they have the same number of vertices and edges, corresponding vertices have the same degree, and edges connect the same vertices.
Weighted graphs have numbers on their edges representing values like distance, time, or cost. These weights help solve practical problems like finding shortest routes or minimum travel times.
When solving problems with weighted graphs, identify the relevant path and add up all the weights along that path to find the total distance, time, or cost.
The degree of a vertex is the number of edges connected to it. This is important when determining if graphs are isomorphic.

Drawing a Network Diagram (HSC SSCE Mathematics Standard): Revision Notes