Một bài toán về đồ thị Đị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 |
Múi giờ GMT. Hiện tại là 05:02 AM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.