tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - Đại cương về đồ thị

Bài giảng Lý thuyết đồ thị: Chương 1 - Đại cương về đồ thị được biên soạn nhằm trang bị cho các ban những kiến thức về định nghĩa đồ thị; các mô hình đồ thị; một số thuật ngữ cơ bản của đồ thị; đường đi – chu trình – sự liên thông; một số đơn đồ thị đặc biệt. | Chương 1 Đại cương về đồ thị Phần . Định nghĩa đồ thị Định nghĩa đồ thị Định nghĩa. Một đơn đồ thị vô hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. VD: 5/14/2020 4:49:36 AM Lý thuyết đồ thị a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị vô hướng do có các cặp cạnh nối cùng một cặp đỉnh c. Không phải đơn đồ thị vô hướng do có cạnh nối một đỉnh với chính nó. Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là danh sách các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Chú ý: Các cạnh cùng nối giữa một cặp đỉnh được gọi là các cạnh song song. Nếu đồ thị có cạnh nối từ một đỉnh với chính nó (cạnh này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị vô hướng. 5/14/2020 4:49:36 AM Lý thuyết đồ thị Định nghĩa đồ thị (tt) VD: Chú ý: Trong một số tài liệu có thể có nhập khái niệm đa đồ thị và giả đồ thị, khi đó, chỉ có một tên gọi chung là đa đồ thị cho cả hai loại. 5/14/2020 4:49:36 AM Lý thuyết đồ thị a. Đa đồ thị vô hướng. e1 và e2 là các cạnh song song. b. Giả đồ thị vô hướng. e là khuyên e1 e2 e Định nghĩa đồ thị (tt) Định nghĩa. Một đơn đồ thị có hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. VD: 5/14/2020 4:49:36 AM Lý thuyết đồ thị Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là danh sách các cặp không có thứ tự gồm hai phần tử của V gọi là các cung. Chú ý: Các cung cùng nối giữa một cặp đỉnh được gọi là các cung song song (parallel arcs). Nếu đồ thị có cung nối từ một đỉnh với chính nó (cung này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị có hướng. 5/14/2020 4:49:36 AM Lý thuyết đồ | Chương 1 Đại cương về đồ thị Phần . Định nghĩa đồ thị Định nghĩa đồ thị Định nghĩa. Một đơn đồ thị vô hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. VD: 5/14/2020 4:53:08 AM Lý thuyết đồ thị a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị vô hướng do có các cặp cạnh nối cùng một cặp đỉnh c. Không phải đơn đồ thị vô hướng do có cạnh nối một đỉnh với chính nó. Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô hướng là một bộ G=, trong đó: V là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là danh sách các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Chú ý: Các cạnh cùng nối giữa một cặp đỉnh được gọi là các cạnh song song. Nếu đồ thị có cạnh nối từ một đỉnh với chính nó (cạnh này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị vô hướng. 5/14/2020 4:53:08 AM Lý thuyết đồ thị Định nghĩa đồ thị (tt) VD: Chú ý: Trong