zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Lý thuyết đồ thị: Chương 4 - Nguyễn Trần Phi Phượng

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:13

Báo xấu

120
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị Euler và đồ thị Halmiton do Nguyễn Trần Phi Phương thực hiện giới thiệu tới các bạn những nội dung về đồ thị Euler; đồ thị Hamilton. Bài giảng phục vụ cho các bạn chuyên ngành Toán học và những bạn quan tâm tới lĩnh vực này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 4 - Nguyễn Trần Phi Phượng

Chương 4 ĐỒ THỊ EULER và ĐỒ THỊ HALMITON
4.1 Đồ thị Euler Định nghĩa Xét đồ thị G = (V,E) – Đường đi đơn trong G được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. – Chu trình đơn trong G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. – Đồ thị G được gọi là đồ thị Euler nếu có chu trình Euler. – Đồ thị G được gọi là đồ thị nửa Euler nếu có đường đi Euler. 26/03/2011 Lý thuyết đồ thị 2
4.1 Đồ thị Euler 3 Ví dụ: Đồ thị G1có các đường đi Euler là: 2 4 G1 d1: 1 2 3 4 2 5 4 1 5 1 5 d2: 1 2 4 3 2 5 1 4 5 Đồ thị nửa Euler … 3 Đồ thị G2 có các chu trình Euler là: 2 4 C1: 1 2 3 4 2 5 4 1 5 6 1 G2 C2: 1 2 4 3 2 5 1 4 5 6 1 1 5 … Đồ thị Euler 6 26/03/2011 Lý thuyết đồ thị 3
4.1 Đồ thị Euler Định lý 1 Đồ 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. Hệ quả Đồ thị vô hướng liên thông G là đồ thị nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. 26/03/2011 Lý thuyết đồ thị 4
4.1 Đồ thị Euler Thuật toán Fleury xác định chu trình Euler Xuất phát từ một đỉnh bất kỳ của G, đi theo các cạnh một cách tùy ý, chỉ cần tuân thủ hai quy tắc sau: i) Xóa bỏ cạnh đã đi qua và đồng thời xóa cả những đỉnh cô lập tạo thành. ii) Ở mỗi bước, chỉ đi qua cầu khi không còn cách chọn lựa nào khác. a b c d Ví dụ: Tìm chu trình ở Euler trong đồ thị h g f e 26/03/2011 Lý thuyết đồ thị 5
4.1 Đồ thị Euler Định lý 2 Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi deg+(v) = deg-(v), ∀v∈V 26/03/2011 Lý thuyết đồ thị 6
4.2 Đồ thị Hamilton Định nghĩa Xét đồ thị G = (V,E) – Đường đi trên G được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. – Chu trình trên G được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. – Đồ thị G được gọi là đồ thị Hamilton nếu có chu trình Hamilton. – Đồ thị G được gọi là đồ thị nửa Hamilton nếu có đường đi Hamilton. 26/03/2011 Lý thuyết đồ thị 7
4.2 Đồ thị Hamilton 3 Ví dụ: Đồ thị G1có các đường đi Hamilton là: 2 4 G1 d1: 3 4 2 5 1 d2: 3 4 5 1 2 1 5 Đồ thị nửa Hamilton … 3 Đồ thị G2 có các chu trình Hamilton là: 2 4 C1: 1 2 3 4 5 6 1 G2 C2: 1 6 5 2 3 4 1 1 5 … Đồ thị Hamilton 6 26/03/2011 Lý thuyết đồ thị 8
4.2 Đồ thị Hamilton Định lý 3 (Dirak 1952) Đơn đồ thị vô hướng G với n đỉnh (n > 2), mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton. Định lý 4 Đồ thị có hướng liên thông mạnh G với n đỉnh. Nếu deg+(v) ≥ n/2, deg-(v) ≥ n/2, ∀v thì G là đồ thị Hamilton. 26/03/2011 Lý thuyết đồ thị 9
4.2 Đồ thị Hamilton Đồ thị đấu loại là đồ thị có hướng mà trong đó hai đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung. Định lý 5 i) Mọi đồ thị đấu loại là nửa Hamilton. ii) Mọi đồ thị đấu loại liên thông mạnh là Hamilton 26/03/2011 Lý thuyết đồ thị 10
4.2 Đồ thị Hamilton Định lý 6 (Ore, 1960) Cho đồ thị G có n đỉnh. Nếu deg(i)+deg(j)≥ n≥3 với i và j là hai đỉnh không kề nhau tùy ý thì G là Hamilton. 26/03/2011 Lý thuyết đồ thị 11
4.2 Đồ thị Hamilton Quy tắc để xây dựng một chu trình Hamilton (H) Quy tắc 1. Tất cả các cạnh kề với đỉnh bậc 2 phải ở trong H Quy tắc 2. Không có chu trình con (chu trình có chiều dài
4.2 Đồ thị Hamilton Ví dụ Đồ thị sau có là đồ thị Hamilton không? 1 2 3 Giả sử G có chu trình Hamilton H. Theo quy tắc 1, 4 5 6 tất cả các cạnh kề với đỉnh bậc 2 đều ở trong H: 12, 14, 7 8 9 23, 36, 47, 78, 69, 89. Ta có chu trình con là 1, 2, 3, 6, 9, 8, 7, 4, 1. Vậy G không là đồ thị Hamilton. 26/03/2011 Lý thuyết đồ thị 13

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.