Báo cáo tài liệu vi phạm
Giới thiệu
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
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
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
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Bài giảng lý thuyết đồ thị - Chương 4
Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng lý thuyết đồ thị - Chương 4
Mộng Thi (Thy)
327
9
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
ĐỒ THị EULER VÀ ĐỒ THị HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị. | Giáo án môn Lý Thuyết Đô Thị Chương 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát Đa đồ thị vô hướng hoặc có hướng thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị. 4.1 Đồ thị Euler Đỉnh nghĩa 1 Cho đồ thị G V E Đường đi đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Chu trình đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Ví dụ 1 Xét dồ thị vô hướng cho bởi hình sau Hình 4.1 Đường đi a b f a e b a d e c b là đường đi Euler Đường đi a f b c e d a e b a là đường Euler và cũng là chu trình Euler. Đường đi a b c e d a e b a f b a không phai là chu trình Euler và cũng không phải là đường Euler Ví dụ 2 Xét đồ thị có hướng cho bởi hình sau Hình 4.2 Hình 4.2 44 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị Đường v4 v3 v2 v4 v1 v5 v2 là đường đi Euler Chu trình v1 v5 v2 v4 v3 v2 v4 v1 không phải là chu trình Euler và cũng không là đường đi Euler. Chú ý Đường đi Euler và chu trình Euler cũng có thể được định nghĩa như sau Đường đi chu trình trong đồ thị G là đường đi chu trình Euler nếu nó đi qua tất cả các cạnh của đồ thị và mỗi cạnh đi qua đúng một lần. Định nghĩa 2 Đồ thị G V E được gọi là đồ thị Euler nếu như nó có chu trình Euler và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Ví dụ 3 Đồ thị cho trong ví dụ 1 là đồ thị Euler còn đồ thị cho trong ví dụ 2 là đồ thị nữa Euler. Định lý 1 định lý Euler Một đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi mỗi đỉnh của nó đều có bậc chẵn. Điều kiện cần và đủ để một đồ thị liên thông có chu trình Euler là tất cả các đỉnh của nó đều có bậc chẵn . Chứng minh Điều kiên cần Một đồ thị liên thông có chu trình Euler thì mỗi bậc của nó đều có bậc chẵn. Thật vậy giả sử chu trình Euler của đồ thị bắt đầu từ đỉnh v1 và tiếp .
TÀI LIỆU LIÊN QUAN
Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học
Bài giảng Lý thuyết đồ thị: Chương 0 - Nguyễn Trần Phi Phượng
Bài giảng Lý thuyết đồ thị: Chương 4 - ThS. Nguyễn Khắc Quốc
Bài giảng Lý thuyết đồ thị: Chương 1 - ThS. Nguyễn Khắc Quốc
Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị
Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 3: Đồ thị phẳng
Bài giảng Lý thuyết đồ thị: Chương 1 - Đại cương về đồ thị
Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Nguyễn Khắc Quốc
Bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính
Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton
Đã 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.