TAILIEUCHUNG - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG III ĐỒ THỊ_5

Chứng minh: Bất đẳng thức n k m được chứng minh bằng quy nạp theo m. Nếu m=0 thì k=n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m 1, với m 1. | CHƯƠNG III ĐỒ THỊ . Định lý Cho G là một đơn đồ thị có n đỉnh m cạnh và k thành phần liên thông. Khi đó n - k n - k 1 n - k m --- -------- . 2 Chứng minh Bất đẳng thức n - k m được chứng minh bằng quy nạp theo m. Nếu m 0 thì k n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m-1 với m 1. Gọi G là đồ thị con bao trùm của G có số cạnh m0 là nhỏ nhất sao cho nó có k thành phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G cũng tăng số thành phần liên thông lên 1 và khi đó đồ thị thu được sẽ có n đỉnh k 1 thành phần liên thông và m0-1 cạnh. Theo giả thiết quy nạp ta có m0-1 n- k 1 hay m0 n-k. Vậy m n-k. Bổ sung cạnh vào G để nhận được đồ thị G có m1 cạnh sao cho k thành phần liên thông là những đồ thị đầy đủ. Ta có m m1 nên chỉ cần chứng minh m n - k n - k 1 37 Giả sử Gi và Gj là hai thành phần liên thông của G với ni và nj đỉnh và ni nj 1 . Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với ni 1 và nj-1 đỉnh thì tổng số đỉnh không thay đổi nhưng số cạnh tăng thêm một lượng là ni 1 ni ni ni -1 2 2 nj nj -1 nj - 1 nj - 2 . _-------------- -------- n -nị 1. 2 2 i j Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả . Vì vậy m1 là lớn nhất n k là cố định khi đồ thị gồm k-1 đỉnh cô lập và một đồ thị đầy đủ với n-k 1 đỉnh. Từ đó suy ra bất đẳng thức cần tìm. . Định nghĩa Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v và đường đi từ v tới u. Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là liên thông. Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. Thí dụ 20 38 G G Đồ thị G là liên thông mạnh nhưng đồ thị G là liên thông yếu không có đường đi từ u tới x cũng như từ x tới u . . Mệnh đề Cho G là một đồ thị vô hướng hoặc có hướng với ma trận liền kề A theo thứ tự các đỉnh v1 v2 . vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới

• Toán học
• thuật toán
• khái niệm thuật toán
• toán rời rạc
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Thuật toán và tư duy thuật toán
• Đặc trưng cơ bản về thuật toán
• Thiết kế thuật toán
• Hiệu quả giảng dạy thuật toán
• Cài đặt thuật toán
• Vấn đề tư duy thuật toán
• Ngôn ngữ lập trình
• Bài giảng thuật toán
• Biểu diễn thuật toán
• Kỹ thuật thiết kế thuật toán
• Phân tích thuật toán
• Đáng giá thuật toán
• Thuật toán máy tính
• Thuật toán tham lam
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Tự học lập trình
• Bài giảng Tin học 10
• Bài giảng Tin học 10 Bài 4
• Bài 4 Bài toán và thuật toán
• Bài giảng Bài toán và thuật toán
• Khái niệm bài toán
• Thuật toán tìm Max của một dãy số
• Cẩm nang thuật toán
• Phương pháp giải thuật toán
• Thuật toán thông dụng
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Thuật toán xử lý chuỗi
• Thuật toán chuyên dụng
• Một số vấn đề về thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• thuật toán DDA
• thuật toán bresenham
• thuật toán đường tròn
• thuật toán MidPoint
• thuật toán vẽ Ellipse
• Thuật toán tô màu
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Thuật toán Google
• Thuật toán Sand
• Thuật toán chim ruồi
• Thuật toán ngựa vằn Zebra Box
• Thuật toán Chim cánh cụt
• Thuật toán Gấu trúc Panda
• Đề thi cuối kì môn Toán kỹ thuật
• Bài thi môn Toán kỹ thuật
• Ôn thi Toán kỹ thuật
• Luyện thi Toán kỹ thuật
• Tài liệu thi Toán kỹ thuật
• Hướng dẫn thi Toán kỹ thuật
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi ngắn nhất
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Thuật toán xử lý thông tin
• Đặc trưng của thuật toán
• Thuật toán Euclid cải tiến
• Ngôn ngữ thuật toán
• Diễn tả thuật toán
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Trình diễn thuật toán
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Tính chất của thuật toán
• Đặc tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Quy hoạch động
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Khóa luận tốt nghiệp
• Khóa luận tốt nghiệp Kế toán Kiểm toán
• Kế toán Kiểm toán
• Kế toán thanh toán
• Nguyên tắc kế toán thanh toán với người mua
• Nguyên tắc kế toán thanh toán với người bán
• Thuật toán gần đúng
• Bài toán tối ưu tổ hợp
• Tối ưu tổ hợp
• Toán tối ưu tổ hợp
• Ứng dụng thuật toán gần đúng
• Tìm hiểu thuật toán gần đúng
• Tài liệu thuật toán gần đúng
• Sáng kiến kinh nghiệm
• Bài tập xây dựng thuật toán giải bài toán
• Thuật toán giải bài toán
• Xây dựng thuật toán máy tính
• Kỹ thuật kiểm toán
• tài liệu Kỹ thuật kiểm toán
• bài giảng Kỹ thuật kiểm toán
• kế toán kiểm toán
• nghiệp vụ kế toán
• kế toán tài chính
• kế toán doanh nghiệp