Graph theory

Introduction:

Graph theory is a captivating branch of mathematics that has found applications in various fields, including computer science, network analysis, social network analysis, and optimization problems. In this article, we will delve into the fundamentals of graph theory, exploring the concept of vertices, edges, and the different types of graphs. We will also provide code examples in C#, JavaScript, Python, and PHP to illustrate key concepts.

Understanding Vertices and Edges:

A graph is a mathematical structure that represents the pairwise relationships between objects. It consists of two essential components: vertices and edges. Vertices, also known as nodes or points, represent the objects themselves. For example, in a social network, each person can be represented as a vertex.
Edges, on the other hand, represent the connections or relationships between vertices. They can be thought of as links or lines. In an undirected graph, the edges link two vertices symmetrically, implying that the relationship is bidirectional. On the contrary, in a directed graph, the edges link two vertices asymmetrically, indicating a one-way relationship.

Types of Graphs:

Graphs can take on various forms, each with its own unique characteristics. Here are some commonly encountered types of graphs:

Complete Graph: A complete graph is one where every pair of vertices is connected by an edge. In other words, there are no isolated vertices in a complete graph.

Links

Code Examples

C#
using System;
using System.Collections.Generic;

class Graph
{
    private Dictionary<int, List<int>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<int, List<int>>();
    }

    public void AddVertex(int vertex)
    {
        adjacencyList[vertex] = new List<int>();
    }

    public void AddEdge(int source, int destination)
    {
        if (!adjacencyList.ContainsKey(source) || !adjacencyList.ContainsKey(destination))
            throw new ArgumentException("Vertex does not exist in the graph.");

        adjacencyList[source].Add(destination);
        adjacencyList[destination].Add(source);
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph();

        graph.AddVertex(1);
        graph.AddVertex(2);
        graph.AddVertex(3);
        graph.AddVertex(4);

        graph.AddEdge(1, 2);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 4);
        graph.AddEdge(4, 1);
    }
}

JavaScript
class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(vertex) {
        this.adjacencyList.set(vertex, []);
    }

    addEdge(source, destination) {
        this.adjacencyList.get(source).push(destination);
        this.adjacencyList.get(destination).push(source);
    }
}

const graph = new Graph();

graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);

graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 1);

Python
class Graph:
    def __init__(self):
        self.adjacencyList = {}

    def addVertex(self, vertex):
        self.adjacencyList[vertex] = []

    def addEdge(self, source, destination):
        self.adjacencyList[source].append(destination)
        self.adjacencyList[destination].append(source)

graph = Graph()

graph.addVertex(1)
graph.addVertex(2)
graph.addVertex(3)
graph.addVertex(4)

graph.addEdge(1, 2)
graph.addEdge(2, 3)
graph.addEdge(3, 4)
graph.addEdge(4, 1)

PHP
class Graph {
    private $adjacencyList;

    public function __construct() {
        $this->adjacencyList = [];
    }

    public function addVertex($vertex) {
        $this->adjacencyList[$vertex] = [];
    }

    public function addEdge($source, $destination) {
        $this->adjacencyList[$source][] = $destination;
        $this->adjacencyList[$destination][] = $source;
    }
}

$graph = new Graph();

$graph->addVertex(1);
$graph->addVertex(2);
$graph->addVertex(3);
$graph->addVertex(4);

$graph->addEdge(1, 2);
$graph->addEdge(2, 3);
$graph->addEdge(3, 4);
$graph->addEdge(4, 1);