Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Cơ sở dữ liệu
bài giảng các chuyên đề phần 8
Đang chuẩn bị liên kết để tải về tài liệu:
bài giảng các chuyên đề phần 8
Thành Lợi
43
25
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
chiều tới x theo các cạnh thuộc đường thứ nhất, sau đó đi từ x tới y theo đường thứ hai, rồi lại đi từ y tới v theo các cạnh thuộc đường đi thứ nhất. Điều này mâu thuẫn với giả thiết (u, v) là cầu. 4⇒5: "Giữa hai đỉnh bất kỳ của T có đúng một đường đi đơn"⇒"T không chứa chu trình đơn nhưng hễ cứ thêm vào một cạnh ta thu được một chu trình đơn" Thứ nhất T không chứa chu trình đơn vì nếu. | Lý thuyết đồ thị 37 chiều tới x theo các cạnh thuộc đường thứ nhất sau đó đi từ x tới y theo đường thứ hai rồi lại đi từ y tới v theo các cạnh thuộc đường đi thứ nhất. Điều này mâu thuẫn với giả thiết u v là cầu. 4 5 Giữa hai đỉnh bất kỳ của T có đúng một đường đi đ ơn T không chứa chu trình đơn nhưng hễ cứ thêm vào một cạnh ta thu được một chu trình đơn Thứ nhất T không chứa chu trình đơn vì nếu T chứa chu trình đơn thì chu trình đó qua ít nhất hai đỉnh u v. Rõ ràng dọc theo các cạnh trên chu trình đó thì từ u có hai đường đi đơn tới v. Vô lý. Giữa hai đỉnh u v bất kỳ của T có một đường đi đơn nối u với v vậy khi thêm cạnh u v vào đường đi này thì sẽ tạo thành chu trình. 5 6 T không chứa chu trình đơn nhưng hễ cứ thêm vào một cạnh ta thu được một chu trình đơn T liên thông và có n - 1 cạnh Gọi u và v là hai đỉnh bất kỳ trong T thêm vào T một cạnh u v nữa thì theo giả thiết sẽ tạo thành một chu trình chứa cạnh u v . Loại bỏ cạnh này đi thì phần còn lại của chu trình sẽ là một đường đi từ u tới v. Mọi cặp đỉnh của T đều có một đường đi nối chúng tức là T liên thông theo giả thiết T không chứa chu trình đơn nên T là cây và có n - 1 cạnh. 6 1 T liên thông và có n - 1 cạnh T là cây Giả sử T không là cây thì T có chu trình huỷ bỏ một cạnh trên chu trình này thì T vẫn liên thông nếu đồ thị mới nhận được vẫn có chu trình thì lại huỷ một cạnh trong chu trình mới. Cứ như thế cho tới khi ta nhận được một đồ thị liên thông không có chu trình. Đồ thị này là cây nhưng lại có n - 1 cạnh vô lý . Vậy T là cây 2. Định nghĩa Giả sử G V E là đồ thị vô hướng. Cây T V F với FcE gọi là cây khung của đồ thị G. Tức là nếu như loại bỏ một số cạnh của G để được một cây thì cây đó gọi là cây khung hay cây bao trùm của đồ thị . Dễ thấy rằng với một đồ thị vô hướng liên thông có thể có nhiều cây khung. G T1 T.2 T3 Hình 13 Đồ thị G và một số ví dụ cây khung T1 T2 T3 của nó Điều kiện cần và đủ để một đồ thị vô hướng có cây khung là đồ thị đó phải liên thông Số cây khung của đồ thị đầy đủ Kn là .
TÀI LIỆU LIÊN QUAN
Bài giảng Toán lớp 7: Chuyên đề phân số - Ngô Thế Hoàng
Báo cáo đề tài nghiên cứu khoa học: Nghiên cứu ứng dụng phần mềm Catia thiết kế các bài giảng mô phỏng để hỗ trợ và nâng cao chất lượng, hiệu quả giảng dạy các môn học chuyên ngành cơ khí
Bài giảng chuyên đề Bệnh học: Ung thư các xoang mặt
Bài giảng chuyên đề Đường dây điện ngầm: Chương 2 - Phạm Thành Chung
Bài giảng chuyên đề: Dược học - Các thuốc chống trầm cảm
Bài giảng Hệ chuyên gia – Chương 2.2: Logic mệnh đề - Logic vị từ cấp một
Bài giảng Phân tích chình sách thuế_Chương: Định giá chuyển giao giữa các bên liên kết
Bài giảng chuyên đề 1: Phần 2 - Nội dung, phương pháp quản lý trường TH
Bài giảng chuyên đề Tâm thần học: Các rối loạn tâm thần thực tổn
ĐỀ CƯƠNG ÔN THI TỐT NGHIỆP CÁC MÔN CHUYÊN NGÀNH TCDN
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.