Cut Set and Tie Set Matrices

Definition

In network graph theory, a cut set is a set of branches whose removal divides a connected graph into two disconnected subgraphs (or partitions the nodes into two disjoint sets), and no proper subset of these branches can achieve this separation. A tie set, also known as a loop set or fundamental loop, is a set of branches that form a closed path or circuit in the graph. These matrices, the Cut Set Matrix (Q) and the Tie Set Matrix (B), are fundamental tools used to systematically represent the topological structure of a network, enabling the formulation and solution of circuit equations based on Kirchhoff's laws.

Main Content

1. Fundamental Cut Sets (f-cut sets)

A fundamental cut set (f-cut set) is a special type of cut set defined with respect to a chosen tree of a connected graph. For a given tree, an f-cut set contains exactly one tree branch and a minimal set of links (branches not in the tree) such that removing all branches in this set disconnects the graph. Each tree branch uniquely defines one fundamental cut set.

• Definition: An f-cut set includes one tree branch and the minimum number of links required to disconnect the graph, where removing only the tree branch would not disconnect it if the links were still present.
• Formation: To form an f-cut set, select a tree branch. Then, identify all links that, when removed along with the chosen tree branch, would disconnect the graph into two parts. The orientation of the f-cut set is typically chosen to align with the direction of its defining tree branch.
• Significance: F-cut sets are crucial for applying Kirchhoff's Current Law (KCL) systematically across the network branches, as each f-cut set represents a generalized node.

2. Fundamental Tie Sets (f-tie sets) / Fundamental Loops

A fundamental tie set (f-tie set) or fundamental loop is a unique closed path formed by adding a single link (a branch not in the tree) to a tree. Each link uniquely defines one fundamental tie set.

• Definition: An f-tie set consists of one link and the unique path of tree branches that connects the two nodes of that link, thereby forming a closed loop.
• Formation: To form an f-tie set, select a link. This link, together with the unique path formed by tree branches between its two nodes, creates a closed loop. The orientation of the f-tie set is usually chosen to align with the direction of its defining link.
• Significance: F-tie sets are essential for applying Kirchhoff's Voltage Law (KVL) systematically around the network loops, as each f-tie set represents a generalized mesh.

3. Cut Set Matrix (Q)

The cut set matrix, denoted by Q, is a rectangular matrix that describes the relationship between branch currents and cut set currents, or branch voltages and cut set voltages, in a network graph.

• Structure: If a graph has 'n' nodes and 'b' branches, and a tree with 'r = n-1' branches (tree branches) is chosen, there will be 'r' fundamental cut sets. The Q matrix will have 'r' rows (one for each fundamental cut set) and 'b' columns (one for each branch).
• Elements ($Q_{ij}$):
  • $Q_{ij} = +1$ if branch 'j' is in fundamental cut set 'i' and its direction coincides with the cut set's orientation.
  • $Q_{ij} = -1$ if branch 'j' is in fundamental cut set 'i' and its direction opposes the cut set's orientation.
  • $Q_{ij} = 0$ if branch 'j' is not in fundamental cut set 'i'.
• Application: The cut set matrix allows for the systematic formulation of Kirchhoff's Current Law (KCL) equations in matrix form: $Q I_b = 0$, where $I_b$ is the vector of branch currents. This signifies that the sum of currents entering (or leaving) any cut set is zero.

4. Tie Set Matrix (B)

The tie set matrix, denoted by B, is a rectangular matrix that describes the relationship between branch voltages and tie set voltages, or branch currents and tie set currents, in a network graph.

• Structure: If a graph has 'n' nodes and 'b' branches, and a tree with 'r = n-1' branches is chosen, there will be 'l = b - (n-1)' fundamental tie sets (links). The B matrix will have 'l' rows (one for each fundamental tie set) and 'b' columns (one for each branch).
• Elements ($B_{ij}$):
  • $B_{ij} = +1$ if branch 'j' is in fundamental tie set 'i' and its direction coincides with the tie set's orientation.
  • $B_{ij} = -1$ if branch 'j' is in fundamental tie set 'i' and its direction opposes the tie set's orientation.
  • $B_{ij} = 0$ if branch 'j' is not in fundamental tie set 'i'.
