Introduction to Networks

TL;DR

Networks are collections of points (vertices) connected by lines (edges), used to model relationships in many real-world situations. We use networks to understand connections like roads, friendships, or computer systems. Key concepts include identifying vertices, edges, paths, and understanding connectivity.

1. The Mental Model

Imagine a map where cities are dots and roads are lines connecting them. That's essentially a network! It helps us visualise how different things are linked and how you can get from one point to another.

2. The Core Material

Networks, sometimes called graphs, are a powerful way to represent connections. Let's break down the main parts:

Vertices (or Nodes)

Photo by Brett Sayles on Pexels

These are the individual points in your network. Think of them as the 'things' you're connecting.
* In a road network, cities or intersections are vertices.
* In a social network, people are vertices.
* In a computer network, individual computers or servers are vertices.

Edges (or Links)

Photo by wal_ 172619 on Pexels

These are the connections between the vertices. They show how the 'things' are related.
* A road between two cities is an edge.
* A friendship between two people is an edge.
* A cable connecting two computers is an edge.

Edges can be:
* Directed: Meaning the connection only goes one way (e.g., a one-way street). We show this with an arrow on the edge.
* Undirected: Meaning the connection goes both ways (e.g., a two-way street). We show this with a simple line.
* Weighted: Meaning the edge has a value or cost associated with it (e.g., distance of a road, time taken, cost of a flight).

Paths and Cycles

Photo by indra projects on Pexels

• A path is a sequence of edges that connects one vertex to another.
• A cycle is a path that starts and ends at the same vertex, visiting other vertices in between.

Connectivity

• A network is connected if there's a path between any two vertices. If you can get from anywhere to anywhere else, it's connected.
• If a network isn't connected, it means it has separate components (groups of connected vertices).

Here's a simple example:

graph LR
    A["Vertex A"] --> B["Vertex B"]
    B --> C["Vertex C"]
    A --> C
    D["Vertex D"]
    C -- "Weighted (10km)" --> D

In this diagram:
* A, B, C, D are the vertices.
* A --> B is a directed edge.
* B --> C is another directed edge.
* A --> C is a directed edge.
* C -- "Weighted (10km)" --> D is an undirected, weighted edge.
* A path from A to D could be A -> C -> D.
* A cycle could be A -> B -> C -> A.

Degree of a Vertex

Photo by https://kaboompics.com/ on Pexels

The degree of a vertex is simply the number of edges connected to it. If an edge is directed, we talk about in-degree (edges coming into the vertex) and out-degree (edges going out of the vertex).

3. Worked Example

Let's look at a simple network representing bus routes between four towns: Alton (A), Bude (B), Caster (C), and Durn (D).

Imagine the following routes:
1. Bus from Alton to Bude (and back)
2. Bus from Alton to Caster (one-way only)
3. Bus from Bude to Durn (and back)
4. Bus from Caster to Durn (and back), taking 30 minutes.

Let's identify the network components:

• Vertices: A, B, C, D (the four towns).

• Edges:

  • (A, B) - Undirected (bus goes both ways)
  • (A, C) - Directed (bus goes A to C only)
  • (B, D) - Undirected (bus goes both ways)
  • (C, D) - Undirected and Weighted (bus goes both ways, takes 30 minutes)

• Degree of each vertex:

  • Vertex A: 2 (connected to B and C)
  • Vertex B: 2 (connected to A and D)
  • Vertex C: 2 (connected from A, and to/from D)
  • Vertex D: 2 (connected to B and C)

• Paths:

  • Path from A to D: A -> B -> D.
  • Another path from A to D: A -> C -> D.

This network is connected because you can get from any town to any other town using the bus routes. For example, to get from Bude to Caster, you could go B -> A -> C or B -> D -> C.

4. Key Takeaways

• Networks use vertices (points) and edges (lines) to represent relationships between things.
• Vertices are the individual items, and edges are the connections between them.
• Edges can be directed (one-way), undirected (two-way), or weighted (have a value like distance or time).
• A path is a sequence of edges from one vertex to another; a cycle is a path that returns to its starting point.
• A network is connected if you can find a path between any two vertices.
• The degree of a vertex is the number of edges connected to it.

Common Mistakes to Avoid:
- Mixing up vertices and edges; remember, vertices are the things, edges are the connections.
- Forgetting that an edge can be directed, meaning you can't always travel in both directions.
- Not noticing if a network is disconnected, meaning some parts aren't reachable from others.
- Confusing a path with a cycle; a cycle always ends where it started.

5. Now Try It

Draw a network representing your immediate family (parents, siblings, grandparents).
1. Identify the vertices: Each family member is a vertex.
2. Identify the edges: Draw an edge between two people if they are directly related (e.g., parent-child, sibling-sibling, spouse-spouse). You don't need to use directed edges here, but you can if you want to show parent-child direction.
3. Calculate the degree: For each family member, count how many direct connections they have.
4. Identify a path: Can you find a path from yourself to a grandparent?
5. Identify a cycle (if any): Is there any path that starts and ends with the same person, going through others?

Success looks like a clear diagram with labels for family members and lines showing their relationships, and your written answers to the questions above.