tailieunhanh - Một số khái niệm cơ bản về lý thuyết đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử V là tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E) được gọi là đồ thị hữu hạn. Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u = (x,y) của E được gọi là một cạnh của đồ thị G = (V,E) | Generated by Foxit PDF Creator Foxit Software http For evaluation only. Chương 1 MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ I. MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ 1. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử V là tập hữu hạn không rỗng các phần tử nào đó. Bộ G V E được gọi là đồ thị hữu hạn. Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u x y của E được gọi là một cạnh của đồ thị G V E . Xét một cạnh u của E khi đó tồn tại hai đỉnh x y của V sao cho u x y ta nói rằng x nối với y hoặc x và y phụ thuộc u. - Nếu cạnh u x y mà x và y là hai đỉnh phân biệt thì ta nói x y là hai đỉnh kề nhau. - Nếu u x x thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên. - Nếu u x y mà x y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra y là đỉnh vào. - Khi giữa cặp đỉnh x y có nhiều hơn một cạnh thì ta nói rằng những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội. x y ----- --- x y b c Hình Thí dụ ở hình a tại đỉnh y có một khuyên b. b là cung x y có hướng. c cặp đỉnh x y tạo thành cạnh bội. Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để biểu diễn như sơ đồ mạng máy tính sơ đồ mạng lưới giao thông sơ đồ thi công một công trình. Thí dụ 1. Xét một mạng máy tính có thể biểu diễn mạng này bằng một mô hình đồ thị trong đó mỗi máy tính là một đỉnh giữa các máy được nối với nhau bằng các dây truyền chúng tương ứng là các cạnh của đồ thị. Một mô hình mạng máy tính như hình trong đó các máy tính a b c d tương ứng là các đỉnh giữa hai máy được nối trực tiếp với nhau thì tương ứng với một cặp đỉnh kề nhau. 1 Generated by Foxit PDF Creator Foxit Software http For evaluation only. b a c Hình Định nghĩa 1. Đơn đồ thị vô hướng G V E bao gồm V là các .

• Khoa học tự nhiên
• tài liệu học đại học
• bài giảng toán học
• lý thuyết đồ thị
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng
• ôn thi cao đẳng
• Đề thi thử đại học môn toán năm 2012
• đề thi toán đại học
• tài liệu luyện thi đại học
• bài tập trắc nghiệm
• cấu trúc đề thi đại học
• ngân hàng đề thi trắc nghiệm
• tài liệu ôn thi đại học
• bộ đề thi đại học
• đề thi thử đại học
• tuyển sinh đại học cao đẳng
• các đề thi đại học