TAILIEUCHUNG - Tài liệu: Lý thuyết đồ thị (phần 4)

Trong các sách, tùy theo ý của tác giả hoặc theo yêu cầu của chủ đề cụ thể mà từ "đồ thị" có thể hàm ý cho phép hoặc không cho phép khuyên hay đa cạnh. Nếu đồ thị không cho phép đa cạnh (và không cho phép khuyên nếu là đồ thị có hướng), đồ thị được gọi là đồ thị đơn. Mặt khác, nếu cho phép đa cạnh (và đôi khi cả khuyên), đồ thị được gọi là đa đồ thị. Đôi khi, từ giả đồ thị (pseudograph) còn được dùng để hàm ý cả đa cạnh và. | ĐÍNHLỶ Cho G là một đơn đồ thị liỀn thông có V đinh E cạnh Vriị E è 3. Nếu G phảng thì ta có bất đổng thức Eí3 V-2 4 CHỬNG MiNHt Hiển nhiên. ĐỊNH LÝ KURA TOWSKI I Một cách tổng quát việc khảo sát tinh chất phảng của một đi thị là một bài toán khỗng dễ. Định lỷ Kuratoivskì đưa ra một điều kiện dt cỏ và đủ để một đổ thị là phdng. I ĐINH NGHĨA I Nhác lại rằng đơn đồ thị đẩy đủ có n đỉnh được ký hiệu là V .X n n - 1 1 Kn và có cạnh. Dễ thấy K1 Ka K b Kf đểu phồng. Hơn nữa .thí dụ 4 đ trên chứng tỏ rằng Kn n è 5 khổng phảng. I Đồ thị lưỡng phân đầy đủ complete bipartite graph KflJ là 1 đơn đồ thị có m n đỉnh gồm m đỉnh bên trái vồ n đinh bên phải sao cho mỗi đỉnh bên trái đếu có cạnh nối đến mọi đỉnh bên phải. I Dễ thấy rằng Km n có mn cạnh. I K Do thí dụ 3 Kn . m n 3 không phẳng. Kết quả tổ 66 quát về tính chất phắng cùa đồ thị lường phân đầy H được nêu ở phần bài tập. Từ đồ thị Go cho trước ta xây dựng 1 đổ thi G theo cách sau Thêm vào Go cổc đỉnh mới và các cạnh mới đỉnh mới có thể nối với 1 đinh khác bằng 1 cạnh mái đỉnh mđi cũng có thể được đạt nằm trên 1 cạnh cũ và chia cạnh cù này thành 2 cạnh mới Ta nói rằng đồ thị G nhận được là có chứa cấu hình configuration Go. Ta đã biết rằng và Kfi không phẳng do đó hiển nhiên nếu một đồ thị có chứa cấu hình hoặc Kr thì nó không phảng. Điều dào lại cũng đúng và là khảng định của định lý Kuratowski ĐINH LÝ Kuratowakl phdn. nếu và chi nếu G khôns chứa cấu hình cũng như Kị. Phần chứng minh của định lý này khá phức tạp và sè Không trình bày ở đây. Độc giả cỏ thể tham khảo trong 1 Ta cổ thể dùng định lý Kuratowski để chứng minh 1 đồ thị là không phẳng. D Ta vè lại chúng như sau 67 1 nếu eị là cạnh biên của mặt fj m J 0 nếu 6ị không là cạnh biên của mặt fj Xét hàng thứ i. Vì cạnh e là cạnh biên củ nhiều nhất là 2 mặt nên tổng các phẩn t trên hàng này 2 1 F J Xmij s 2 j i 11 E F Ị Suy ra Xm j XSmy-2E 1 KisE Ỉ 1 j l lắjsF Lại xét cột thứ j. Vì mặt fj có ít nhất g cạạ biên nên tổng các phần .

• Toán học
• lý thuyết đồ thị
• toán đồ thị
• toán tin học
• tài liệu đồ thị
• hướng dẫn toán đồ thị
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị