5 trang
179 lượt xem
6 lượt tải
Giáo trình đồ thị
Giáo trình đồ thị - Khái niệm đồ thị Chúng ta đã nhìn thấy hoặc sử dụng bản đồ các tuyến đường giao thông của một thành phố, sơ đồ tổ chức một cơ quan, sơ đồ khối tính toán của một thuật toán, sơ đồ một mạng máy tính ... Đó là những ví dụ cụ thể về đồ thị. Đồ thị (graph) là một mô hình toán học được ứng dụng trong nhiều lĩnh vực khoa học, kỹ thuật và được định nghĩa như sau.
Giáo trình đồ thị - Một số tính chất về Đường đi trên đồ thị Một số tính chất về Đường đi trên đồ thị Trong phần này chúng ta xét một số tính chất của đường đi nối hai đỉnh trong một đồ thị cũng như sự tồn tại của chúng. Định lý 1.2: Giả sử đồ thị G có n đỉnh. Tồn tại đường đi từ đỉnh a đến đỉnh b trên đồ thị G khi và chỉ khi tồn tại một đường đi từ a đến b trên đồ thị này với độ dài không vượt quá n-1. Chứng minh: Giả sử có đường đi từ đỉnh a tới đỉnh b....
5 trang
160 lượt xem
7 lượt tải
Giáo trình đồ thị - Hàm Grundy trên đồ thị Hàm Grundy là một hàm toán học xây dựng trên đồ thị, do P. M. Grundy đề xuất để nghiên cứu một số tính chất lý thú của đồ thị. Trước tiên, ta ký hiệu tập các số nguyên không âm là N = {0, 1, 2, . . .}. 2.1. Hàm Grundy Định nghĩa 2.1: Giả sử G = (V, F) là một đồ thị. Hàm g : V → N được gọi là hàm Grundy của đồ thị G nếu: ∀x ∈ V : g(x) = min {N \ g(F(x))}.
5 trang
163 lượt xem
12 lượt tải
Giáo trình đồ thị - Sắc số của đồ thị Sắc số của đồ thị Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau: Hãy tô màu các đỉnh của một đồ thị đã cho, sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm: m : V → {0, 1, 2, ... , k-1} sao cho, nếu hai đỉnh x và y kề nhau thì m(x) ≠ m(y).
6 trang
164 lượt xem
6 lượt tải
Giáo trình đồ thị - Các thuật toán duyệt đồ thị Phép duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị này thành một danh sách tuyến tính. Hay nói một cách khác, phép duyệt đồ thị cho ta một cách “đi qua” tất cả các đỉnh của đồ thị để truy nhập, thêm bớt thông tin ở các đỉnh của đồ thị đó. Phép duyệt đồ thị không phụ thuộc vào hướng của các cạnh.
3 trang
161 lượt xem
14 lượt tải
Giáo trình đồ thị - Duyệt theo chiều rộng (Breadth-First Search) Nếu trong thuật toán duyệt đồ thị, cấu trúc danh sách DS được tổ chức theo kiểu hàng đợi (danh sách vào trước - ra trước – FIFO ) thì ta có phương pháp duyệt theo chiều rộng. Trong phương pháp này việc duyệt có tính chất “lan rộng”. Một đỉnh được duyệt xong ngay sau khi ta đã xét hết tất cả các đỉnh kề với nó.
3 trang
320 lượt xem
26 lượt tải
Giáo trình đồ thị - Chu trình euler và chu trình hamilton Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. 7.1. Chu trình Euler Khái niệm chu trình Euler được ra đời từ bài toán nổi tiếng sau đây.
5 trang
232 lượt xem
31 lượt tải
Giáo trình đồ thị - Chu trình Hamilton Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần. Bài toán này đã dẫn tới những khái niệm sau đây. Định nghĩa 7.5: Đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. ...
6 trang
194 lượt xem
13 lượt tải
Giáo trình đồ thị - Đồ thị phẳngTrong một thị trấn có ba biệt thự và ba nhà máy cung cấp: điện, nước và khí
đốt. Mỗi biệt thự đều muốn mắc đường cáp điện ngầm, đường ống cấp nước,
đường ống cấp khí đốt riêng từ nhà mình đến ba nhà máy mà không gặp đường ống
của các biệt thự khác. Hỏi rằng có làm được những đường đi như thế hay không?
8 trang
105 lượt xem
6 lượt tải
Chịu trách nhiệm nội dung: Nguyễn Công Hà. ©2025 Công ty TNHH Tài Liệu trực tuyến Vi Na.
Địa chỉ: 54A Nơ Trang Long, P. Bình Thạnh, TP.HCM - Điện thoại: 0283 5102 888 - Email: info@tailieu.vn
Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015