Luận văn thạc sĩ: Xây dựng hệ thống khuyến nghị dựa trên Graph Neural Network

Luận văn thạc sĩ nghiên cứu hệ thống khuyến nghị sử dụng graph neural network, ứng dụng trong khoa học máy tính và phân tích dữ liệu.

• Tác giả: Bùi Bá Anh
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Xây Dựng Hệ Thống Khuyến Nghị Dựa Trên Graph Neural Network
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT OF DISSERTATION
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu chung
• 1.2. Mô tả Bài toán khuyến nghị theo phiên
• 1.3. Mục tiêu và nhiệm vụ của luận văn
• 1.4. Giới hạn đề tài
• 1.5. Đóng góp của luận văn
• 1.6. Tóm tắt nội dung
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 3. CHƯƠNG 3: CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 4. CHƯƠNG 4: MÔ HÌNH ĐỀ XUẤT
• 5. CHƯƠNG 5: KẾT QUẢ THỰC NGHIỆM VÀ THẢO LUẬN
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• Tài liệu tham khảo

Tóm tắt

I. Giới thiệu chung

Trong bối cảnh công nghệ thông tin phát triển nhanh chóng, hệ thống khuyến nghị đã trở thành một công cụ quan trọng giúp các nhà cung cấp dịch vụ hiểu rõ hơn về nhu cầu và sở thích của người dùng. Hệ thống khuyến nghị không chỉ giúp tối ưu hóa doanh thu mà còn nâng cao trải nghiệm người dùng. Đặc biệt, bài toán khuyến nghị theo phiên (Session-based Recommendation) đã thu hút sự chú ý lớn nhờ vào khả năng xử lý dữ liệu tuần tự của các mô hình học sâu như Graph Neural Network (GNN). Luận văn này nghiên cứu việc ứng dụng GNN trong việc xây dựng hệ thống khuyến nghị, nhằm cải thiện độ chính xác và hiệu quả của các gợi ý sản phẩm trong các phiên hoạt động của người dùng.

1.1. Mô tả Bài toán khuyến nghị theo phiên

Bài toán khuyến nghị theo phiên tập trung vào việc dự đoán sản phẩm tiếp theo mà người dùng có khả năng quan tâm dựa trên các hành vi tương tác trước đó. Hệ thống khuyến nghị sẽ phân tích hành vi của người dùng trong một khoảng thời gian ngắn để đưa ra gợi ý chính xác hơn. Đặc điểm quan trọng nhất của bài toán này là tính ngắn hạn và tính tuần tự của các hành vi tương tác. Việc khai thác thông tin từ các phiên hoạt động giúp hệ thống khuyến nghị có thể đưa ra các gợi ý phù hợp hơn với nhu cầu thực tế của người dùng tại thời điểm đó.

II. Cơ sở lý thuyết

Chương này sẽ tổng hợp các lý thuyết và mô hình liên quan đến hệ thống khuyến nghị, đặc biệt là các phương pháp sử dụng Graph Neural Network. Mô hình GNN cho phép biểu diễn các phiên hoạt động dưới dạng đồ thị, từ đó khai thác mối quan hệ giữa các sản phẩm một cách hiệu quả. Cơ chế học sâu và các mô hình như Mạng nơ ron nhân tạo (ANN) và Mạng nơ ron hồi tiếp (RNN) cũng sẽ được phân tích để hiểu rõ hơn về cách thức hoạt động của hệ thống khuyến nghị. Việc áp dụng GNN trong hệ thống khuyến nghị không chỉ giúp cải thiện độ chính xác mà còn tối ưu hóa quá trình học tập của mô hình.

2.1. Mô hình Graph Neural Network

