Một bà i toán về đồ thị

[nguyendung_hy]

Định nghĩa1:Ma trận A được gọi là ma trận hoàn toàn đơn modun nếu mọi định thức con khác 0 của nó đều có trị tuyệt đối là 1
Định nghĩa 2:Đồ thị G=(V,E) trong đó V={1,2,...,n} E={e1,e2,...em} là đơn đồ thị có hướng,xây dựng ma trận A={a(ij)|i=1,2,..,n j=1,2,..,m} trong đó
a(ij)=1 nếu đỉnh i là đỉnh đầu của cung ej
a(ij)=-1 nếu đỉnh i là đỉnh cuối của cung ej
a(ij)=0 nếu đỉnh i không là đầu mút của cung ej
Ma trận A xây dựng như trên gọi là ma trận liên thuộc đỉnh-cạnh
Chứng minh:
Ma trận liên thuộc đỉnh cạnh của đơn đồ thị có hướng là hoàn toàn đơn modun
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]