HoB icon

Networks

Two-dimensional geometric network (or graph)

Questioning is the foundation of all learning.
The first step in rejecting not knowing is to ask, why?
Sweetland

Introduction

This article explores two-dimensional networks.

Three networks

Which of these networks can be traced without lifting a pen or finger or repeating movement along an edge?

Square - YES or NO?

House -

X box -

X box house -

Momre exploration

How about these networks?

Network examples 2

Three more.

Network examples 3

Create some of your own!

 

Let's analyze networks!

Can we determine which can or can't be traced without tracing them?

Is there pattern?

Let's collect data and look for a pattern.

Network Edges Nodes

Nodes with

1 edge

Nodes

with 2 edges

Nodes

with 3 edges

Number

even edge nodes

Number

odd edge nodes
5 4 0 2 2 2 2
7 5 0 3 2 2 3

 

 

              

 

 

              

 

 

              

 

 

              

 

 

              

 

 

              

 

 

              

 

 

              

 

Hint:

Whether it can be traced depends entirely on the connectivity of its nodes and the number of edges (lines) meeting at the points (nodes).

Let's dig a little deeper

You may have noticed that those that can be traced, can traced in a couple of ways. They can be completely traced back to the starting position in a single continuous line without lifting your pencil or retracing any edge.

And ones that start and stop in different places.

Let's define what we know so far.

Definitions

Eulerian network is a network that can be traced if you can begin at an edge and draw the entire graph without lifting up your pencil or going over an edge twice.

Based on these conditions, a full trace can result in two outcomes: a circuit or path.

A Euler Path is a path that goes through every edge of a graph exactly once. It has a distinct start and finish. A drawing where you start at one of the vertex and finish at another. (like the house).

A Euler Circuit is a Euler path that begins and ends at the same vertex. A continuous loop. (A figure-8 where every node has an even number of intersecting lines).

 

How can we determine if a network will have a path or circuit?

You may have an idea from the data in the table above. If not you might want to consider these hints. Or review the data and add some more.

 

Hint

Review the table for the following information.

  • Count the nodes.
  • Count the number of edges for each of the nodes.
  • Count the number of lines (edges) connected to a specific node (point), These are called its degree.
  • What do you know about networks with all even amounts of edges at their node?
  • Are there any networks with an odd number of edges in which there is a complete path or circuit?
  • If so how many of them in a Euler Path and Euler Circuit?

 

 

 

 

 

Spoiler alert!

Summary

Zero odd vertices: The network can be traced and you will end up exactly where you started. This is called an Eulerian Circuit.

Exactly two odd vertices: The network can be successfully traced, but you must start at one odd vertex and end your tracing at the other.

More than two odd vertices: The network cannot be traced in a single continuous line.

 

 

Check out the Konigsberg Bridge Problem and see if you can explain it with a Euler Path & Circuit.

 


Top