tailieunhanh - Phần tích thiết kế giải thuật (phần 14)

Đồ thị là một phần quan trọng trong ngành công nghệ thông tin, và trong tài liệu này các bạn cũng sẽ làm quen với lí thuyết đồ thị và một sô kiến thức quan trọng của đồ thị cơ bản | Định nghĩa ĐỒ thi phang Một đồ thị vô hướng G được gọi là phang nếu tồn tại một càch vế G trọng mạt phàng sàồ chô không cồ hài cạnh nàô cUà G càt nhàu. Khi G là một đô thị phàng thì môi càch vế G trọng màt phàng sàô chô không cô hài cành nàô cUà G càt nhàu được gôi là môt biếu diến phàng cUà G. Ly Thuyết Đo Thị - Đo Thị Phang - Khoa CNTT - Đai Học KHTN 2 1 Định nghĩa Ghi chu hai cạnh co chung một đỉnh được qui ước là không càt nhau Ly Thuyết Đổ Thị - Đổ Thị Phang - Khoa CNTT - Đai Học KHTN 3 Định nghĩa Ví du Đô thị G1 là đô thị phàng và càc đô thị G2 G3 là Ly Thuyết Đổ Thị - Đổ Thị Phang - Khoa CNTT - Đai Học KHTN 4 2 Định nghĩa b Phép biên đổi đồng phôi Thêm vàô 1 đỉnh nằm trên 1 cạnh hay gổp 2 cạnh cổ chung đỉnh bạc 2 thành 1 cạnh. c Đổ thi đồng phổi Hai đổ thi được gổi là đổng phổi nếu mổì đổ thi cổ được từđổ thi kia bằng càch thực hiên mổt dày càc phép biến đổi đổng phổi. Đinh ly Nếu G là một đổ thi phàng thì tà cổ thê tìm một đổ thi G1đổng phổi vôi G sàổ chổ cổ thê vê G1 bàng càch chỉ dung càc đổàn thàng. Lý Thuyết Đo Thị - Đo Thị Phang - Khoa CNTT - Đai Học KHTN 5 Định nghĩa Càc đổ thi sàu đày đổng phổi Lý Thuyết Đo Thị - Đo Thị Phang - Khoa CNTT - Đai Học KHTN 6