Mô hình Graph Neural Network (GNN) cho phép xử lý dữ liệu dưới dạng đồ thị, giúp khai thác các mối quan hệ phức tạp giữa các sản phẩm trong một phiên hoạt động. GNN có khả năng học hỏi từ cấu trúc đồ thị, từ đó tạo ra các đại diện cho sản phẩm dựa trên các kết nối của chúng. Điều này cực kỳ quan trọng trong bài toán khuyến nghị theo phiên, nơi mà mối quan hệ giữa các sản phẩm có thể ảnh hưởng lớn đến quyết định của người dùng. GNN không chỉ nâng cao khả năng dự đoán mà còn hỗ trợ việc tối ưu hóa quá trình tìm kiếm và đề xuất sản phẩm.

III. Mô hình đề xuất

Luận văn đề xuất hai mô hình cải tiến cho hệ thống khuyến nghị dựa trên GNN. Mô hình đầu tiên tập trung vào việc bổ sung thông tin về mức độ yêu thích của người dùng dựa trên thời gian tương tác với sản phẩm. Mô hình thứ hai sử dụng cơ chế Self-Attention để cải thiện khả năng học của mô hình. Cả hai mô hình này đều được kiểm nghiệm trên các tập dữ liệu thực tế, cho thấy sự cải thiện đáng kể về độ chính xác của các gợi ý sản phẩm. Điều này chứng tỏ rằng việc tích hợp thời gian và mối quan hệ giữa các sản phẩm có thể giúp hệ thống khuyến nghị hoạt động hiệu quả hơn.

3.1. Đề xuất 1 Đánh giá lại mức độ quan tâm

Đề xuất đầu tiên là cải thiện độ chính xác của hệ thống khuyến nghị bằng cách đánh giá lại mức độ quan tâm của người dùng dựa trên thời gian mà họ dành cho từng sản phẩm. Việc này giúp mô hình hiểu rõ hơn về sở thích thực sự của người dùng trong một phiên hoạt động, từ đó đưa ra các gợi ý phù hợp hơn. Kết quả thực nghiệm cho thấy rằng việc bổ sung yếu tố thời gian đã giúp cải thiện đáng kể độ chính xác của mô hình.

IV. Kết quả thực nghiệm và thảo luận

Kết quả thực nghiệm từ các mô hình đề xuất cho thấy rằng việc sử dụng Graph Neural Network trong hệ thống khuyến nghị đã mang lại những kết quả ấn tượng. Các mô hình đã được kiểm tra trên ba tập dữ liệu khác nhau và đều cho thấy sự cải thiện về độ chính xác so với các mô hình truyền thống. Điều này chứng tỏ rằng GNN có thể khai thác tốt hơn các mối quan hệ phức tạp giữa các sản phẩm, từ đó cải thiện chất lượng gợi ý cho người dùng. Hơn nữa, việc áp dụng cơ chế Self-Attention cũng giúp mô hình tăng cường khả năng học hỏi từ dữ liệu, tạo ra các gợi ý chính xác hơn.

4.1. Hạn chế và vấn đề tồn đọng

Dù đạt được nhiều kết quả khả quan, luận văn cũng chỉ ra một số hạn chế trong nghiên cứu. Một trong những vấn đề tồn đọng là việc khai thác thông tin từ các phiên hoạt động có thể gặp khó khăn khi dữ liệu không đầy đủ hoặc không chính xác. Hơn nữa, việc mở rộng mô hình để áp dụng cho các lĩnh vực khác cũng cần được xem xét. Nghiên cứu trong tương lai có thể tìm kiếm giải pháp cho những vấn đề này nhằm nâng cao hiệu quả của hệ thống khuyến nghị.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của thương mại điện tử và các nền tảng trực tuyến, việc cá nhân hóa trải nghiệm người dùng thông qua hệ thống khuyến nghị trở nên thiết yếu. Theo báo cáo của ngành, hơn 70% doanh thu của các trang thương mại điện tử đến từ các đề xuất sản phẩm phù hợp với sở thích người dùng. Bài toán khuyến nghị theo phiên (Session-based Recommendation System - SBRS) tập trung vào việc dự đoán sản phẩm tiếp theo người dùng có thể quan tâm trong một phiên hoạt động ngắn hạn, dựa trên các tương tác tuần tự của họ. Mục tiêu chính của luận văn là xây dựng hệ thống khuyến nghị dựa trên mô hình Graph Neural Network (GNN), khai thác đặc tính tuần tự và mối quan hệ phức tạp giữa các sản phẩm trong phiên hoạt động.

