Đồ thị và các thuật toán – Chương 1: Đại cương về đồ thị

Đồ thị và các thuật toán – Chương 1 trình bày những kiến thức cơ bản về đồ thị như: Định nghĩa và các khái niệm, ma trận biểu diễn đồ thị, tính liên thông, phạm vi và liên thông mạnh, đẳng cấu của các đồ thị, các đồ thị đặc biệt. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Đồ thị và các thuật toán – Chương 1: Đại cương về đồ thị Mu.c lu.c o.i n´ L` oi d`au ¯ˆ 7 - a.i cu.o.ng vˆ 1 D `e d`o thi. ¯ˆ 9 1.1 - i.nh ngh˜ıa v`a c´ac kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . D 9 1.1.1 - `ˆo thi. c´o hu.´o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 9 1.1.2 - `ˆo thi. v`a ´anh xa. d¯a tri. . . . . . . . . . . . . . . . . . . . . . . . . . . D 10 1.1.3 - `ˆo thi. vˆo hu.´o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 10 1.1.4 C´ac d¯i.nh ngh˜ıa ch´ınh . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Ma trˆa.n biˆe˙’u diˆ˜en d¯`ˆo thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 Ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-cung . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2 Ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-ca.nh . . . . . . . . . . . . . . . . . . . . . . 15 1.2.3 `e hay ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-d¯ı˙’nh . . . . . . . . . . . . . Ma trˆa.n kˆ 17 1.2.4 C´ac biˆe˙’u diˆ˜en cu˙’a d¯`oˆ thi. . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 T´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 `en v`a chu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . Dˆay chuyˆ 23 1.3.2 - u.`o.ng d¯i v`a ma.ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 24 1.3.3 T´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1 http://www.ebook.edu.vn 1.3.4 `au, k−liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cˆ 28 1.3.5 - `ˆo thi. liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . D 31 1.4 Pha.m vi v`a liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4.1 Ma trˆa.n pha.m vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4.2 `an liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . T`ım c´ac th`anh phˆ 36 1.4.3 Co. so˙’. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5 - ˇa˙’ng cˆa´u cu˙’a c´ac d¯`ˆo thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 41 1.5.1 1−d¯ˇa˙’ng cˆa´u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.5.2 2−d¯ˇa˙’ng cˆa´u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.6 C´ac d¯`oˆ thi. d¯aˇ. c biˆe.t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.6.1 - `ˆo thi. khˆong c´o ma.ch . . . . . . . . . . . . . . . . . . . . . . . . . . D 46 1.6.2 - `ˆo thi. phˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 46 2 C´ o´ co. ba˙’n cu˙’a d ac sˆ `o thi. ¯ˆ 49 2.1 Chu sˆo´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2 Sˇa´c sˆo´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.1 C´ach t`ım sˇa´c sˆo´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3 Sˆo´ ˆo˙’n d¯.inh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Sˆo´ ˆo˙’n d¯.inh ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Phu˙’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.6 Nhˆan cu˙’a d¯`ˆo thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.6.1 C´ac d¯i.nh l´ `e tˆ y vˆ `on ta.i v`a duy nhˆa´t . . . . . . . . . . . . . . . . . . . 69 2.6.2 Tr`o cho.i Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2 http://www.ebook.edu.vn 3 C´ ac b` ai to´ an vˆ ¯u.` `e d o.ng d ...