Graphs: Terminology & Representations

1. Vertex (Node): A fundamental unit in a graph representing an entity. It can represent anything, such as a city, person, or object.
2. Edge (Link): A connection between two vertices in a graph. It can be directed or undirected, weighted or unweighted.
3. Directed Graph (Digraph): A graph where edges have a direction associated with them, indicating a one-way relationship between vertices.
4. Undirected Graph: A graph where edges have no direction, indicating a two-way relationship between vertices.
5. Weighted Graph: A graph where edges have weights or costs associated with them, representing the cost of traversing from one vertex to another.
6. Degree of a Vertex: The number of edges incident to a vertex. In directed graphs, there are separate in-degree and out-degree measures.
7. Path: A sequence of vertices connected by edges, representing a route from one vertex to another.
8. Cycle: A path that starts and ends at the same vertex, without visiting any other vertex more than once.

Representations of Graphs:

1. Adjacency Matrix: A two-dimensional array where each cell represents the presence or absence of an edge between two vertices. It’s efficient for dense graphs but consumes more memory for sparse graphs.
2. Adjacency List: A collection of lists or arrays, where each list/array represents a vertex, and its elements represent the vertices adjacent to it. It’s efficient for sparse graphs but may require more time for certain operations.
3. Edge List: A simple list of edges, where each edge is represented by a pair of vertices (or triplet with weights). It’s straightforward but less efficient for certain operations compared to adjacency list or matrix.

Graphs & Multi-graphs:

1. Graph: In graph theory, a graph typically refers to a simple graph where each pair of vertices is connected by at most one edge.
2. Multi-graph: A multi-graph is a generalization of a graph where multiple edges between the same pair of vertices are allowed. These edges may have different weights or attributes.
3. Parallel Edges: In a multi-graph, parallel edges refer to multiple edges connecting the same pair of vertices.
4. Self-loop: An edge that connects a vertex to itself in a graph or multi-graph.

Multi-graphs can represent more complex relationships between entities, where multiple interactions or connections between the same pair of entities are possible. They are useful in various applications, including network analysis, transportation systems, and social networks. However, they may require more sophisticated algorithms and data structures for manipulation compared to simple graphs.