Phạm vi nghiên cứu tập trung trên ba tập dữ liệu thực tế phổ biến là Yoochoose, Diginetica và Otto, với thời gian thu thập dữ liệu trong khoảng vài năm gần đây. Luận văn đề xuất hai cải tiến chính: bổ sung thông tin về thời gian theo dõi sản phẩm như một dạng phản hồi gián tiếp để đánh giá mức độ yêu thích, và áp dụng cơ chế self-attention nhằm nâng cao khả năng học mối quan hệ giữa các sản phẩm trong phiên. Việc cải thiện độ chính xác của hệ thống khuyến nghị không chỉ giúp tăng trải nghiệm người dùng mà còn góp phần tối ưu hóa doanh thu và giữ chân khách hàng cho các nền tảng thương mại điện tử.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên ba nền tảng lý thuyết chính:

1. Lý thuyết đồ thị (Graph Theory): Đồ thị được biểu diễn dưới dạng G = (V, E), trong đó V là tập đỉnh (sản phẩm), E là tập cạnh (mối quan hệ giữa sản phẩm). Đồ thị có hướng được sử dụng để mô hình hóa các phiên hoạt động, thể hiện thứ tự tương tác giữa các sản phẩm.

2. Mạng nơ-ron nhân tạo (Artificial Neural Network - ANN): Mạng ANN gồm các perceptron kết nối, với các tầng đầu vào, ẩn và đầu ra. Mạng học sâu (Deep Learning) được sử dụng để trích xuất đặc trưng phức tạp từ dữ liệu tuần tự.

3. Graph Neural Network (GNN): GNN sử dụng cơ chế truyền thông điệp (Message Passing) để tổng hợp đặc trưng của các đỉnh dựa trên đặc trưng của các đỉnh lân cận. Cách tiếp cận này cho phép mô hình hóa mối quan hệ không gian và thời gian trong dữ liệu đồ thị.

4. Cơ chế Self-Attention: Được phát triển từ mô hình Transformer, self-attention tính trọng số tương quan giữa các phần tử trong chuỗi, giúp mô hình tập trung vào các mối quan hệ quan trọng trong phiên hoạt động. Multi-Head Self-Attention mở rộng khả năng này bằng cách sử dụng nhiều khối attention song song.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Ba tập dữ liệu thực tế Yoochoose, Diginetica và Otto được sử dụng, với tổng số phiên hoạt động lên đến hàng trăm nghìn, bao gồm các tương tác bấm chọn (click) của người dùng.

• Phương pháp phân tích: Mô hình cơ sở SRGNN được lựa chọn để phát triển. Hai đề xuất cải tiến được thực nghiệm: (1) tích hợp trọng số dựa trên thời gian theo dõi sản phẩm và thời điểm tương tác để đánh giá mức độ yêu thích; (2) thay thế cơ chế attention trong SRGNN bằng Multi-Head Self-Attention để nâng cao khả năng học mối quan hệ phức tạp.

• Cỡ mẫu và chọn mẫu: Dữ liệu được xử lý để giữ lại các phiên hoạt động có độ dài phù hợp, tập trung vào hành vi bấm chọn duy nhất trong phiên nhằm đơn giản hóa mô hình và phù hợp với thực tế ứng dụng.

