Xem mẫu

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC ĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN VỀ TÔ MÀU ĐỒ THỊ 1 ĐỒ THỊ PHẲNG Bài toán Tìm cách làm cho các con đường đi dẫn từ 3 ngôi nhà tới 3 cái giếng sao cho không có 2 con đường nào cắt nhau? Mô hình bài toán Đỉnh: các gia đình và giếng nước Cạnh: đường đi từ nhà đến các giếng Có thể vẽ đồ thị mà không có 2 cạnh nào cắt nhau? Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị 2 ĐỒ THỊ PHẲNG Đồ thị phẳng Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở điểm không phải là điểm mút của mỗi cạnh. Hình vẽ như vậy được gọi là một biểu diễn phẳng của đồ thị. Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị 3 ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị 4 ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị 5 ... - tailieumienphi.vn
nguon tai.lieu . vn