Graph (discrete mathematics)

Definition and Basics

A graph in discrete mathematics is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called an arc or line). Graphs are one of the prime objects of study in discrete mathematics.

Formal Definition

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, formed by pairs of vertices. In the common case, a pair (x, y) is different from (y, x); i.e., the edges are directed from one vertex to another. Such a graph is called a directed graph or digraph. Graphs such as these are among the objects studied by graph theory.

Types of Graphs

There are different types of graphs, which are classified based on their properties. Some of the common types include:

Simple Graphs: A graph is simple if it has no loops and no more than one edge between any two different vertices.
Multigraphs: A graph which may have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.
Pseudographs: A graph which may have multiple edges and loops, that is, edges that connect a vertex to itself.
Directed Graphs: A graph in which edges have orientations.
Undirected Graphs: A graph in which edges do not have an orientation. The edge (x, y) is identical to the edge (y, x) and they are not considered to be distinct.

Graph Properties

Graphs have certain properties that can be used to describe them. These include:

Degree: The degree of a vertex of a graph is the number of edges incident to the vertex.
Adjacency: Two vertices are said to be adjacent if they are both endpoints of the same edge.
Path: A path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence.
Cycle: A cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices.
Connectedness: A graph is said to be connected if there is a path from any point to any other point in the graph.

Graph Representation

Graphs can be represented in various ways, two of which are:

Adjacency Matrix: An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
Adjacency List: An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges.

Applications of Graphs

Graphs are used in many fields of study including computer science, physics, chemistry, biology, and network analysis. Some applications include:

Computer Networks: Graphs are used to represent the network of computers or servers and the connections between them.
Social Networks: Social structures can be represented by graphs where vertices represent individuals and edges represent relationships between them.
Web Graphs: The structure of the web can be represented by a directed graph where the vertices represent web pages and directed edges represent links from one page to another.