Đồ Thị Euler, đồ Thị Hamilton.pdf (Bài Giảng Toán Rời Rạc 2) | Tải Miễn ...

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Bài giảng Toán rời rạc 2 - Đồ thị Euler, đồ thị Hamilton pdf 32 1 MB 2 53 4.9 ( 21 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Đang xem trước 10 trên tổng 32 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Bài giảng Toán rời rạc 2 Toán rời rạc 2 Toán rời rạc Đồ thị Euler đồ thị Hamilton Chứng minh đồ thị là nửa Euler

Nội dung

ĐỒ THỊ EULER ĐỒ THỊ HAMILTON Toán rời rạc 2 Nội dung • Đồ thị Euler • Đồ thị Hamilton 2 Đồ thị Euler Khái niệm đồ thị Euler (1/2) • Định nghĩa. – Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. – Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần được gọi là đường đi Euler. – Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler. – Đồ thị có đường đi Euler được gọi là nửa Euler. • Ví dụ 1: 4 Khái niệm đồ thị Euler (2/2) • Ví dụ 2: 5 Điều kiện cần và đủ để đồ thị là Euler • Đồ thị vô hướng – Đồ thị vô hướng liên thông G= là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. • Đồ thị có hướng – Đồ thị có hướng liên thông yếu G= là đồ thị Euler khi và chỉ khi tất cả các đỉnh của nó đều có bán đỉnh bậc ra bằng bán đỉnh bậc vào (điều này làm cho đồ thị là liên thông mạnh) 6 Chứng minh đồ thị là Euler • Với đồ thị vô hướng: – Kiểm tra đồ thị có liên thông hay không? • Kiểm tra DFS(u) = V hoặc BFS(u) = V l iên thông – Kiểm tra bậc của tất cả cả đỉnh có phải số chẵn hay không? • Với ma trận kề, tổng các phần tử của hàng u�(cột u) là bậc của đỉnh u. • Với đồ thị có hướng: – Kiểm tra đồ thị có liên thông yếu hay không? • Kiểm tra đồ thị vô hướng tương ứng là liên thông, hoặc • Kiểm tra nếu tồn tại đỉnh u∈V để DFS(u)=V hoặc BFS(u)=V? – Kiểm tra tất cả các đỉnh có thỏa mãn bán bậc ra bằng bán bậc vào hay không? • Với ma trận kề, bán bậc ra của đỉnh u là deg+(u) là số các số 1 của hàng u, bán bậc vào của đỉnh u là deg-(u) là số các số 1 của cột u. 7 Ví dụ với đồ thị vô hướng • Cho đồ thị vô hướng được biểu diễn dưới dạng ma trận kề như hình dưới. Chứng minh là đồ thị Euler . • Vì BFS(1) = { 1, 2, 6, 3, 5, 7, 4, 11, 8, 10, 12, 9, 13} = V. Do vậy, G liên thông. • Ta lại có: • • • • • • • deg(1) = deg(13) = 2. deg (2) = deg(3) = 4 deg(4) = deg(5) = 4 deg(6) = deg(7) = 4 deg(8) = deg(9) = 4 deg(10) = deg(11) = deg(12) = 4 8 Ví dụ với đồ thị có hướng • Cho đồ thị có hướng được biểu diễn dưới dạng ma trận kề như hình dưới. Chứng minh là đồ thị Euler . 9 Thuật toán tìm chu trình Euler 10 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Lý thuyết Dow Trắc nghiệm Sinh 12 Mẫu sơ yếu lý lịch Đề thi mẫu TOEIC Đồ án tốt nghiệp Thực hành Excel Tài chính hành vi Bài tiểu luận mẫu Giải phẫu sinh lý Atlat Địa lí Việt Nam Đơn xin việc Hóa học 11 adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này