• Application: The tie set matrix allows for the systematic formulation of Kirchhoff's Voltage Law (KVL) equations in matrix form: $B V_b = 0$, where $V_b$ is the vector of branch voltages. This signifies that the algebraic sum of voltages around any closed loop is zero.

Working / Process

Let's illustrate the process with a simple undirected graph, then assign directions for matrix construction. Consider a graph with 4 nodes (1, 2, 3, 4) and 5 branches (b1, b2, b3, b4, b5).

Network Graph Example: Branches with assumed directions: b1: 1 -> 2 b2: 2 -> 3 b3: 3 -> 4 b4: 4 -> 1 b5: 2 -> 4

      b1
   1 ----> 2
   ^       |
   |       | b2
   b4      v
   |       3
   |      ^ \
   4 <----  | b5
    (b3)    | (b5 direction 2->4)

Visual representation of the graph for understanding branch and node connections.

1. Choose a Tree and Orient Branches

• Selecting a Tree: A tree is a subgraph that connects all nodes without forming any loops. For our example graph, let's choose the tree T = {b1, b2, b3}. The links (branches not in the tree) are L = {b4, b5}.

      b1
   1 ----> 2
           |
           | b2
           v
           3
           ^
           | b3
           4

*This diagram shows the chosen tree with branches b1, b2, b3.*

• Orient Branches: The directions given for b1-b5 in the initial graph will be used.

2. Construct Fundamental Cut Sets and Their Matrix (Q)

There are 'n-1' = 4-1 = 3 fundamental cut sets, one for each tree branch. We assign an orientation to each cut set, usually aligning with its defining tree branch.

• F-Cut Set 1 (defined by b1): To cut b1, we separate node 1 from the rest. The cut set contains {b1, b4} (considering the rest of the tree is connected). Let its orientation be aligned with b1 (from node 1).

  • Branches in cut set: {b1, b4}.
  • $Q_{1,b1}$: b1's direction (1->2) aligns with cut set (separates 1). $Q_{1,b1} = +1$.
  • $Q_{1,b4}$: b4's direction (4->1) opposes cut set (enters 1). $Q_{1,b4} = -1$.
  • Other branches (b2, b3, b5) are not in this cut set: $Q_{1,b2}=0, Q_{1,b3}=0, Q_{1,b5}=0$.

• F-Cut Set 2 (defined by b2): To cut b2, we separate node 3 from nodes 1, 2, 4. The cut set contains {b2, b3, b5}. Let its orientation be aligned with b2 (from node 2).

  • Branches in cut set: {b2, b3, b5}.
  • $Q_{2,b2}$: b2's direction (2->3) aligns with cut set (leaves 2/enters 3). $Q_{2,b2} = +1$.
  • $Q_{2,b3}$: b3's direction (3->4) aligns with cut set (leaves 3/enters 4). $Q_{2,b3} = +1$.
  • $Q_{2,b5}$: b5's direction (2->4) aligns with cut set (leaves 2/enters 4). $Q_{2,b5} = +1$.
  • Other branches (b1, b4) are not in this cut set: $Q_{2,b1}=0, Q_{2,b4}=0$.

• F-Cut Set 3 (defined by b3): To cut b3, we separate node 4 from nodes 1, 2, 3. The cut set contains {b3, b4, b5}. Let its orientation be aligned with b3 (from node 3).

  • Branches in cut set: {b3, b4, b5}.
  • $Q_{3,b3}$: b3's direction (3->4) aligns with cut set (leaves 3/enters 4). $Q_{3,b3} = +1$.
  • $Q_{3,b4}$: b4's direction (4->1) opposes cut set (leaves 4). $Q_{3,b4} = -1$.
  • $Q_{3,b5}$: b5's direction (2->4) aligns with cut set (enters 4). $Q_{3,b5} = +1$.
  • Other branches (b1, b2) are not in this cut set: $Q_{3,b1}=0, Q_{3,b2}=0$.

