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