Elements of graph theory

Branch and Node - A branch that represents a circuit element, is a line joining two nodes and a node is defined as a common point at which two or more branches meet together.

Graph- A  linear graph or simply a graph is defined as a collection of nodes and branches. The graph shows the geometrical interconnection of the elements of a network. A graph is connected if and only if there is a path directly or indirectly every pair of nodes. The circuits of a graph have the following properties.

1. The maximum number of branches in a circuit, will be equal to the number of nodes.
2. There are exactly two paths between any pair of nodes in a circuit.
3. There are at least two branches in a circuit.

Each branch or edge of the graph carries an arrow to indicate its orientation. A graph whose branches are oriented or directed graph, otherwise the graph is indirected graph.

Path- A path is an improper subgraph such that,

1. At the terminating nodes, only one branch is incident, and
2. At the remaining nodes, two branches are incident.

Tree (Twigs) and Co-Tree (Links or Chords) - A tree is defined as a connected graph that has no closed path. A tree may be defined as any set of branches in the original graph that is just sufficient to connect all the nodes. The number of branches is n-1.

For a given graph it is possible to draw numerous trees. The tree branches are (n-1), which are called twigs. The remaining branches are called links. The branches of the graph which are not in the tree form the co-tree or complement of the tree. Links is any branch belonging to the co-tree. It obvious that for each tree there exists a particular co-tree corresponding to that particular tree.

A graph, is then, the union of tree and its co-tree. This decomposition of a graph into tree and co-tree or its branches into twigs and links is not unique.

• Number of twigs; nt = n - 1
• Number of links; nl = b - nt = b - n + 1

Properties of a Tree

1. Tree consisted of all the nodes of the graph.
2. There will be no closed path in the tree.
3. There ca be many possible different trees for a given graph depending on the number nodes and branches.
4. If the graph has n number of nodes, then tree will have (n-1) branches.
5. Number of co-tree branches or number of link branches, (l = b - n + 1).

Loop or Circuit- If a link is added to a tree, the resulting graph contains one closed path, known as loop(or a circuit).

A loop of a graph has following properties:

1. There are exactly two paths between any pair of nodes in the circuit.
2. There exists at least two branches in a loop.
3. The maximum possible branches in a loop are equal to the number of nodes in the graph.

Loops which contain only one link are Independent and are known as basic or fundamental loops (f-loops) or tiesets. Consequently, the number of f-loops is equal to the number of links. Orientation of a f-loop is chosen to be the same as that of its link.

Cut-set- A cut-set is a minimal set up of branches that, if removed, divides a connected graph into two connected subgraphs i.e., it separates the nodes of the graph into two groups. So, it can be said that removal of these branches from original graph, reduces the rank of the original graph by one. Cut-sets containing only one twigs are independent and are known as basic or fundamental cut-sets (f cut-sets). Orientation of a f-cut-set is chosen to be the same as that of its twig. the Number of f-cut-sets is equal to the number of twigs.