0.3 Các ma trận mạng và phạm vi ứng dụng  (Page 2/3)

7643215Hình 4.3 : Vòng cơ bản định hướng theo graph liên thông FGE40312

Vết cắt là tập hợp của các nhánh, nếu bỏ đi hoặc chia graph liên thông thành hai graph con liên thông. Nhóm vết cắt có thể chọn độc lập duy nhất nếu mỗi vết cắt chỉ bao gồm một nhánh cây. Vết cắt độc lập như vậy gọi là vết cắt cơ bản. Số vết cắt cơ bản đúng bằng số nhánh cây. Sự định hướng của vết cắt cơ bản được chọn giống như hướng của nhánh cây. Vết cắt cơ bản của graph cho trong hình 4.2 được trình bày trong hình 4.4

7643215Hình 4.4 : Vết cắt cơ bản định hướng theo graph liên thông BDCA01423

4.3. MA TRẬN THÊM VÀO.

4.3.1. ma trận thêm vào nhánh - nút â.

Sự liên hệ giữa nhánh và nút trong graph liên thông trình bày bởi ma trận thêm vào nhánh nút. Các thành phần của ma trận được trình bày như sau:

aịj = 1 : Nếu nhánh thứ i và nút thứ j có chiều hướng từ nhánh i vào nút j

aịj = -1: Nếu nhánh thứ i và nút thứ j có chiều hướng từ nhánh i ra khỏi nút j

aịj = 0 : Nếu nhánh thứ i và nút thứ j không có mối liên hệ với nhau.

Kích thước của ma trận là e x n, với e là số nhánh và n là số nút của graph. Ma trận thêm vào nhánh nút cho trong graph hình 4.2 trình bày như trên. Với:

Đ = 111-1-1-1-11-11-111-11234567en40123 $\sum _{j=0}^4{a}_{ij}=0i=\mathrm{1,}\mathrm{2,}\text{.}\text{.}\text{.}e$

Các cột của ma trận  là phụ thuộc tuyến tính. Vì vậy hạng của Â<n.

4.3.2. ma trận thêm vào nút a.

Các nút của graph liên thông có thể chọn làm nút qui chiếu. Nút qui chiếu có thể thay đổi, nó được xem như một nút trong graph có thể cân nhắc khi ấn định cụ thể một nút nào đó làm nút qui chiếu. Ma trận thu được từ ma trận  bỏ đi cột tương ứng với nút chọn làm nút qui chiếu là ma trận nhánh - nút A, nó sẽ được gọi là ma trận nút. Kích thước của ma trận là e x (n-1) và hạng là n-1 = b.

Với: b là số nhánh cây của graph. Chọn nút 0 làm nút qui chiếu thể hiện trên graph trong hình 4.2.

nút1234567eA = -1-1-1-11-11-111-14123

Ma trận A là hình chữ nhật và là duy nhất. Nếu hàng của A sắp xếp theo một cây riêng biệt thì ma trận trên có thể phân chia thành các ma trận con Ab có kích thước b x (n-1) và At có kích thước là l x (n-1). Số hàng của ma trận Ab tương ứng với số nhánh cây và số hàng của ma trận At tương ứng với số nhánh bù cây. Ma trận phân chia của graph trên hình 4.2 được trình bày như sau:

nútnút1234567eA = -1-1-1-11-11-111-1e= AtCác nútAbNhánh câyNhánh bù cây4123

Ab là ma trận vuông không duy nhất với hạng (n -1).

4.3.3. Ma trận hướng đường - nhánh cây K:

Hướng của các nhánh cây đến các đường trong 1 cây được trình bày bằng ma trận hướng đường - nhánh cây. Với 1 đường được định hướng từ 1 nút qui chiếu. Các phần tử của ma trận này là:

kij = 1: Nếu nhánh cây i nằm trong đường từ nút j đến nút qui chiếu và được định hướng cùng hướng.

kij = -1: Nếu nhánh cây i nằm trong đường từ nút j đến nút qui chiếu nhưng được định hướng ngược hướng.

kij = 0: Nếu nhánh cây i không nằm trong đường từ nút j đến nút qui chiếu.

Với nút 0 là nút qui chiếu ma trận hướng đường - nhánh cây liên kết với cây được trình bày ở hình 4.2 có dạng dưới đây.

đường1234Nhánh câyK = -1-1-1-1-14123

Đây là ma trận vuông không duy nhất với cấp là (n-1). Ma trận hướng - đường nhánh cây liên hệ nhánh cây với các đường nhánh cây nối đến nút qui chiếu và ma trận Ab liên kết các nhánh cây với các nút. Vì vậy có tỉ lệ tương ứng 1:1 giữa các đường và các nút.