zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Lý thuyết đồ thị - Phần 4

Chia sẻ: Hoàng Danh Long | Ngày: | Loại File: PPT | Số trang:7

Báo xấu

186
lượt xem 64
download

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

Tham khảo tài liệu 'lý thuyết đồ thị - phần 4', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết đồ thị - Phần 4

3.4. Đồ thị phẳng 3.4.1. Định nghiã và ví dụ  Biểu diễn phẳng  Đồ thị phẳng  Ví dụ 1. biểu diễn phẳng biểu diễn không phẳng đồ thị phẳng đồ thị phẳng
3.4. Đồ thị phẳng  Ví dụ 2.  Ví dụ 3.
3.4. Đồ thị phẳng 3.4.2. Định lý Euler và các hệ quả  Định lý Euler: Số miền phẳng=số cạnhsố đỉnh+2  Hệ quả 1: Nếu G=(V,E) là đơn đồ thị phẳng, liên thông có m đỉnh (m≥ 3) và n cạnh. Khi đó m ≤ 3n6 Ví dụ 4: Chứng minh K5 không phẳng  Hệ quả 2: Nếu G=(V,E) là đơn đồ thị phẳng, liên thông có m đỉnh (m≥ 3) và n cạnh, không có chu trình độ dài 3. Khi đó m ≤ 2n4 Ví dụ 5: Chứng minh K3,3 không phẳng
3.4. Đồ thị phẳng 3.4.2. Đồ thị đồng phôi và định lý Kuratovski  Phép phân chia sơ cấp  Từ một đồ thị phẳng G=(V,E), nếu bỏ đi một cạnh và thêm vào một đỉnh cùng với hai cạnh nối đỉnh vừa thêm với các đỉnh kề của cạnh vừa bỏ đi thi ta nói đã thực hiện một phép phân chia sơ cấp đồ thị G.  Đồ thị đồng phôi  Hai đồ thị G1 và G2 được gọi là đồng phôi nếu chúng cùng thu được từ một đồ thị bằng một số hữu hạn các phép phân chia sơ cấp.
3.4. Đồ thị phẳng  Định lý Kuratovski Một đồ thị không phẳng khi và chỉ khi nó chứa một đồ thị con đồng phôi với K3,3 hoặc K5.  Ví dụ:  Đồ thị Petersen  Đồ thị Kn phẳng khi nào?  Đồ thị Qn phẳng khi nào?

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.