The Central Idea
A network is a collection of entities connected by relationships.
Mathematically, we usually represent a network as a graph
\[ \boxed{G=(V,E)}, \]where \(V\) is the set of vertices and \(E\) is the set of edges.
In communication problems:
- vertices represent devices, people, locations, or states;
- edges represent links, channels, relationships, or permitted transitions.
The central problem is not merely whether two things are connected. We often need to know how they are connected, how much can move through the connections, how quickly information can travel, and what happens when part of the network fails.
Networks as Models
The same mathematical structure can represent many different systems.
| System | Vertices | Edges |
|---|---|---|
| Computer network | Computers, routers, switches | Communication links |
| Social network | People or accounts | Relationships or interactions |
| Transportation network | Intersections or terminals | Roads, tracks, or routes |
| Power network | Generators, substations, loads | Transmission lines |
| Organizational network | People, teams, departments | Communication or dependency links |
Undirected and Directed Communication
An undirected edge represents a connection that can be used in both directions.
For example,
\[ A-B \]may represent a two-way communication link.
A directed edge represents a one-way relationship:
\[ A\rightarrow B. \]Directed networks are useful when communication, influence, permission, or movement is asymmetric.
Weighted Networks
An edge can carry a numerical weight.
In communication networks, a weight might represent:
- latency;
- distance;
- cost;
- capacity;
- reliability;
- energy consumption;
- signal loss.
The meaning of the weight determines how the network should be analyzed.
Adjacency
Two vertices are adjacent when an edge directly connects them.
Suppose the network contains
\[ A-B,\qquad A-C,\qquad C-D. \]Then A is adjacent to B and C.
A is not directly adjacent to D, even though a path from A to D exists.
Degree and Communication Load
In an undirected graph, the degree of a vertex is the number of incident edges.
If vertex A is connected directly to B, C, D, and E, then
\[ \boxed{\deg(A)=4}. \]Degree can provide a simple measure of local connectivity.
A high-degree vertex may serve as an important communication hub, although degree alone does not determine overall network importance.
In-Degree and Out-Degree
In a directed network, we distinguish incoming and outgoing edges.
The in-degree of vertex \(v\) is
\[ \deg^-(v), \]and the out-degree is
\[ \deg^+(v). \]In a communication system, high in-degree may indicate that many sources send information to a node, while high out-degree may indicate broad distribution from that node.
Paths
A path is a sequence of connected vertices.
For example,
\[ A\rightarrow B\rightarrow D\rightarrow F \]is a path from A to F if all three required edges exist.
Communication between two devices may travel through several intermediate vertices before reaching the destination.
Path Length
In an unweighted graph, path length is often measured by the number of edges.
The path
\[ A-B-C-D \]contains three edges, so its length is
\[ \boxed{3}. \]In a weighted network, the path weight is instead the sum of edge weights.
Weighted Path Cost
Suppose a communication route uses links with delays
\[ 4\text{ ms},\qquad 7\text{ ms},\qquad 3\text{ ms}. \]The total path latency is
\[ 4+7+3=\boxed{14\text{ ms}}. \]When latency is additive, shortest-path methods can be used to select a lower-delay route.
Connectivity
A network is connected when every pair of vertices is joined by some path.
If one vertex or group of vertices cannot reach the rest of the network, the graph is disconnected.
Connectivity is one of the most basic requirements of a functioning communication system.
Connected Components
A connected component is a maximal connected part of a graph.
Suppose a graph contains:
- A connected to B and C;
- D connected to E;
- no edge between the two groups.
Then the graph has two connected components:
\[ \{A,B,C\} \]and
\[ \{D,E\}. \]Reachability in Directed Networks
In directed networks, connectivity must respect edge direction.
If
\[ A\rightarrow B\rightarrow C, \]then C is reachable from A.
But A is not necessarily reachable from C.
This distinction matters in broadcast systems, dependency graphs, web-link networks, and permission structures.
Strong Connectivity
A directed network is strongly connected when every vertex can reach every other vertex through directed paths.
Strong connectivity is more demanding than simply ignoring directions and checking whether the underlying graph is connected.
Shortest Communication Paths
A network may contain several routes between the same source and destination.
If edge weights represent latency or cost, a common goal is to find
\[ \boxed{\text{the minimum-total-weight path}}. \]This is the shortest-path problem.
A Shortest-Path Example
Suppose the available links have latencies:
- A-B: 2;
- A-C: 6;
- B-C: 1;
- B-D: 5;
- C-D: 2.
One route from A to D is
\[ A\rightarrow B\rightarrow D \]with latency
\[ 2+5=7. \]Another is
\[ A\rightarrow B\rightarrow C\rightarrow D \]with latency
\[ 2+1+2=\boxed{5}. \]The second route is better under the latency objective.
Routing Tables
A communication node may store information about which next link should be used to reach different destinations.
A simplified routing table could contain:
| Destination | Next Hop | Estimated Cost |
|---|---|---|
| B | B | 2 |
| C | B | 3 |
| D | B | 5 |
The table summarizes path information without storing every possible route explicitly.
Local Routing Decisions
In many distributed networks, a packet or message is forwarded one step at a time.
The current node chooses the next hop according to a routing rule.
A sequence of local forwarding decisions creates the full path through the network.
Hop Count
One simple routing metric is hop count, the number of edges used by a route.
The route
\[ A\rightarrow B\rightarrow C\rightarrow D \]has
\[ \boxed{3\text{ hops}}. \]Fewer hops can be desirable, but minimum hop count does not always mean minimum latency or maximum reliability.
Bandwidth and Capacity
A communication link may have a maximum transmission capacity.
If an edge \(e\) can carry at most \(c(e)\) units per second, then any flow \(f(e)\) through that link must satisfy
\[ \boxed{0\le f(e)\le c(e)}. \]Capacity constraints transform a simple routing problem into a network-flow problem.
Flow Conservation
At an intermediate node, flow entering the node generally must equal flow leaving it, unless the node creates, consumes, stores, or discards flow.
In the standard network-flow model,
\[ \boxed{ \sum \text{flow in} = \sum \text{flow out} } \]for each intermediate vertex.
A Simple Flow Example
Suppose source S sends data toward destination T through two parallel routes.
One route can carry at most \(8\) units per second.
The other can carry at most \(5\) units per second.
If the routes are otherwise independent, their combined capacity is at most
\[ 8+5=\boxed{13} \]units per second.
Bottlenecks
A bottleneck is a link or small group of links whose limited capacity restricts the performance of a larger network.
Suppose a path has edge capacities
\[ 10,\qquad 6,\qquad 12. \]A single-path flow cannot exceed the smallest capacity:
\[ \boxed{\min(10,6,12)=6}. \]The edge with capacity \(6\) is the bottleneck on that path.
Cuts
A cut separates the vertices of a network into two groups.
In a source-to-destination flow problem, a cut separates the source from the destination.
The capacity of the cut is determined by the capacities of the relevant edges crossing from the source side to the destination side.
Maximum Flow and Minimum Cut
One of the central results of network-flow theory is that, under the standard model,
\[ \boxed{\text{maximum flow value}=\text{minimum cut capacity}}. \]This means the smallest separating capacity identifies the largest amount of flow the network can support from source to destination.
The result connects operational throughput with structural bottlenecks.
Broadcasting
A broadcast sends information from one source to many recipients.
If every vertex must receive the message, a useful structure is a spanning tree.
A spanning tree connects all vertices while avoiding cycles.
Spanning Trees
A spanning tree of a connected graph contains every vertex and exactly enough edges to remain connected without cycles.
If a spanning tree has \(n\) vertices, then it has
\[ \boxed{n-1} \]edges.
This makes spanning trees useful for basic broadcast structures and low-redundancy connection designs.
Minimum Spanning Trees
If edges have construction costs, lengths, or other weights, a minimum spanning tree connects all vertices with minimum total edge weight.
This can model problems such as:
- laying communication cable;
- connecting offices;
- building backbone infrastructure;
- designing low-cost distribution structures.
Spanning Trees and Redundancy
A spanning tree uses no redundant edges.
That makes it efficient, but also potentially fragile.
Removing any edge from a tree disconnects it.
Therefore, the minimum-cost network is not always the most resilient network.
Redundancy
Redundancy means providing more than one route, component, or connection capable of performing an important function.
In a communication network, redundancy can allow traffic to be rerouted if an edge or node fails.
Redundancy usually increases cost, but it can also increase reliability and fault tolerance.
Single Points of Failure
A single point of failure is a component whose failure can disable a critical part of the system.
In graph terms, certain vertices or edges may be structurally essential to connectivity.
Identifying these elements is an important part of network resilience analysis.
Bridges
A bridge is an edge whose removal increases the number of connected components.
If a communication link is a bridge, losing that one link disconnects some part of the network.
Bridges are therefore natural candidates for redundancy planning.
Articulation Points
An articulation point is a vertex whose removal disconnects a connected graph.
In practical terms, an articulation point may represent a critical router, relay station, office, or hub through which otherwise separate regions communicate.
Edge Connectivity
The edge connectivity of a graph is the minimum number of edges that must be removed to disconnect the graph.
A network with edge connectivity \(1\) contains at least one bridge.
Larger edge connectivity generally indicates stronger resistance to link failures.
Vertex Connectivity
The vertex connectivity of a graph measures the minimum number of vertices whose removal disconnects the graph, subject to the standard graph-theoretic definitions.
This gives a structural measure of resistance to node failure.
Latency and Throughput Are Different
Latency measures how long information takes to travel.
Throughput measures how much information can be transferred over time.
A path can have low latency but limited capacity.
Another path can have higher latency but much greater throughput.
These are different optimization objectives.
Reliability of a Single Link
Suppose a communication link works with probability
\[ p. \]Then its failure probability is
\[ \boxed{1-p}. \]Reliability calculations become more interesting when several links are connected in series or in parallel.
Series Reliability
Suppose a communication path requires every one of several independent links to work.
If the link reliabilities are
\[ p_1,p_2,\ldots,p_n, \]then the path reliability is
\[ \boxed{p_1p_2\cdots p_n}. \]For three links with reliability \(0.98\) each,
\[ (0.98)^3\approx\boxed{0.9412}. \]Parallel Redundancy
Suppose two independent links can each provide the required connection.
Let their reliabilities be \(p_1\) and \(p_2\).
The system fails only if both links fail:
\[ P(\text{failure})=(1-p_1)(1-p_2). \]Therefore,
\[ \boxed{ P(\text{working}) =1-(1-p_1)(1-p_2) }. \]Parallel Reliability Example
Suppose two independent redundant links each work with probability
\[ 0.90. \]The probability both fail is
\[ (0.10)(0.10)=0.01. \]Therefore, the probability that at least one works is
\[ 1-0.01=\boxed{0.99}. \]Redundancy increases reliability under the independence assumption.
Centrality
In some applications, we want to identify structurally important vertices.
Different centrality measures capture different meanings of importance.
Examples include:
- degree centrality;
- closeness centrality;
- betweenness centrality;
- eigenvector-based measures.
No single centrality measure is universally correct.
Degree Centrality
Degree centrality emphasizes the number of direct connections.
In a simple undirected graph with \(n\) vertices, one normalized form is
\[ \boxed{ C_D(v)=\frac{\deg(v)}{n-1} }. \]A vertex connected directly to every other vertex has normalized degree centrality \(1\).
Betweenness and Brokerage
A vertex can be important even without having the highest degree.
If many shortest paths between other vertices pass through one node, that node may serve as a bridge or broker between regions of the network.
Betweenness centrality is designed to capture this kind of structural position.
Network Diameter
The diameter of a connected unweighted graph is the largest shortest-path distance between any two vertices.
If
\[ d(u,v) \]is shortest-path distance, then
\[ \boxed{ \operatorname{diam}(G) = \max_{u,v\in V}d(u,v) }. \]Diameter gives a coarse measure of the network's maximum separation.
Network Density
Density compares the number of existing edges with the number that could exist.
For a simple undirected graph with \(n\) vertices and \(m\) edges,
\[ \boxed{ \text{density} = \frac{2m}{n(n-1)} }. \]Density near \(1\) indicates many possible connections are present.
Density near \(0\) indicates a sparse network.
Complete Networks
A simple undirected complete graph on \(n\) vertices contains every possible edge.
Its number of edges is
\[ \boxed{\binom{n}{2}=\frac{n(n-1)}{2}}. \]A fully connected network provides many direct routes, but the number of required links grows quadratically.
The Cost of Full Connectivity
For \(10\) vertices, a complete simple graph requires
\[ \binom{10}{2} =\frac{10\cdot9}{2} =\boxed{45} \]edges.
A spanning tree on the same \(10\) vertices requires only
\[ \boxed{9} \]edges.
This illustrates the tradeoff between low infrastructure cost and high redundancy.
Communication Trees
Tree structures arise naturally in hierarchical communication.
One root may send information to several children, each of which forwards the information farther.
Trees avoid duplicate cycles, but they also create dependency on parent links.
Cycles and Alternate Routes
Cycles create alternate routes.
If
\[ A-B-C-D-A \]forms a cycle, then there are at least two ways to travel between many pairs of vertices in the cycle.
This can improve resilience when one link fails.
Flooding
A simple communication strategy is to forward a message across many or all available outgoing links.
This can improve reachability but may create:
- duplicate messages;
- excess bandwidth use;
- cycles;
- congestion.
Practical systems therefore use identifiers, hop limits, spanning structures, or routing rules to control repeated forwarding.
Congestion
A network can be connected and still perform poorly when too much traffic is concentrated on limited-capacity links.
Congestion can increase:
- delay;
- queue lengths;
- packet loss;
- variability in delivery time.
Network design therefore depends on both topology and traffic.
Queues at Network Nodes
When messages arrive faster than they can be processed immediately, they wait in a queue.
This connects network analysis with stochastic queueing models.
A link may have enough long-run capacity on average yet still experience temporary congestion because arrivals and service times vary.
Dynamic Networks
Real networks can change over time.
Edges may:
- appear;
- fail;
- recover;
- change weight;
- change capacity.
A route that is optimal at one moment may no longer be optimal later.
Communication Under Failure
Suppose the normal shortest route is
\[ A\rightarrow B\rightarrow D. \]If edge \(B-D\) fails, the network may need to use
\[ A\rightarrow C\rightarrow E\rightarrow D. \]A resilient network is designed so that important communication can continue through alternate paths.
Network Robustness
Robustness broadly describes the ability of a network to continue functioning despite disruptions.
Useful questions include:
- How many failures can occur before connectivity is lost?
- Which edges are most critical?
- Which vertices are most critical?
- How much capacity remains after a failure?
- Can traffic be rerouted?
Network Design Is a Tradeoff
Adding edges can improve:
- connectivity;
- redundancy;
- capacity;
- route flexibility.
But additional edges can also increase:
- construction cost;
- maintenance;
- coordination complexity;
- security exposure.
Good network design balances these competing objectives.
Common Error: Confusing an Edge with a Path
An edge is one direct connection.
A path may contain several edges.
If A reaches D through
\[ A-B-C-D, \]then A and D are connected by a path, but they are not necessarily adjacent.
Common Error: Ignoring Direction
In a directed graph,
\[ A\rightarrow B \]does not imply
\[ B\rightarrow A. \]Reversing an edge without justification can create paths that do not actually exist.
Common Error: Adding Capacities Along One Path
For a single path with edge capacities
\[ 10,\ 8,\ 6, \]the path cannot carry
\[ 10+8+6=24 \]units simultaneously.
The path is limited by its bottleneck:
\[ \boxed{6}. \]Common Error: Using the Smallest Number of Hops as the Shortest Weighted Path
Consider two routes:
\[ A\rightarrow B\rightarrow D \]with weights
\[ 9+9=18, \]and
\[ A\rightarrow C\rightarrow E\rightarrow D \]with weights
\[ 3+3+3=9. \]The second route has more hops but smaller total weight.
Common Error: Treating a Minimum Spanning Tree as a Shortest-Path Tree
A minimum spanning tree minimizes the total weight needed to connect all vertices.
It does not necessarily preserve the shortest path from one chosen source to every other vertex.
These are different optimization problems.
Common Error: Assuming High Degree Means Highest Importance
A highly connected vertex may be important, but another lower-degree vertex may sit between otherwise separate regions.
Importance depends on the network question being asked.
Degree, betweenness, closeness, reliability role, and capacity role measure different aspects of importance.
Common Error: Assuming Redundant Links Are Independent
Reliability formulas for parallel independent links use multiplication of failure probabilities.
But two links may fail together if they share:
- the same power source;
- the same physical conduit;
- the same upstream provider;
- the same environmental exposure.
Independence is a modeling assumption that must be justified.
A Reliable Procedure for Network Problems
- Identify the entities that should become vertices.
- Identify the relationships that should become edges.
- Determine whether edges are directed or undirected.
- Attach weights or capacities when relevant.
- State the operational question clearly.
- Determine whether the objective concerns connectivity, shortest path, flow, cost, or resilience.
- Select the appropriate graph concept or algorithm.
- Calculate the relevant path, tree, flow, cut, or structural measure.
- Check assumptions such as nonnegative weights or independence.
- Interpret the result in the language of the original system.
A Reliable Procedure for Communication Routing
- Identify the source and destination.
- List the available directed or undirected links.
- Choose the routing metric.
- Calculate candidate path costs or run an appropriate shortest-path method.
- Check capacity and policy restrictions.
- Choose the best feasible route under the stated metric.
- Identify an alternate route when resilience matters.
- Recalculate if the network changes.
A Reliable Procedure for Network Resilience
- Identify critical services or source-destination pairs.
- Check whether alternate paths exist.
- Identify bridges and articulation points.
- Inspect bottleneck capacities.
- Test important edge or vertex failures.
- Evaluate whether redundant components share common failure causes.
- Compare resilience improvements with their added cost.
Example: Full Communication-Path Workflow
Suppose a network contains:
- A-B: 3 ms;
- A-C: 5 ms;
- B-C: 1 ms;
- B-D: 6 ms;
- C-D: 2 ms;
- D-E: 4 ms.
One route from A to E is
\[ A\rightarrow B\rightarrow D\rightarrow E \]with latency
\[ 3+6+4=13\text{ ms}. \]Another is
\[ A\rightarrow B\rightarrow C\rightarrow D\rightarrow E \]with latency
\[ 3+1+2+4=\boxed{10\text{ ms}}. \]Under the latency objective, the second route is preferable among these candidates.
Example: Full Reliability Workflow
Suppose a communication path contains three independent links with reliabilities
\[ 0.99,\qquad0.97,\qquad0.98. \]Because every link must work, the path reliability is
\[ (0.99)(0.97)(0.98). \]Therefore,
\[ \boxed{P(\text{path works})\approx0.9411}. \]The path is less reliable than any one of its individual links because all three must succeed.
Example: Full Capacity Workflow
Suppose source S reaches T through two independent route branches.
Branch 1 has capacities
\[ 9,\qquad6. \]Its path capacity is
\[ \min(9,6)=6. \]Branch 2 has capacities
\[ 5,\qquad8. \]Its path capacity is
\[ \min(5,8)=5. \]If the branches are edge-disjoint and can be used simultaneously, the combined source-to-destination flow can reach
\[ 6+5=\boxed{11} \]units under this simplified structure.
Practice 1: Degree
Vertex A is directly connected to B, C, D, E, and F.
Find \(\deg(A)\).
Practice 2: Path Length
Find the unweighted path length of
\[ A-B-C-D-E. \]Practice 3: Weighted Path
A route contains link delays
\[ 5,\ 2,\ 4,\ 3 \]milliseconds.
Find the total latency.
Practice 4: Path Bottleneck
A path contains link capacities
\[ 12,\ 7,\ 10,\ 9. \]What is the maximum single-path flow supported by these links?
Practice 5: Spanning-Tree Edge Count
How many edges does a spanning tree on \(14\) vertices contain?
Practice 6: Complete-Graph Edge Count
How many edges are in the complete simple undirected graph on \(8\) vertices?
Practice 7: Series Reliability
Three independent required links each have reliability \(0.95\).
Find the reliability of the complete three-link path.
Practice 8: Parallel Reliability
Two independent redundant links each have reliability \(0.80\).
Find the probability that at least one works.
Practice 9: Density
A simple undirected graph has \(5\) vertices and \(7\) edges.
Find its density.
Practice 10: Connectivity Failure
A connected graph becomes disconnected when one particular edge is removed.
What is that edge called?
Practice Answers
Practice 1
A has five incident edges, so
\[ \boxed{\deg(A)=5}. \]Practice 2
The path contains four edges:
\[ \boxed{4}. \]Practice 3
\[ 5+2+4+3=\boxed{14\text{ ms}}. \]Practice 4
The path is limited by its smallest-capacity edge:
\[ \min(12,7,10,9)=\boxed{7}. \]Practice 5
A spanning tree on \(n\) vertices contains \(n-1\) edges:
\[ 14-1=\boxed{13}. \]Practice 6
\[ \binom{8}{2} =\frac{8\cdot7}{2} =\boxed{28}. \]Practice 7
\[ (0.95)^3 =0.857375. \]Therefore,
\[ \boxed{P(\text{path works})\approx0.8574}. \]Practice 8
Each link fails with probability
\[ 0.20. \]Both fail with probability
\[ (0.20)(0.20)=0.04. \]Therefore,
\[ 1-0.04=\boxed{0.96}. \]Practice 9
\[ \text{density} = \frac{2m}{n(n-1)} = \frac{2(7)}{5(4)} = \frac{14}{20} = \boxed{0.70}. \]Practice 10
The edge is a
\[ \boxed{\text{bridge}}. \]What to Remember
Networks provide a common mathematical language for communication, transportation, infrastructure, social relationships, and other connected systems.
- vertices represent entities;
- edges represent connections;
- directed edges preserve direction;
- weights can represent delay, cost, distance, or capacity;
- paths describe possible communication routes;
- connectivity determines whether vertices can reach one another;
- shortest paths optimize additive route measures;
- capacities constrain flow;
- bottlenecks limit throughput;
- spanning trees connect all vertices without cycles;
- redundancy can improve resilience;
- bridges and articulation points identify structural vulnerabilities;
- reliability depends on both topology and component behavior.
The central habit is: separate the network's structure from the quantity being optimized, then choose the graph concept that matches the operational question.
Where We Go Next
Network models explain how information and resources move through connected structures. The next applied problem family focuses on a related challenge: how information itself can be represented, transmitted accurately, and protected from error or unauthorized interpretation.
The next lesson, Coding, Security, and Cryptography, develops the discrete structures behind data representation, error detection, secure communication, keys, modular arithmetic, and cryptographic systems.