Ma trận cấu trúc mạng
Trong chương trước, chúng ta đã thảo luận về cách biến đổi một mạch điện thành một đồ thị tương đương. Bây giờ, chúng ta hãy thảo luận về Ma trận cấu trúc liên kết mạng hữu ích để giải quyết bất kỳ vấn đề nào về mạch điện hoặc mạng bằng cách sử dụng các đồ thị tương đương của chúng.
Ma trận liên kết với đồ thị mạng
Sau đây là ba ma trận được sử dụng trong lý thuyết Đồ thị.
- Ma trận liên thuộc
- Ma trận vòng lặp cơ bản
- Ma trận bộ cắt cơ bản
Ma trận liên thuộc
Ma trận tỷ lệ ngẫu nhiên biểu diễn đồ thị của một mạch điện hoặc mạng điện nhất định. Do đó, có thể vẽ đồ thị của cùng một mạch điện hoặc mạng điện từincidence matrix.
Chúng ta biết rằng đồ thị bao gồm một tập hợp các nút và chúng được nối với nhau bằng một số nhánh. Vì vậy, kết nối của các nhánh với một nút được gọi là tỷ lệ mắc. Ma trận tỷ lệ được biểu diễn bằng chữ A. Nó còn được gọi là ma trận tỷ lệ nút đến nhánh hoặcnode incidence matrix.
Nếu có 'n' nút và nhánh 'b' có trong directed graph, thì ma trận tỷ lệ sẽ có 'n' hàng và 'b' cột. Ở đây, các hàng và cột tương ứng với các nút và nhánh của đồ thị có hướng. Vì thếorder của ma trận tỷ lệ sẽ là n × b.
Các elements of incidence matrix sẽ có một trong ba giá trị này, +1, -1 và 0.
Nếu dòng nhánh rời khỏi một nút đã chọn, thì giá trị của phần tử sẽ là +1.
Nếu dòng điện nhánh đi vào một nút đã chọn, thì giá trị của phần tử sẽ là -1.
Nếu dòng điện nhánh không đi vào một nút đã chọn hoặc không rời khỏi một nút đã chọn, thì giá trị của phần tử sẽ là 0.
Quy trình tìm Ma trận Tỷ lệ
Thực hiện theo các bước sau để tìm ma trận tỷ lệ của đồ thị có hướng.
Chọn một nút tại một thời điểm của đồ thị có hướng đã cho và điền liên tiếp các giá trị của các phần tử của ma trận tỷ lệ tương ứng với nút đó.
Lặp lại bước trên cho tất cả các nút của đồ thị có hướng đã cho.
Thí dụ
Hãy xem xét những điều sau directed graph.
Các incidence matrix tương ứng với đồ thị có hướng trên sẽ là
$$ A = \ begin {bmatrix} -1 & 1 & 0 & -1 & 0 & 0 \\ 0 & -1 & 1 & 0 & 1 & 0 \\ 1 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & -1 & -1 \ end {bmatrix} $$
Các hàng và cột của ma trận trên đại diện cho các nút và các nhánh của đồ thị có hướng đã cho. Bậc của ma trận tỷ lệ này là 4 × 6.
Bằng cách quan sát ma trận tỷ lệ trên, chúng ta có thể kết luận rằng summationcủa các phần tử cột của ma trận tỷ lệ bằng không. Điều đó có nghĩa là dòng điện nhánh rời khỏi một nút và chỉ đi vào một nút duy nhất khác.
Note- Nếu đồ thị đã cho là kiểu không có hướng thì chuyển nó thành đồ thị có hướng bằng cách biểu diễn các mũi tên trên mỗi nhánh của nó. Chúng ta có thể xem xét hướng tùy ý của dòng điện trong mỗi nhánh.
Ma trận vòng lặp cơ bản
Vòng lặp cơ bản hoặc f-looplà một vòng lặp, chỉ chứa một liên kết và một hoặc nhiều nhánh rẽ. Vì vậy, số vòng lặp f sẽ bằng số liên kết. Ma trận vòng lặp cơ bản được biểu diễn bằng chữ B. Nó còn được gọi làfundamental circuit matrixvà ma trận Tie-set. Ma trận này đưa ra mối quan hệ giữa dòng điện nhánh và dòng điện liên kết.
Nếu có 'n' nút và nhánh 'b' có trong directed graph, thì số liên kết có trong cây đồng ứng với cây đã chọn của đồ thị đã cho sẽ là b-n + 1.
Vì vậy, ma trận vòng lặp cơ bản sẽ có hàng 'b-n + 1' và cột 'b'. Ở đây, các hàng và cột tương ứng với các liên kết của đồng cây và các nhánh của đồ thị đã cho. Do đó, thứ tự của ma trận vòng lặp cơ bản sẽ là(b - n + 1) × b.
Các elements of fundamental loop matrix sẽ có một trong ba giá trị này, +1, -1 và 0.
Giá trị của phần tử sẽ được +1 cho liên kết của vòng lặp f đã chọn.
Giá trị của các phần tử sẽ là 0 đối với các liên kết và nhánh còn lại, không thuộc vòng lặp f đã chọn.
Nếu hướng của dòng điện nhánh của vòng f đã chọn giống với chiều của dòng liên kết f vòng, thì giá trị của phần tử sẽ là +1.
Nếu hướng của dòng điện xoắn của vòng f đã chọn ngược với chiều của dòng liên kết f, thì giá trị của phần tử sẽ là -1.
Quy trình tìm Ma trận vòng lặp cơ bản
Làm theo các bước sau để tìm ma trận vòng cơ bản của đồ thị có hướng đã cho.
Chọn một cây của đồ thị có hướng cho trước.
Bằng cách bao gồm một liên kết tại một thời điểm, chúng ta sẽ nhận được một vòng lặp f. Điền các giá trị của các phần tử tương ứng với vòng lặp f này trong một hàng của ma trận vòng lặp cơ bản.
Lặp lại bước trên cho tất cả các liên kết.
Thí dụ
Hãy xem cây sau của directed graph, được xem xét cho ma trận tỷ lệ.
Cây trên gồm ba nhánh d, e & f. Do đó, các nhánh a, b & c sẽ là các liên kết của Cây đồng ứng với Cây trên. Bằng cách bao gồm một liên kết tại một thời điểm đến Cây ở trên, chúng tôi sẽ nhận được mộtf-loop. Vì vậy, sẽ có baf-loops, vì có ba liên kết. Ba vòng lặp f này được thể hiện trong hình sau.
Trong hình trên, các nhánh được biểu diễn bằng các đường màu tạo thành các vòng f. Chúng ta sẽ nhận được các giá trị phần tử khôn ngoan hàng của ma trận Tie-set từ mỗi vòng lặp f. NênTieset matrix trong số các Cây được xem xét ở trên sẽ là
$$ B = \ begin {bmatrix} 1 & 0 & 0 & -1 & 0 & -1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & -1 & 1 \ kết thúc {bmatrix} $$
Các hàng và cột của ma trận trên đại diện cho các liên kết và các nhánh của đồ thị có hướng đã cho. Bậc của ma trận tỷ lệ này là 3 × 6.
Các number of Fundamental loop matricescủa một biểu đồ có hướng sẽ bằng số Cây của biểu đồ có hướng đó. Bởi vì, mỗi Cây sẽ có một ma trận vòng lặp Cơ bản.
Ma trận tổng hợp cơ bản
Bộ cắt cơ bản hoặc f-cut setlà số nhánh tối thiểu được loại bỏ khỏi đồ thị theo cách mà đồ thị ban đầu sẽ trở thành hai đồ thị con biệt lập. Bộ f-cut chỉ chứaone twigvà một hoặc nhiều liên kết. Vì vậy, số f bộ cắt sẽ bằng số cành cây.
Fundamental cut set matrix được biểu diễn bằng chữ C. Ma trận này cung cấp mối quan hệ giữa điện áp nhánh và điện áp nhánh.
Nếu có 'n' nút và nhánh 'b' có trong directed graph, thì số lượng cành cây có trong một Cây được chọn của đồ thị đã cho sẽ là n-1. Vì vậy, ma trận tập hợp cắt cơ bản sẽ có 'n-1' hàng và 'b' cột. Ở đây, các hàng và cột tương ứng với các nhánh của cây và nhánh đã chọn của biểu đồ đã cho. Vì thếorder của ma trận tập hợp cắt cơ bản sẽ là (n-1) × b.
Các elements of fundamental cut set matrix sẽ có một trong ba giá trị này, +1, -1 và 0.
Giá trị của phần tử sẽ được +1 cho nhánh của f-cutset đã chọn.
Giá trị của các phần tử sẽ là 0 đối với các nhánh và liên kết còn lại, không thuộc tập cắt f đã chọn.
Nếu hướng của dòng điện liên kết của bộ cắt f đã chọn giống với hướng của dòng điện nhánh bộ cắt f, thì giá trị của phần tử sẽ là +1.
Nếu hướng của dòng điện liên kết của bộ cắt f đã chọn ngược với hướng của dòng điện liên kết f bộ cắt, thì giá trị của phần tử sẽ là -1.
Quy trình tìm Ma trận tổng hợp cơ bản
Thực hiện theo các bước sau để tìm ma trận tập cắt cơ bản của đồ thị có hướng đã cho.
Chọn một cây đồ thị có hướng cho trước và biểu diễn các liên kết bằng các đường chấm.
Bằng cách loại bỏ một cành cây và các liên kết cần thiết cùng một lúc, chúng ta sẽ nhận được một bộ f-cut. Điền các giá trị của các phần tử tương ứng với tập cắt f này vào một hàng của ma trận tập cắt cơ bản.
Lặp lại bước trên cho tất cả các cành cây.
Thí dụ
Coi như directed graph , mà chúng ta đã thảo luận trong phần ma trận tỷ lệ. Chọn các nhánh d, e & f của đồ thị có hướng này dưới dạng các nhánh. Vì vậy, các nhánh a, b & c còn lại của đồ thị có hướng này sẽ là các liên kết.
Các twigs d, e & f được biểu diễn bằng các đường liền nét và links a, b & c được biểu diễn bằng các đường chấm trong hình sau.
Bằng cách loại bỏ một cành cây và các liên kết cần thiết cùng một lúc, chúng ta sẽ nhận được một bộ f-cut. Vì vậy, sẽ có ba bộ cắt f, vì có ba nhánh. Ba cái nàyf-cut sets được hiển thị trong hình sau.
Chúng ta sẽ có ba tập cắt f bằng cách loại bỏ tập hợp các nhánh và liên kết của C 1 , C 2 và C 3 . Chúng ta sẽ nhận được các giá trị phần tử khôn ngoan hàng của ma trận tập cắt cơ bản từ mỗi tập cắt f. Nênfundamental cut set matrix trong số các Cây được xem xét ở trên sẽ là
$$ C = \ begin {bmatrix} 1 & -1 & 0 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 & 1 & 0 \\ 1 & 0 & -1 & 0 & 0 & 1 \ kết thúc {bmatrix} $$
Các hàng và cột của ma trận trên đại diện cho các nhánh và nhánh của đồ thị có hướng đã cho. Bậc của ma trận tập cắt cơ bản này là 3 × 6.
Các number of Fundamental cut set matricescủa một biểu đồ có hướng sẽ bằng số Cây của biểu đồ có hướng đó. Bởi vì, mỗi Cây sẽ có một ma trận bộ cắt Cơ bản.