Some terms related to the graph theory

Network models are intimately related to a certain branch of mathematics known as the graph theory. Actually networks themselves are graphs! Thus further we briefly introduce some of the terms related to the mathematical graph theory.

In mathematics a graph is a collection of vertices (or nodes) that are interconnected by edges (or links, or arcs). Edges might be either undirected or directed and they also might have weights assigned.

Graphs with directed edges are called directed graphs.

Undirected graph can be referred to as complete graph, if and only if every node is connected to all other nodes.

Graph is empty if it does not posses any edges.

Edges are considered to be adjacent if they connect to one common node. Nodes are considered to be adjacent if they are connected by an edge.

Node's, in the undirected graph, degree is a number of nodes adjacent to it.

Chain or path is a set of the adjacent edges.

Circuit or cycle is a path which has the same initial and final nodes.

Length of the path is a number of edges in the path.

Graph H is a subgraph of graph G, if H is composed of G nodes and edges.

H is an induced subgraph of G if it has exactly the edges that appear in G.

Graph is considered to be connected, if any pair of nodes is connected by the path.

Connected component of graph G is an induced subgraph of G.

Acyclic graph is called forest. Connected forest is called a tree.

Fig. 1:Various examples of graphs.