Graphs and Networks: Terminology and notation

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.