Graphs and Networks: Terminology and Notation

Basic Terminology

A Graph is a collection of points, known as vertices, and lines, known as edges, connecting those points.
Directed Graphs or Digraphs are graphs where each edge has an associated direction. Edges in such graphs are also known as arcs.
A Path is a sequence of vertices such that each vertex is adjacent to the vertex following it. A path from vertex A to vertex B is denoted as A-B.
A Cycle is a path in which the first vertex is also the last vertex, and no vertex is repeated, except the first and last one.
A Loop is an edge that starts and ends on the same vertex.
Two vertices are said to be adjacent if there is an edge connecting them.
The degree of a vertex is the total number of edges incident to it. In a Digraph, the degree can be split into indegree (number of edges pointing to the vertex) and outdegree (number of edges originating from the vertex).

A graph is Connected if there exists a path between each pair of vertices.
A Tree is an acyclic connected graph, where there is exactly one path between any two vertices.
A Subgraph is a portion of a graph which is a graph in its own right.
A graph is Complete if each pair of distinct vertices is connected by a unique edge. In a complete graph with ‘n’ vertices, each vertex has a degree of ‘n-1’.
A Planar Graph is one which can be drawn in a plane without any edges crossing over each other.
A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set with a vertex in the second set.

Network is a special kind of graph, where each arc has an associated capacity, which represents the maximum amount of flow the arc can carry.
The source in a network is a special node from where the flow originates, and the sink is the node where the flow ends.
The flow on an arc in a network cannot exceed its capacity.
A weighted graph or network is a graph in which a number (the weight) is assigned to each edge. These weights might represent, for example, costs, lengths or capacities, depending on the problem at hand.
The weight of a path or tree is the sum of the weights of the edges in the path or tree.
The maximum flow from the source to the sink is the highest possible total flow along all paths from source to sink not exceeding the arc capacities.