• Timeline nghiên cứu: Nghiên cứu bắt đầu từ tháng 2/2023, hoàn thành vào tháng 6/2023, bao gồm các giai đoạn thu thập và xử lý dữ liệu, xây dựng mô hình, thực nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Cải thiện độ chính xác nhờ thời gian theo dõi: Việc bổ sung thông tin thời gian người dùng xem sản phẩm giúp mô hình tăng Precision trung bình khoảng 3-5% so với mô hình SRGNN gốc trên cả ba tập dữ liệu. Ví dụ, trên tập Yoochoose, Precision tăng từ 0.68 lên 0.71.

2. Hiệu quả của cơ chế Multi-Head Self-Attention: Thay thế cơ chế attention truyền thống bằng Multi-Head Self-Attention giúp mô hình khai thác tốt hơn mối quan hệ giữa các sản phẩm trong phiên, tăng Mean Reciprocal Rank (MRR) lên khoảng 4% so với mô hình cơ sở.

3. Tương tác giữa hai đề xuất: Kết hợp cả hai đề xuất không chỉ cải thiện từng chỉ số riêng lẻ mà còn nâng cao tổng thể hiệu suất mô hình, thể hiện qua việc tăng đồng thời Precision và MRR trên tất cả các tập dữ liệu.

4. Khả năng tổng quát hóa: Mô hình đề xuất duy trì hiệu quả trên các tập dữ liệu có đặc điểm khác nhau về mật độ tương tác, chứng tỏ tính linh hoạt và khả năng áp dụng rộng rãi.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do việc khai thác thêm yếu tố thời gian theo dõi cung cấp thông tin phản hồi gián tiếp về mức độ quan tâm của người dùng, điều mà các mô hình trước đây thường bỏ qua. Cơ chế self-attention giúp mô hình nhận diện và tập trung vào các sản phẩm có ảnh hưởng lớn trong phiên, thay vì chỉ dựa vào các mối quan hệ cục bộ.

So với các nghiên cứu trước đây, kết quả này phù hợp với xu hướng ứng dụng GNN và attention trong khuyến nghị, đồng thời bổ sung thêm yếu tố thời gian như một tín hiệu quan trọng. Dữ liệu có thể được trình bày qua biểu đồ so sánh Precision và MRR giữa các mô hình, cũng như bảng tham số cấu hình và kết quả thực nghiệm chi tiết.

Đề xuất và khuyến nghị

1. Tích hợp thời gian theo dõi trong hệ thống khuyến nghị: Các nhà phát triển nên bổ sung thông tin thời gian người dùng tương tác với sản phẩm để cải thiện độ chính xác dự đoán, ưu tiên triển khai trong vòng 6 tháng tới.

2. Áp dụng cơ chế Multi-Head Self-Attention: Nâng cấp mô hình khuyến nghị hiện tại bằng cách thay thế cơ chế attention truyền thống, giúp tăng khả năng học mối quan hệ phức tạp, nên được thực hiện bởi đội ngũ phát triển AI trong 3-4 tháng.

3. Đào tạo và cập nhật mô hình định kỳ: Thực hiện huấn luyện lại mô hình với dữ liệu mới để duy trì hiệu suất, khuyến nghị mỗi quý một lần, do bộ phận dữ liệu và AI chịu trách nhiệm.

4. Mở rộng nghiên cứu sang các hành vi tương tác khác: Nghiên cứu thêm các loại hành vi như mua hàng, chia sẻ để đa dạng hóa dữ liệu đầu vào, dự kiến triển khai trong kế hoạch phát triển dài hạn.

Đối tượng nên tham khảo luận văn

1. Nhà phát triển hệ thống khuyến nghị: Có thể áp dụng các phương pháp và mô hình đề xuất để nâng cao hiệu quả đề xuất sản phẩm, giảm tỷ lệ bỏ giỏ hàng.

2. Nhà nghiên cứu khoa học máy tính: Tìm hiểu sâu về ứng dụng GNN và self-attention trong bài toán khuyến nghị, làm cơ sở cho các nghiên cứu tiếp theo.

3. Chuyên gia phân tích dữ liệu thương mại điện tử: Sử dụng các kết quả để hiểu rõ hơn về hành vi người dùng và tối ưu hóa chiến lược cá nhân hóa.

