Graphs and Networks

An exact introduction to graph models, degrees, paths, connectivity, and network reasoning.

Vertices store objects; edges store selected relationships. A six-vertex network highlights one connected path in a contrasting colour. The numbered vertices and visible edges support direct checks of adjacency, routes, and cycles.

Precise definition

A graph $G=(V,E)$ consists of a vertex set $V$ and an edge set $E$. In a simple undirected graph, each edge is an unordered pair of distinct vertices, with no loops or repeated edges. A path follows adjacent vertices without repeating vertices; a cycle is a closed path of positive length with no repeated internal vertex.

Notation and mathematical language

Vertices $u,v$ are adjacent when $\{u,v\}\in E$. The degree $\deg(v)$ counts incident edges. A graph is connected when every two vertices are joined by a path. Directed graphs use ordered pairs; weighted graphs attach costs or lengths, so definitions and algorithms must match the graph type.

Conceptual picture

A graph deliberately suppresses irrelevant geometry: vertices may be redrawn anywhere without changing adjacency. What matters is which objects are linked. Adjacency lists emphasize local neighbours; adjacency matrices support algebraic operations; a drawing supports visual reasoning but can hide crossings or suggest nonexistent edges.

Fully worked example

Interpretation and application

Graphs represent roads, communication links, social ties, task dependencies, and molecules. An edge can mean very different relationships; a social-network edge records association, not necessarily influence or causation. Weighted shortest paths require weights with a clear interpretation such as distance, time, or cost.