Graphs

1. Overview
2. Types of graphs
3. Representation of a graph

• A graph is a set of nodes (also called vertices) connected by edges.
• A graph is usually noted G(V, E) (V being the number of vertices and E the number of edges).

Notes :

• In directed graphs, the in-degree of a vertex is the number of edges pointing to it.
• In directed graphs, the out-degree of a vertex is the number of edges starting from it.
• In a graph cycle, the minimum degree for each vertex belonging to the cycle is 2.
• In a connected graph, the vertex with minimum eccentricity (equal to the radius) is called the central point of the graph.
• In a disconnected graph, the distance between a pair of vertices can be undefined (or infinite) if no path exists between them.
• Thus, vertex eccentricity does not exist in disconnected graphs, since there is at least a pair of vertices in it for which no path exist.

Notes :

• Paths between vertices are constrained by edge directions if the graph is directed.
• In directed graphs, the weight can be different for each direction on bidirectional edges.

• When the input is a graph, its size is expressed relative to V (number of vertices) and E (number of edges).
• For instance, an algorithm of complexity O(V + E) will process every vertex and every edge on every vertex.

• Reminder : in directed graphs, paths and cycles are constrained by the direction the edges point to.

Notes :

• In a bipartite graph, any edge connects a vertex from Va to a vertex from Vb.
• In a complete graph containing V vertices, each vertex degree is V - 1.
• A complete digraph is a complete directed graph : for any vertices Va and Vb, an edge points from Va to Vb' and another from Vb to Va.
• Directed acyclic graphs (DAG) are useful for representing the execution of a program and are important in computer science.

• In an undirected graph, a component is a connected subgraph that is not part of any larger connected subgraph.
• A connected graph has exactly one component, the graph itself.

Note : in directed graphs, components are called strongly connected components.

• A graph can be represented using different data structures with specific roles :

1. Vertices array : an array storing the graph's vertices, each being uniquely identified by their index.

// the shape of a vertex in the graph
interface Vertex {
    value:string;
}
// each vertex is being uniquely identified by its index in the array and accessed in O(1)
const vertices:Array<Vertex> = [
    {value: `red`},
    {value: `green`},
    {value: `blue`}
];

2. Adjacency list : an array of arrays storing objects that represent the graph's edges.

// a graph edge stores connected vertex index as well as the edge's weight
interface Edge {
    index:number;
    weight:number;
}
// this graph is (blue) <---> (red) ---> (green)
const edges:Array<Array<Edge>> = [
    [{ index: 1, weight: 5 }, { index: 2, weight: 1 }],
    [],
    // bidirectional edges are represented by 2 distinct edges on 2 distinct vertices ...
    [{ index: 0, weight: 9 }]
];

3. Adjacency matrix : an array of arrays of numbers representing the graph's edges through a matrix.

// the same (blue) <---> (red) ---> (green) graph represented using an adjacency matrix ...
const edges:Array<Array<number>> = [
    [0, 5, 1]
    [0, 0, 0]
    [9, 0, 0]
];

Notes :

• For sparsely connected graphs, adjacency lists should be preferred to adjacency matrixes for memory optimization.
• Put another way, adjacency matrixes store connections between vertices AS WELL AS ABSENCE OF CONNECTIONS while adjacency lists only store connections.