# 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).

## Characterising Graphs

• 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 Flows

• 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.