tailieunhanh - Giáo trình đồ thị

trong thực tế để miêu tả một tình huống người ta thường biểu thị bằng một hình ảnh gồm các điểm(các đỉnh)-biểu diễn các thực thể - và vẽ các đoạn thẳng nối cặp các đỉnh biểu diễn mối quan hệ giữa chúng. Những hình ảnh như thế thường gọi là các đồ thị. | Muc luc Leri nói đầu 7 1 Dili cương về đo thi 9 Dinh nghĩa và các khái niệm. 9 Dệ thi có hướng. 9 Dó thi vá ánh xa đa tri. 10 Đó thi vó hướng . 10 Các đinh nghĩa chánh. 11 Ma trán biệu điện đó thi. 13 . Ma trận liện thuóc đỉnh-cung. 13 Ma tran liện thuôc đỉnh-canh. 15 . . . Ma trôn kô hay ma tran liôn thuôc đỉnh-đỉnh . 17 . . . Cac biôu đi n ciỉa đó thi. 18 . Tính liện thông. 23 Dệy chuyện và chu trành. 23 Dường đi va mạch. 24 Tính liện thệng. 24 1 Cầu k liên thông. 28 Đô thi liôn thong mạnh. 31 Phạm vi vạ liôn thong mạnh. 33 Mạ trạô. n phạ. m vi . 33 Tìm các thạnh phôn liôn thông mạnh. 36 Cơ sở. 39 Đạng côu cUạ cạc dô thi. 41 1 dẳng cạu. 42 2 dạng cạu. 43 Các đô thi dạc biôt. 46 E ồ thi khong cá mạch . 46 Đo thi phạng. 46 2 Cac so co ban của đồ thi 49 Chu so. 49 Sẳạác soôá . 52 Cạch tìm sẳc so. 54 Sô ổn đinh trong. 55 So o n đinh ngoại. 61 Phu . 65 Nhạn cuạ đô thi. 69 . Các đinh ly vô tôn tại và duy nhất. 69 Trà chơi Nim. 72 2 3 Các bái toán về đường đi 75 Đường đi giữa hai đỉnh . 75 Đường đi giữa hai đỉnh . 75 Đồ thi liên thông manh. 76 Đường đi ngắn nhêt giữa hai đỉnh . 78 Trường hợp ma trận trông lượng khêng am. 78 Trường hợp ma trân trông lượng tuy ý. 82 Đường đi ngắn nhat giữa têt ca các cặp đỉnh. 87 Thuêt tôán Heđetniemi trường hợp ma trên trông lượng khêng am 88 Thuêt tôán Flôýđ trường hợp ma trên trông lượng tuý ý . 93 Phát hiên mach cá đê đài am. 96 Mach tối ưu trông đồ thi cá hai trông lượng. 96 4 CAY 99 Mở đêu. 99 Cêý Huffman. 101 Cac bê ma tốt . 101 Mã Huffman. 103 Cêý baô trum. 105 Thuêt tôán tìm kiêm theô chiêu rống xác đinh câý baô trùm. 107 Thuêt tôán tìm kiêm theô chiêu sau xác đinh cêý baô trum . 107 Tìm câý baô tràm đựa trên hai mang tuýốn tính. 108 Thuêt .