Using graphs and networks

UnderstandingNetworks and Graphs

Graphs consist of points called vertices (or nodes), and lines joining them, called edges.
A network is a connected graph, often used to model physical, biological, social, or informational systems.
Graphs can be directed, where each edge has a specific direction, or undirected, where edges have no particular direction.
Weighted graphs have a numerical value, or ‘weight’, associated with each edge.
The degree of a vertex is the number of edges connected to it. In a directed graph, the in-degree records the number of inward-pointing edges, and the out-degree the number of outward-pointing edges.

Creating Graphs and Networks

Graphs are represented using adjacency matrices or edge lists. An adjacency matrix is a square matrix where the entry in the i-th row and j-th column is equal to the number of edges between vertices i and j.
A complete graph is a graph where every pair of distinct vertices is connected by a unique edge.
The complement of a graph is another graph on the same set of vertices where two vertices are adjacent if and only if they are not adjacent in the original graph.

Applications of Graphs and Networks

Graphs and networks have numerous real-world applications. They are used in fields ranging from transport (road networks, flight paths) to computer science (internet networks, data structures).
Common problems involve finding the shortest path between two nodes, the minimum spanning tree of a weighted graph, or the maximum flow through a network.

Traversing Graphs and Networks

A walk in a graph is a sequence of vertices and edges, with each edge connecting consecutive vertices.
The length of a walk is the number of edges in it.
A walk in which no edge is repeated is called a trail. If no vertex is repeated, it’s a path. A circuit is a trail that begins and ends at the same vertex, while a cycle is a path that begins and ends at the same vertex.
A graph is connected if there is a path from every vertex to every other vertex.

Graph Theory Algorithms

The Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental algorithms for traversing graphs. They respectively explore the graph in breadthwise and depthwise directions from a starting node.
The Dijkstra’s algorithm provides a solution for the shortest path problem in weighted graphs.
The Kruskal’s algorithm and Prim’s algorithm are used for finding the minimum spanning tree in a graph.

Properties of Graphs and Networks

The Euler’s theorem states that a connected graph has an Euler circuit (a circuit that includes every edge of the graph exactly once) if and only if every vertex has an even degree.
The Handshaking theorem states that the sum of the degrees of all the vertices in a graph is twice the number of edges.
The concept of isomorphism allows us to classify graphs. Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves the adjacency relation.