Diễn Đàn MathScope - Xem bài viết đơn

Bài này chính là chứng minh đồ thị 2 phía đầy đủ $K_{3,3}$ không phải là đồ thị phẳng.
Lời giải

Các khái niệm được sử dụng

05-06-2014, 10:29 AM	#2
Fool's theorem +Thành Viên Danh Dự+ Tham gia ngày: Oct 2012 Đến từ: T1 K46 Chuyên ĐHSP Hà Nội Bài gởi: 187 Thanks: 42 Thanked 192 Times in 101 Posts	Bài này chính là chứng minh đồ thị 2 phía đầy đủ $K_{3,3}$ không phải là đồ thị phẳng. Lời giải Ta sẽ chứng minh bằng phản chứng. Giả sử đồ thị $K_{3,3}$ là đồ thị phẳng. Áp dụng công thức Euler cho đồ thị phẳng ta có $f=e-v+2=9-6+2=5$ với $f$ là số mặt của đồ thị, $e$ là số cạnh và $v$ là số đỉnh. Tiếp theo ta sẽ chứng minh mỗi mặt của một đồ thị 2 phía phẳng cần sử dụng ít nhất 4 cạnh. Thật vậy, gọi 2 tập đỉnh của $K_{3,3}$ là $A$ và $B$. Một mặt cần sử dụng ít nhất 3 cạnh, tuy nhiên 3 cạnh không cắt nhau (do đang giả sử là đồ thị phẳng) và đều là 3 cạnh nối 1 đỉnh tập $A$ đến 1 đỉnh tập $B$ thì không thể tạo thành tam giác được (đoạn này vẽ hình ra sẽ dễ hiểu hơn ), vậy nên một mặt cần sử dụng ít nhất 4 cạnh. Mà một cạnh thì là chung của 2 mặt vậy nên ta có bất đẳng thức là $4f \leq 2e$ hay $5=f \leq \frac{9}{2}$ (mâu thuẫn) Ta có đpcm. Các khái niệm được sử dụng Đồ thị 2 phía : Đồ thị có 2 tập đỉnh $A$ và $B$, tất cả các cạnh đều là nối 2 đỉnh thuộc 2 tập khác nhau Đồ thị 2 phía đầy đủ : Đồ thị 2 phía mà giữa 2 đỉnh bất kì thuộc 2 tập khác nhau thì đều có cạnh nối Đồ thị phẳng : đồ thị không có 2 cạnh nào cắt nhau __________________ Hope against hope. thay đổi nội dung bởi: Fool's theorem, 05-06-2014 lúc 10:50 AM