Lí thuyết đồ thị part 7

Đồ thị được biểu diễn đồ họa bằng cách vẽ một điểm cho mỗi đỉnh và vẽ một cung giữa hai đỉnh nếu chúng được nối bởi một cạnh. Nếu đồ thị là có hướng thì hướng được chỉ bởi một mũi tên. Không nên lẫn lộn giữa một đồ hình của đồ thị với bản thân đồ thị (một cấu trúc trừu tượng, không đồ họa) bởi có nhiều cách xây dựng đồ hình. Toàn bộ vấn đề nằm ở chỗ đỉnh nào được nối với đỉnh nào, và bằng bao nhiêu cạnh. Trong thực hành, thường rất khó để...
Nội dung trích xuất từ tài liệu:
Lí thuyết đồ thị part 7 e1 , e2 , . . . , eq cua e1 , e2 , . . . , eq ta nhˆn d u.o.c mˆt d` thi Euler m´.i c´ tˆ’ng trong lu.o.ng nho ˙ ¯ ˙¯¯’ ˙ ’ ¯¯ ¯ a ¯. o ¯ˆ . .o o oo . . . .n, mˆu thuˆn. ˜ ho a a Bˆy gi`. x´t d` thi d` y d u K(V1 ) trˆn tˆp c´c d ınh V1 trong d o c´c canh thˆm v`o o e ¯ˆ . ¯a ¯ ˙ ’ e a a ¯˙ ’ a o ˆ ¯´ a . e a . .o.ng w bˇ ng d o d`i cua dˆy chuyˆn nho nhˆ t trong G gi˜.a hai d ınh v ` ` ´ ˙a ’ ˙ ’a ˙ ’ (vi , vj ) c´ trong lu . o. ij a ¯ˆ a e u ¯ . i v` vj . Khi d ´ mˆ i canh cua K(V1 ) tu.o.ng u.ng v´.i mˆt dˆy chuyˆn trong G. V` w(e) ≥ 0 v´.i ˜ ` ˙ ’ a ¯o o . ´ ooa e ı o . moi canh e ∈ E nˆn wij c´ thˆ’ d u.o.c x´c d .nh bˇ ng thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t, ˙ ` ´ ´ e o e ¯ . a ¯i a a a ım ¯ o ¯ a a .. . ˙ ’ chˇng han Floyd (xem 3.3.2) hay Dantzig [16]. a . Dinh l´ 5.2.3 Tˆn tai tu.o.ng u.ng mˆt-mˆt gi˜.a l`.i gia i tˆi u.u cu a b`i to´n ngu.`.i d u.a -. `. ’´ ˙o ˙a ’ y o ´ oouo a o¯ . . thu. Trung Hoa v´.i mˆt cˇp gh´p ho`n ha o c´ trong lu.o.ng nho nhˆ t trong d` thi K(V1 ). ´ ˙o. ’ ˙ ’a o oa e a ¯ˆ . o .. . Ch´.ng minh. X´t mˆt l`.i giai tˆi u.u cua b`i to´n ngu.`.i d u.a thu. Trung Hoa v` d at E l` ’´ ˙o ˙aa ’ u e oo o¯ a ¯ˇ a . . tˆp c´c canh thˆm v`o G. Theo Bˆ’ d` 5.2.1 ta c´ thˆ’ thiˆt lˆp tu.o.ng u.ng v´.i mˆ i d ınh ˙e ˙ ˜’ ´. o ¯˙ aa. e a o ¯ˆ oe ea ´ o . vi ∈ V1 v´.i mˆt d ınh vj ∈ V1 bˇ ng mˆt dˆy chuyˆn so. cˆ p µij m` c´c canh thuˆc E . Theo ` ` ´ o o ¯˙ .’ a oa e a aa . o . . ˙ d` 5.2.2, µij c´ d o d`i nho nhˆ t. Trong d` thi K(V1 ) c´c dˆy chuyˆn µij tu.o.ng u.ng canh ’ ¯ˆ ´ ` ˙a ’ Bˆ e o o ¯ˆ a ¯o . ˆ aa e ´ . . (vi , vj ). Do d o tˆ t ca c´c d ınh cua V1 d u.o.c kˆt ho.p, hai v´.i hai, v` c´c canh (vi , vj ) tu.o.ng ´’ ´ ¯´ a ˙ a ¯˙ ’ ˙ ’ ¯. e . o aa . u.ng dˆy chuyˆn µij cua G , tao th`nh mˆt cˇp gh´p ho`n hao K cua d` thi K(V1 ). (Trong ` ˙ ’ ˙ ’ ˙ ¯o . ’ˆ ´ ...