4. Quản lý sản phẩm và marketing: Áp dụng kiến thức để thiết kế các chiến dịch quảng cáo và khuyến mãi dựa trên dự đoán hành vi người dùng chính xác hơn.

Câu hỏi thường gặp

1. Graph Neural Network là gì và tại sao lại phù hợp cho bài toán khuyến nghị theo phiên?
   GNN là mô hình học sâu xử lý dữ liệu dạng đồ thị, giúp tổng hợp thông tin từ các đỉnh lân cận. Trong khuyến nghị theo phiên, sản phẩm và mối quan hệ tuần tự được biểu diễn dưới dạng đồ thị có hướng, nên GNN giúp khai thác hiệu quả các mối liên hệ phức tạp giữa sản phẩm.

2. Tại sao yếu tố thời gian theo dõi sản phẩm lại quan trọng?
   Thời gian theo dõi phản ánh mức độ quan tâm của người dùng đến sản phẩm, là dạng phản hồi gián tiếp giúp mô hình đánh giá chính xác hơn sở thích thực sự, từ đó cải thiện độ chính xác đề xuất.

3. Self-Attention khác gì so với attention truyền thống?
   Self-Attention tính trọng số tương quan giữa tất cả các phần tử trong chuỗi, cho phép mô hình tập trung vào các mối quan hệ toàn cục, trong khi attention truyền thống thường chỉ tập trung vào các phần tử cục bộ hoặc theo thứ tự.

4. Các tập dữ liệu Yoochoose, Diginetica và Otto có đặc điểm gì?
   Đây là các tập dữ liệu thực tế phổ biến trong nghiên cứu khuyến nghị, chứa hàng trăm nghìn phiên hoạt động với các tương tác bấm chọn sản phẩm, có mật độ và đặc điểm khác nhau, giúp đánh giá tính tổng quát của mô hình.

5. Mô hình đề xuất có thể áp dụng trong thực tế như thế nào?
   Mô hình có thể được tích hợp vào các nền tảng thương mại điện tử để đề xuất sản phẩm theo phiên, giúp tăng tỷ lệ chuyển đổi và nâng cao trải nghiệm người dùng thông qua các đề xuất chính xác và kịp thời.

Kết luận

• Luận văn đã xây dựng thành công hệ thống khuyến nghị theo phiên dựa trên Graph Neural Network, khai thác hiệu quả đặc tính tuần tự và mối quan hệ giữa sản phẩm.
• Hai đề xuất chính là bổ sung thông tin thời gian theo dõi và áp dụng cơ chế Multi-Head Self-Attention đã cải thiện đáng kể độ chính xác và khả năng học của mô hình.
• Kết quả thực nghiệm trên ba tập dữ liệu thực tế cho thấy tính tổng quát và hiệu quả của mô hình đề xuất.
• Hạn chế hiện tại là chưa khai thác đa dạng các loại hành vi tương tác và chưa áp dụng trên quy mô dữ liệu lớn hơn.
• Đề xuất các bước tiếp theo bao gồm mở rộng mô hình với các hành vi khác, tối ưu hóa hiệu suất tính toán và triển khai thử nghiệm thực tế trên nền tảng thương mại điện tử.

Quý độc giả và các nhà nghiên cứu được khuyến khích áp dụng và phát triển thêm các giải pháp dựa trên nền tảng này để nâng cao hiệu quả hệ thống khuyến nghị trong tương lai.

Trích đoạn nội dung tài liệu

