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

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

0
132
lượt xem
62
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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    
  2. 3.4. Đồ thị phẳng  Ví dụ 2.   Ví dụ 3.    
  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ạnh­số đỉ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 ≤  3n­6  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 ≤  2n­4  Ví dụ 5: Chứng minh K3,3 không phẳng    
  4. 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.    
  5. 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?    
  6.    
  7.    
Đồng bộ tài khoản