Basic Terminology used in Graphs.

Directed graph G, also known as a digraph, is a graph in which every edge has a direction assigned to it. An edge of a directed graph is given as an ordered pair (u, v) of nodes in G.

Adjacent nodes or neighbors –  For every edge, e = (u, v) that connects nodes u and v, the nodes u and v are the end-points and are said to be the adjacent nodes or neighbors.

• Out-degree of a node The out-degree of a node u, written as outdeg(u), is the number of edges that originate at u.
• In-degree of a node The in-degree of a node u, written as indeg(u), is the number of edges that terminate at u.
• Degree of a node – Degree of a node u, deg(u), is the total number of edges containing the node u. therefore Degree(node) = outdeg(node) + indeg(node)

• Path is defined as a sequence of (n+1) nodes. It is written as P = {v0, v1, v2, …, vn), of length n from a node u to vHere, u = v₀, v = v_n and v_i–1 is adjacent to vi for i = 1, 2, 3, …, n.
• Closed path A path P is known as a closed path if the edge has the same end-points. That is, if v₀ = v_n.
• Simple path A path P is known as a simple path if all the nodes in the path are distinct with an exception that v0 may be equal to vn. If v0 = vn, then the path is called a closed simple path.

Regular graph – It is a graph where each vertex has the same number of neighbors. That is, every node has the same degree.

Connected graph A graph is said to be connected if for any two vertices (u, v) in V there is a path from u to v. That is to say that there are no isolated nodes in a connected graph.

Complete graph A graph G is said to be complete if all its nodes are fully connected. That is, there is a path from one node to every other node in the graph. A complete graph has n(n–1)/2 edges, where n is the number of nodes in G.

Labelled graph or weighted graph – In a weighted graph, the edges of the graph are assigned some weight or length. The weight of an edge denoted by w(e) indicates the cost of traversing the edge.

• Loop -An edge that has identical end-points is called a loop. That is, e = (u, u).
• Multiple edges Distinct edges which connect the same end-points are called multiple edges.
• Multi-graph A graph with multiple edges and/or loops is called a multi-graph.
• Size of a graph The size of a graph is the total number of edges in it.
• Isolated vertex A vertex with degree zero. Such a vertex is not an end-point of any edge.
• Pendant vertex (also known as leaf vertex) A vertex with degree one.

Transitive Closure -For a directed graph G = (V,E), the transitive closure of G is a graph G* = (V,E*). In G*, for every vertex pair v, w in V there is an edge (v, w) in E* if and only if there is a valid path from v to w in G.

Adjacency matrix is used to represent which nodes are adjacent to one another. By definition, two nodes are said to be adjacent if there is an edge connecting them. In a directed graph G, if node v is adjacent to node u, then there is definitely an edge from u to v.

Adjacency List This structure consists of a list of all nodes in G. Every node is in turn linked to its own list that contains the names of all other nodes that are adjacent to it.