Lý thuyết mạng - Cấu trúc liên kết mạng

Cấu trúc liên kết mạng là một biểu diễn đồ họa của các mạch điện. Nó rất hữu ích để phân tích các mạch điện phức tạp bằng cách chuyển đổi chúng thành đồ thị mạng. Cấu trúc liên kết mạng còn được gọi làGraph theory.

Thuật ngữ cơ bản của cấu trúc liên kết mạng

Bây giờ, chúng ta hãy thảo luận về các thuật ngữ cơ bản liên quan đến cấu trúc liên kết mạng này.

Đồ thị

Biểu đồ mạng được gọi đơn giản là graph. Nó bao gồm một tập hợp các nút được kết nối bởi các nhánh. Trong đồ thị, một nút là điểm chung của hai hoặc nhiều nhánh. Đôi khi, chỉ một nhánh duy nhất có thể kết nối với nút. Nhánh là một đoạn thẳng nối hai nút.

Bất kỳ mạch điện hoặc mạng nào cũng có thể được chuyển đổi thành tương đương của nó graphbằng cách thay thế các phần tử thụ động và các nguồn điện áp bị ngắn mạch và các nguồn dòng điện bị hở mạch. Điều đó có nghĩa là, các đoạn thẳng trong biểu đồ biểu diễn các nhánh tương ứng với các phần tử thụ động hoặc các nguồn điện áp của mạch điện.

Thí dụ

Chúng ta hãy xem xét những điều sau electric circuit.

Trong đoạn mạch trên, có four principal nodes và những người đó được gắn nhãn 1, 2, 3 và 4. Có seven branches Trong đoạn mạch trên, trong đó một nhánh chứa nguồn điện áp 20 V, nhánh khác chứa nguồn dòng 4 A và năm nhánh còn lại chứa các điện trở có điện trở lần lượt là 30 Ω, 5 Ω, 10 Ω, 10 Ω và 20 Ω.

Một tương đương graph ứng với mạch điện trên được biểu diễn trong hình sau.

Trong biểu đồ trên, có four nodesvà chúng được gắn nhãn tương ứng là 1, 2, 3 & 4. Chúng giống như của các nút chính trong mạch điện. Cósix branches trong đồ thị trên và chúng được đánh dấu lần lượt là a, b, c, d, e & f.

Trong trường hợp này, chúng tôi có one branch less trong đồ thị vì nguồn dòng 4 A làm mạch hở, đồng thời biến đổi mạch điện thành đồ thị tương đương của nó.

Từ Ví dụ này, chúng ta có thể kết luận những điểm sau:

Các number of nodes hiện trong đồ thị sẽ bằng số nút chính có trong mạch điện.
Các number of branches hiện trong một đồ thị sẽ nhỏ hơn hoặc bằng số nhánh có trong một mạch điện.

Các loại đồ thị

Sau đây là các loại đồ thị:

Biểu đồ được kết nối
Đồ thị không kết nối
Đồ thị hướng
Đồ thị vô hướng

Bây giờ, chúng ta hãy thảo luận từng đồ thị một.

Biểu đồ được kết nối

Nếu tồn tại ít nhất một nhánh giữa bất kỳ nút nào trong số hai nút của biểu đồ, thì nó được gọi là connected graph. Điều đó có nghĩa là mỗi nút trong biểu đồ được kết nối sẽ có một hoặc nhiều nhánh được kết nối với nó. Vì vậy, không có nút nào sẽ hiển thị là bị cô lập hoặc tách biệt.

Biểu đồ được hiển thị trong Ví dụ trước là connected graph. Ở đây, tất cả các nút được kết nối bởi ba nhánh.

Đồ thị không kết nối

Nếu tồn tại ít nhất một nút trong biểu đồ mà vẫn không được kết nối bởi một nhánh chẵn, thì nó được gọi là unconnected graph. Vì vậy, sẽ có một hoặc nhiều nút cô lập trong một đồ thị không được kết nối.

Hãy xem xét đồ thị được hiển thị trong hình sau.