Cut Set Matrix (Q): b1 b2 b3 b4 b5 f-c1 [ 1 0 0 -1 0 ] f-c2 [ 0 1 1 0 1 ] f-c3 [ 0 0 1 -1 1 ]

3. Construct Fundamental Tie Sets and Their Matrix (B)

There are 'b - (n-1)' = 5 - 3 = 2 fundamental tie sets, one for each link. We assign an orientation to each tie set, usually aligning with its defining link.

• F-Tie Set 1 (defined by b4): Adding link b4 (4->1) to the tree {b1, b2, b3} forms a loop {b1, b2, b3, b4}. Let its orientation be aligned with b4 (clockwise loop 1-2-3-4-1).

  • Branches in tie set: {b1, b2, b3, b4}.
  • $B_{1,b4}$: b4's direction (4->1) aligns with loop. $B_{1,b4} = +1$.
  • $B_{1,b1}$: b1's direction (1->2) aligns with loop. $B_{1,b1} = +1$.
  • $B_{1,b2}$: b2's direction (2->3) aligns with loop. $B_{1,b2} = +1$.
  • $B_{1,b3}$: b3's direction (3->4) aligns with loop. $B_{1,b3} = +1$.
  • Other branch (b5) is not in this tie set: $B_{1,b5}=0$.

• F-Tie Set 2 (defined by b5): Adding link b5 (2->4) to the tree {b1, b2, b3} forms a loop {b2, b3, b5}. Let its orientation be aligned with b5 (loop 2-3-4-2).

  • Branches in tie set: {b2, b3, b5}.
  • $B_{2,b5}$: b5's direction (2->4) aligns with loop. $B_{2,b5} = +1$.
  • $B_{2,b2}$: b2's direction (2->3) aligns with loop. $B_{2,b2} = +1$.
  • $B_{2,b3}$: b3's direction (3->4) aligns with loop. $B_{2,b3} = +1$.
  • Other branches (b1, b4) are not in this tie set: $B_{2,b1}=0, B_{2,b4}=0$.

Tie Set Matrix (B): b1 b2 b3 b4 b5 f-t1 [ 1 1 1 1 0 ] f-t2 [ 0 1 1 0 1 ]

Advantages / Applications

• Systematic Network Analysis: Cut set and tie set matrices provide a structured way to apply Kirchhoff's Laws (KCL and KVL), transforming complex circuit analysis into matrix algebra problems.
• Formulation of Circuit Equations: They are used to derive the fundamental KCL equations ($Q I_b = 0$) and KVL equations ($B V_b = 0$), which are the basis for solving for unknown currents and voltages in a network.
• Duality Theory: The concept of cut sets and tie sets highlights the duality principle in network theory, where KCL in one domain corresponds to KVL in its dual, and vice versa. This is evident from the property that the cut set matrix and tie set matrix are orthogonal ($Q B^T = 0$).
• Computational Efficiency: For large and complex networks, using matrix methods based on cut sets and tie sets can be more computationally efficient than manual application of KCL/KVL.
• Computer-Aided Design (CAD) Tools: These matrices are fundamental to algorithms used in circuit simulation and design automation software.

Summary

Cut set and tie set matrices are essential topological matrices in network graph theory that systematically represent the connectivity of a network's branches with respect to specific sets of branches (cut sets for KCL and tie sets for KVL). The Cut Set Matrix (Q) relates branch currents to fundamental cut sets, while the Tie Set Matrix (B) relates branch voltages to fundamental tie sets. These matrices simplify the formulation of Kirchhoff's laws into a concise matrix form, serving as powerful tools for analyzing and solving complex electrical circuits. For efficient circuit analysis and computer-aided design, understanding fundamental cut sets, fundamental tie sets, and their matrix representations is crucial.