Đang chuẩn bị liên kết để tải về tài liệu:
Đồ thị và các thuật toán - Chương 2

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 2 Các số cơ bản của đồ thị | Chương 2 Các số cơ bản của do thi 2.1 Chủ so Khái niệm mà chung ta sẽ de cập ở đây không phu thuộc vào sự định huáng ta sẽ nói về cạnh chú- khậng phài cung. Dậ tóng quàt xát da dó thi về hướng G V E cá n dính m canh và p thành phận liền thóng. Dặt p G n P G m p G m n p. Ta g ọi G là chu sô cúa dó thi G. Dinh ly 2.1.1 Cho đa đồ thi vô hướng G V E . Gia su G là đồ thi nhận được từ G bằng càch nối hai đỉnh a và b của G bởi môt canh mới nếu a và b trùng nhau hoậc cồ thể nối vối nhau bởi môt day chuyen cởa G thà p G0 p G G0 G 1 trong trường hợp ngược lai p G0 p G 1 G0 G . Chứng minh. Theó cach xậy dựng đa đó thi G0 cá n n dỉnh m m 1 canh va gia sú G cá p thanh phận liận thậng. Nậu a b hóặc cá mật dậy chuyận nói a với b. Khi đó phép biận dổi G thanh G khậng thay đói só thanh phận hận thóng tức la p p. Dó đó p G0 n p n p p G G0 m p G0 G 1. 49 Ngược lại nếu a b và không ton tại dây chuyền nối a và b thì do cách xác định G0 ta có p p 1. Suy rạ p G n p n p 1 n p 1 p G 1 G0 m p G0 m 1 p G 1 m p G G . Hệ quả 2.1.2 p G 0 và G 0. Chứng minh. Thết vốy xuết phát tù dô thị thành lạp bâng câc đỉnh của đa đế thị vế hướng G đỉnh no cố lạp với đỉnh kia ta xây đựng G dân đốn từng cạnh mót khởi dốu ta có p 0 0 mói khi thêm mốt cạnh thì hoặc p tâng va luc đá khống do i hoặc tăng và luc đá p khống đối. Như vạy trong qua trình xây đựng đo thi G các so p va chỉ cá thố tâng. Đố co thể vốn đung những kốt qua phong phu ciỉâ deli so vector trong việc nghiên cứu người ta thường đặt Iii o ng ứng mối chu trình trong G với mốt vector theo câch sau dốy. Mối cạnh cua đa đo thi G dốu duofc đinh hướng mốt câch tuy y nốu chu trình p đi qua cạnh ek rk lan thuạn hướng vì sk lốn ngược hướng thì ta đặt ck rk sk nốu ek lâ mốt khuyốn thì ta luốn qui ước sk 0 . Vector m chi 0u C1 C2 . Cm goi la vector chu trình tương ứng với p vì ky hiộu lì fi hay lì p nốu khong thố gốy ra nhâm lẫn . Các chu trình p p g . goi lâ độc lập nốu câc vector chu trình tương ứng độc lốp tuyốn tính Chu y rang đinh nghĩa nay khong phu .