Trong đồ thị này, các nút 2, 3 và 4 được nối với nhau bằng hai nhánh. Tuy nhiên, thậm chí không có một nhánh nào được kết nối vớinode 1. Vì vậy, nút 1 trở thành mộtisolated node. Do đó, biểu đồ trên là mộtunconnected graph.

Đồ thị hướng

Nếu tất cả các nhánh của biểu đồ được biểu diễn bằng các mũi tên, thì biểu đồ đó được gọi là directed graph. Các mũi tên này chỉ ra hướng của dòng điện trong mỗi nhánh. Do đó, biểu đồ này còn được gọi làoriented graph.

Hãy xem xét đồ thị được hiển thị trong hình sau.

Trong đồ thị trên, chiều của dòng điện được biểu diễn bằng một mũi tên trong mỗi nhánh. Do đó, nó là mộtdirected graph.

Đồ thị vô hướng

Nếu các nhánh của biểu đồ không được biểu diễn bằng các mũi tên, thì biểu đồ đó được gọi là undirected graph. Vì không có hướng của dòng điện, đồ thị này còn được gọi làunoriented graph.

Biểu đồ được hiển thị trong Ví dụ đầu tiên của chương này là một unoriented graph, bởi vì không có mũi tên nào trên các nhánh của biểu đồ đó.

Subgraph và các loại của nó

Một phần của biểu đồ được gọi là subgraph. Chúng tôi nhận được đồ thị con bằng cách loại bỏ một số nút và / hoặc nhánh của một đồ thị nhất định. Vì vậy, số nhánh và / hoặc nút của đồ thị con sẽ ít hơn số lượng của đồ thị ban đầu. Do đó, chúng ta có thể kết luận rằng một đồ thị con là một tập hợp con của đồ thị.

Sau đây là two types trong số các đồ thị con.

Tree
Co-Tree

Cây

Cây là một đồ thị con được kết nối của một đồ thị đã cho, chứa tất cả các nút của đồ thị. Tuy nhiên, không nên có bất kỳ vòng lặp nào trong đồ thị con đó. Cành cây được gọi làtwigs.

Hãy xem xét những điều sau connected subgraph của đồ thị, được hiển thị trong Ví dụ ở đầu chương này.

Đồ thị con được kết nối này chứa tất cả bốn nút của đồ thị đã cho và không có vòng lặp. Do đó, nó là mộtTree.

Cây này chỉ có ba nhánh trong số sáu nhánh của biểu đồ đã cho. Bởi vì, nếu ta xét nhánh chẵn của các nhánh còn lại của đồ thị thì trong đồ thị con liên thông trên sẽ có một vòng lặp. Khi đó, đồ thị con được kết nối kết quả sẽ không phải là Cây.

Từ Cây trên, chúng ta có thể kết luận rằng number of branches có mặt trong Cây phải bằng n - 1 trong đó 'n' là số nút của đồ thị đã cho.

Cây đồng

Co-Tree là một đồ thị con, được hình thành với các nhánh bị loại bỏ trong khi tạo thành một Cây. Do đó, nó được gọi làComplementcủa một cái cây. Với mỗi Cây, sẽ có một Cây cùng loại tương ứng và các nhánh của nó được gọi làlinkshoặc hợp âm. Nói chung, các liên kết được biểu diễn bằng các đường chấm.

Các Co-Tree tương ứng với Cây trên được thể hiện trong hình sau.

Co-Tree này chỉ có ba nút thay vì bốn nút của đồ thị đã cho, bởi vì Nút 4 được tách biệt với Co-Tree ở trên. Do đó, Co-Tree không cần phải là một đồ thị con được kết nối. Cây Co-Tree này có ba nhánh và chúng tạo thành một vòng lặp.

Các number of brancheshiện diện trong một cây đồng sẽ bằng hiệu giữa số nhánh của một đồ thị nhất định và số nhánh cây. Về mặt toán học, nó có thể được viết là

$$ l = b - (n - 1) $$

$$ l = b - n + 1 $$

Ở đâu,