Chương 1, GIỚI THIỆU ĐỀ TÀI: trình bày tổng quan về đề tài, lý do thực hiện đề tài và ý nghĩa thực tiễn của bài toán, cũng như giới hạn và phạm vi của đề tài. Cuối cùng là nhiệm vụ và cấu trúc của luận văn. – Chương 2, CƠ SỞ LÝ THUYẾT: tổng hợp những vấn đề học thuật liên quan nhất sẽ áp dụng để giải quyết bài toán, tập trung chủ yếu vào nội dung của học sâu, từ Mạng nơ ron nhân tạo (Artificial Neural Network) tới Recurrent Neural Network, cơ chế attention và đặc biệt là lý thuyết về Graph Neural Network. – Chương 3, CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN: trình bày một cách tổng quát về những nghiên cứu liên quan đã và đang được thực hiện, cũng như xu hướng chung hiện nay trong việc 8 giải quyết bài toán.

Phần này cũng đưa ra những bàn luận và đánh giá cho các phương pháp kể trên vì đó là cơ sở quan trọng cho những nghiên cứu của học viên trong quá trình thực hiện luận văn. – Chương 4, MÔ HÌNH ĐỀ XUẤT: giới thiệu mô hình cơ sở cho Bài toán khuyến nghị theo phiên. Đồng thời đưa ra các cải tiến và động lực cho các đề xuất đó. Cuối cùng, học viên trình bày các bước tiến hành thí nghiệm trên những tập dữ liệu khác nhau và đánh giá kết quả của những cải tiến so với mô hình cơ sở.

– Chương 5, KẾT LUẬN: tổng hợp các kết quả đạt được trong quá trình thực hiện luận văn từ bước nghiên cứu và xây dựng giả thuyết đến triển khai thực nghiệm. Phần này cũng trình bày những hạn chế và vấn đề tồn đọng, cuối cùng đề xuất các giải pháp cải tiến trong tương lai. Mục lục, Danh sách hình vẽ, Danh sách bảng được cung cấp ở đầu luận văn. Tài liệu tham khảo sẽ được trình bày ở cuối luận văn.

9 Chương 2 CƠ SỞ LÝ THUYẾT 2. Tổng quan về Lý thuyết đồ thị 2. Định nghĩa và ví dụ về đồ thị Lý thuyết đồ thị được xem như một lĩnh vực của toán học rời rạc, được phát triển từ rất lâu và có nhiều ứng dụng trong khoa học cũng như thực tiễn, đặc biệt là đối với các ngành toán học và khoa học máy tính.1 minh họa Bài toán 7 cây cầu 1 dưới dạng đồ thị.1: Bài toán 7 cây cầu Königsberg biểu diễn dưới dạng đồ thị Định nghĩa: Một đồ thị được biểu diễn dưới dạng G = (V, E), trong đó V, E là hai tập hợp hữu hạn, với V là tập hợp các đỉnh (vertex) của đồ thị, E là tập hợp các cạnh (edge). Một cạnh e của đồ thị được hình thành từ sự liên kết hai đỉnh u, v thuộc đồ thị, thường được viết e = (u, v).

Khi này ta nói, u, v là hai mút của cạnh e và e là cạnh nối u với v. Như vậy, nếu coi mỗi đỉnh của đồ thị biểu diễn một đối tượng, thì một cạnh 10 trong đồ thị biểu diễn một quan hệ hai ngôi giữa các đối tượng này. Nếu vai trò của hai đầu mút u, v đối với cạnh e là như nhau, tức là không kể đến thứ tự của chúng trong việc biểu diễn cạnh, ta gọi đó là cạnh vô hướng. Ngược lại, việc biểu diễn e cần kể đến thứ tự trước sau của u, v, khi này e là cạnh có hướng, trong đó u (giả sử) là đỉnh đầu, v là đỉnh cuối của cạnh e.

