Lí thuyết đồ thị part 8

Có nhiều cách khác nhau để lưu trữ các đồ thị trong máy tính. Sử dụng cấu trúc dữ liệu nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trên lý thuyết, người ta có thể phân biệt giữa các cấu trúc danh sách và các cấu trúc ma trận. Tuy nhiên, trong các ứng dụng cụ thể, cấu trúc tốt nhất thường là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏi...
Nội dung trích xuất từ tài liệu:
Lí thuyết đồ thị part 8tuyˆn cua n´ theo gia thiˆt quy nap lˆp th`nh mˆt co. so. gˆm c´c chu tr` d ˆc lˆp. Khi ´˙o ´ ˙` ’ ˙ ’ ’o e e .a a o a ınh ¯o a . . .. .u han m´.i m` chu tuyˆn l` mˆt chu tr` khˆng phu thuˆc ´ ˙. . ’tra lai canh e, ta c´ mˆt diˆn h˜ oo eu oa eao ınh o o . . . . . . .´.c (v` n´ ch´.a mˆt canh khˆng thuˆc v`o mˆt chu tr` n`o trong sˆ ´v`o c´c chu tr` tru o aa ınh ıo u o. o oa o ınh a o . . . ´y). Do bˆ’ sung mˆt canh khˆng thˆ’ l`m tˇng chu sˆ lˆn qu´ mˆt d o.n vi, nˆn ˙ ˙a a ´ec´c chu tr` ˆ a ınh a o o. o e o a o¯ .e . .sˆ diˆn h˜.u han cua d` thi G qua l` x´c d inh mˆt co. so. gˆm c´c chu tr` d ˆc lˆp. ´. ˙` ˙ ¯o . ’ˆ ˙ a a ¯. ’ ’o oeu o a ınh ¯o a . . ..Hˆ qua 6.3.2 [Euler, 1752] Gia su. G l` d` thi tˆ pˆ phˇ ng liˆn thˆng n d ı’nh, m canh v` ˙ ’ ˙ ’ ˙˙ ’’ ¯˙ e a ¯ˆ . o o a o e o a . .f diˆn. Khi d ´ e ¯o . f = m − n + 2.Ch´.ng minh. Thˆt vˆy, sˆ c´c diˆn h˜.u han bˇ ng chu sˆ ν (G), nˆn ` ´ ´ u a a oa eu a o e .. . . f = ν (G) + 1 = (m − n + 1) + 1 = m − n + 2. C˜ng c´ thˆ’ ch´.ng minh c´ch kh´c nhu. sau. ˙ u oeu a a Nhˆn x´t rˇ ng chı cˆn ch´.ng minh cho mˆt d o.n d` thi, v` viˆc thˆm mˆt khuyˆn hoˇc ae` ˙` ’a a u o¯ ¯ˆ . ı e o e o e a . . . . . .n gian l` tˇng sˆ diˆn v` sˆ canh cua d` thi lˆn mˆt d o.n vi. ´. ´ ˙¯ ’ ˙ aa ’ ˙ ¯o . e ’ˆthˆm mˆt canh song song chı d o e o. o e ao. o¯ . . .Ch´ng ta c˜ng c´ thˆ’ xo´ tˆ t ca c´c d ınh treo v` c´c canh liˆn thuˆc n´. Nˆu thˆm (hoˇc ˙ ´’ ´ o e a a ˙ a ¯˙ ’ u u aa . e ooe e a . .b´.t) mˆt canh v` mˆt d ınh th` hiˆu sˆ (m − n) khˆng d ˆ’i.˙ .´ a o ¯˙ .’ o o. ıeo o ¯o . V` mˆ i d o.n d` thi phˇng c´ thˆ’ biˆ’u diˆn trˆn mˇt phˇng sao cho mˆ i canh l` mˆt ˙˙ ˜ ˙ ’ ˜ ˙ ’ ˜ ...