Trong biểu diễn e = (u, v) đối với cạnh có hướng, ta nói e là cạnh nối từ u đến v. Ngoài ra, trong định nghĩa cạnh, nếu một cạnh được nối bởi một đỉnh đến chính nó, hay e = (u, u), e được gọi là khuyên. Dưới đây là phân loại một số dạng đồ thị: − Đồ thị vô hướng và đồ thị có hướng: Một đồ thị mà tất cả các cạnh của nó là vô hướng được gọi là đồ thị vô hướng (Hình 2.2a), ngược là là đồ thị có hướng (Hình 2. Nếu bỏ đi hướng trên tất cả các cạnh có hướng, một đồ thị có hướng sẽ trở thành đồ thị vô hướng.2: Đồ thị vô hướng và đồ thị có hướng − Đơn đồ thị và đa đồ thị: Một đồ thị không có khuyên và giữa hai đỉnh chỉ có nhiều nhất là một cạnh nối được gọi là một đơn đồ thị (Hình 2.

Các đồ thị có khuyên hay có nhiều hơn một cạnh nối giữa hai đỉnh được gọi là các đa đồ thị (Hình 2. − Đồ thị có trọng số: Trong một đồ thị, nếu trên mỗi cạnh được gán 11 Hình 2.3: Đơn đồ thị và đa đồ thị cho một số thực nào đó, ta gọi đó là đồ thị có trọng số. Nếu không nói gì thêm, ta xem như đồ thị không có trọng số (trọng số trên tất cả các cạnh là bằng nhau). Một số khái niệm khác trong đồ thị: − Kề: Đỉnh v được gọi là kề với u nếu có cạnh nối từ u đến v trên một cạnh có hướng.

Nếu đó là cạnh vô hướng, ta nói u, v kề nhau. − Liên thuộc: Nếu đỉnh u là một trong hai mút của cạnh e, khi này ta nói đỉnh u liên thuộc cạnh e. − Bậc của đỉnh: Trong đồ thị vô hướng, bậc của đỉnh u là tổng số cạnh liên thuộc với nó, kí hiệu là deg(u). Trong đồ thị có hướng, người ta quan tâm đến cả cạnh ra, vào tại một đỉnh, vì vậy khái niệm bậc được thay thế bằng nửa bậc, bao gồm nửa bậc vào, kí hiệu deg− (u), là số cạnh đi vào u, và nửa bậc ra, kí hiệu deg+ (u), là số cạnh đi ra từ u.

Nếu một đỉnh có bậc (hoặc nửa bậc vào, ra) bằng 0, ta gọi đó là đỉnh treo. Từ những khái niệm về bậc nói trên, ta có Định lý bắt tay. Định lý bắt tay: Trong đơn đồ thị vô hướng G = (V, E), tổng bậc của 12 tất cả các đỉnh trong đồ thị bằng 2 lần số cạnh: ∑ deg(u) = 2|E| (2.1) u∈V Nếu đồ thị được cho là có hướng, tổng của nửa bậc vào và tổng của nửa bậc ra bằng nhau và cùng bằng số cạnh trong đồ thị: ∑ deg+ (u) = ∑ deg− (u) = |E| (2.2) u∈V u∈V − Đường đi: là một dãy các cạnh kề nhau (cạnh sau kề cạnh trước), xuất phát từ đỉnh s và kết thúc tại đỉnh t. Đường đi có thể là vô hướng hoặc có hướng.

Số cạnh trên đường đi được gọi là độ dài của đường đi. − Chu trình: là một đường đi không có cạnh lặp lại và đỉnh đầu trùng với đỉnh cuối. Tương tự như đường đi, chu trình có thể có hướng hoặc vô hướng. Một chu trình không có đỉnh lặp (trừ đỉnh đầu, đỉnh cuối trùng nhau) được gọi là một chu trình đơn.

− Đồ thị con: Đồ thị con của một đồ thị G là một đồ thị nhận được từ G bằng cách bỏ đi một số cạnh và một số đỉnh (cùng với các cạnh liên quan đến những đỉnh này). Khi đó, đồ thị con G′ = (V ′ , E ′ ), trong đó V ′ ⊆ V và E ′ ⊆ E. − Liên thông: Một đồ thị vô hướng được gọi là liên thông nếu giữa hai đỉnh bất kỳ đều tồn tại một đường đi nào đó giữa hai đỉnh này là điểm bắt đầu và kết thúc. Trong đồ thị có hướng, nếu ta không quan tâm đến hướng của cạnh, và đồ thị vô hướng thu được là liên thông, ta nói đồ thị có hướng đó liên thông yếu.

Nếu điều kiện có hướng cũng được thỏa mãn, đồ thị đó được gọi là liên thông mạnh. 13 Trong đời sống, chúng ta bắt gặp nhiều hình ảnh có thể mô tả được dưới dạng đồ thị. Ví dụ như một mạng máy tính gồm nhiều trung tâm máy được kết nối với nhau để chia sẻ thông tin, lúc này mỗi trung tâm được xem như một đỉnh trong đồ thị, giữa hai trung tâm có hình thành kênh thoại sẽ tạo thành một cạnh. Vì kênh thoại như là một cách trao đổi thông tin nên sẽ có hai chiều, dẫn đến đồ thị được xây dựng từ cách biểu diễn trên là một đa đồ thị có hướng (vì tồn tại khuyên, một trung tâm có thể có kênh trao đổi trong chính nó).

Một ví dụ khác là hệ thống mạng giao thông khi mà mỗi nút giao thông được xem như một đỉnh, và đoạn đường nối hai nút giao thông có thể xem như một cạnh. Các loại đồ thị đặc biệt Một số đồ thị đặc biệt thường gặp: − Đồ thị đầy đủ: là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối. Như vậy số cạnh của đồ thị đầy đủ gồm n đỉnh là n(n − 1) và được kí hiệu là Kn 2 − Đồ thị vòng: là đơn đồ thị vô hướng và tồn tại một chu trình đơn đi qua tất cả các đỉnh và các cạnh của nó. Số cạnh trong một đồ thị vòng n đỉnh cũng bằng n và được kí hiệu là Cn.

Ngoài ra có thể thấy, bậc của mỗi đinh trong đồ thị vòng đều bằng 2. − Đồ thị bánh xe: được định nghĩa là khi ta thêm một đỉnh và n cạnh từ đỉnh đó đến tất cả các đỉnh khác trong đồ thị vòng Cn , ta thu được đồ thị bánh xe Wn. Số cạnh trong đồ thị bánh xe Wn là 2n. − Đồ thị lập phương: là đơn đồ thị vô hướng gồm 2n đỉnh, mỗi đỉnh được đặt tên bằng một chuỗi n bit.

Hai đỉnh được nối với nhau nếu và 14 chỉ nếu tên của chúng chỉ khác nhau đúng một bit. Đồ thị lập phương như vậy được kí hiệu là Qn , bao gồm n × 2n−1 đỉnh. − Đồ thị phẳng: Một đồ thị được gọi là phẳng nếu có thể vẽ nó trên mặt phẳng sao cho không có cạnh nào cắt nhau trừ tại đỉnh. − Đồ thị hai phía: là một đơn đồ thị vô hướng có thể phân hoạch tập đỉnh thành hai lớp sao cho chỉ có các cạnh nối đỉnh của lớp này với đỉnh của lớp kia (nghĩa là không có cạnh nối hai đỉnh của cùng một lớp).

Một đồ thị được gọi là đồ thị hai phía đầy đủ nếu nó là đồ thị hai phía và mỗi đỉnh thuộc tập đỉnh thứ nhất có cạnh nối đến tất cả các định của tập đỉnh thứ hai, và được kí hiệu là Km,n (m, n là số lượng đỉnh ở mỗi tập) 2. Biểu diễn đồ thị Có nhiều cách biểu diễn đồ thị, để thuận tiện cho việc lưu trữ và tính toán trên máy tính, ba cách biểu diễn thường gặp nhất của đồ thị: 1. Ma trận kề: trong cách biểu diễn này, các đỉnh của đồ thị được đánh số lần lượt từ 1 đến n (với n là số đỉnh của đồ thị).