Giáo Trình Lý Thuyết Đồ Họa Cơ Bản - Khái Niệm và Thuật Ngữ Quan Trọng

Giáo trình Lý thuyết đồ họa cơ bản biên soạn theo chương trình đào tạo chuẩn, phù hợp sinh viên ngành phục vụ đào tạo và nghiên c

• Tác giả: Nguyễn Đức Nghĩa
• Trường học: Trường Cao Đẳng Kỹ Thuật Lý Tự Trọng
• Chuyên ngành: Lý Thuyết Đồ Hoạ
• Đề tài: Các Khái Niệm Cơ Bản Của Lý Thuyết Đồ Thị
• Loại tài liệu: Giáo trình

Mục lục chi tiết

• 1. CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
• 1.1. ĐỊNH NGHĨA ĐỒ THỊ
• 1.2. CÁC THUẬT NGỮ CƠ BẢN
• 1.3. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
• 1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
• 1.4.1. Đồ thị đầy đủ
• 1.4.2. Đồ thị hai phía
• 1.4.3. Đồ thị phẳng
• 1.5. Bài tập lý thuyết
• 1.5.1. Bài toán tô màu đồ thị
• 1.6. Bài tập lập trình
• 1.6.1. Mảng một chiều
• 1.6.2. Sắp xếp
• 1.6.3. Mảng (ma trận)
• 1.6.4. Struct
• 1.6.5. File
• 2. CHƯƠNG 2: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH
• 2.1. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ
• 2.1.1. Ma trận trọng số
• 2.1.2. Ma trận liên thuộc đỉnh-cạnh
• 2.2. DANH SÁCH CẠNH (CUNG)

Tóm tắt

I. Tổng Quan Về Giáo Trình Học Phần Lý Thuyết Đồ Thị Cơ Bản

Giáo trình lý thuyết đồ thị là nền tảng cốt lõi trong khoa học máy tính và toán học ứng dụng. Học phần này cung cấp kiến thức về 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 đó. Mục tiêu chính là trang bị cho người học khả năng mô hình hóa và giải quyết các bài toán thực tế phức tạp, từ mạng máy tính, logistics, đến phân tích mạng xã hội. Nội dung giáo trình bắt đầu từ những khái niệm cơ bản nhất, phân biệt rõ các loại đồ thị như đồ thị vô hướng và đồ thị có hướng, đơn đồ thị và đa đồ thị. Việc nắm vững các định nghĩa này là bước đệm quan trọng để tiếp cận các thuật toán đồ thị phức tạp hơn. Theo tài liệu của Trường Cao Đẳng Kỹ Thuật Lý Tự Trọng, việc hiểu rõ "Định nghĩa 1" về các loại đồ thị là yêu cầu tiên quyết. Lý thuyết đồ thị và ứng dụng của nó không chỉ giới hạn trong học thuật mà còn mở ra nhiều cơ hội trong các lĩnh vực công nghệ cao, đòi hỏi tư duy logic và kỹ năng giải quyết vấn đề một cách có hệ thống.

1.1. Khái niệm cốt lõi Đồ thị vô hướng và đồ thị có hướng

Trong lý thuyết đồ thị, hai loại cấu trúc cơ bản nhất là đồ thị vô hướng và đồ thị có hướng. Một đơn đồ thị vô hướng G = (V,E) bao gồm tập đỉnh V và tập cạnh E, trong đó mỗi cạnh là một cặp đỉnh không có thứ tự. Ngược lại, một đơn đồ thị có hướng G = (V,E) có tập cung E, mỗi cung là một cặp đỉnh có thứ tự. Sự khác biệt này dẫn đến các khái niệm khác nhau về bậc. Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh liên thuộc với nó. Trong khi đó, đồ thị có hướng sử dụng khái niệm bán bậc ra (số cung đi ra) và bán bậc vào (số cung đi vào). Theo "Định lý 2" trong tài liệu gốc, tổng tất cả các bán bậc ra bằng tổng tất cả các bán bậc vào và bằng tổng số cung của đồ thị. Hiểu rõ sự khác biệt này là nền tảng để xây dựng các cấu trúc dữ liệu và giải thuật phù hợp cho từng loại bài toán, chẳng hạn như phân tích mạng xã hội (vô hướng) hay lập lịch công việc (có hướng).

1.2. Tầm quan trọng của lý thuyết đồ thị và ứng dụng thực tiễn

Lý thuyết đồ thị và ứng dụng của nó hiện diện trong hầu hết mọi khía cạnh của cuộc sống hiện đại. Trong mạng máy tính, các thuật toán tìm đường đi ngắn nhất như thuật toán Dijkstra giúp tối ưu hóa việc truyền dữ liệu. Trong logistics và vận tải, bài toán tìm chu trình Hamilton giúp xác định lộ trình hiệu quả nhất cho người giao hàng. Các mạng xã hội sử dụng đồ thị để phân tích mối quan hệ và đề xuất kết nối. Thậm chí trong công nghệ chế tạo mạch in, bài toán về đồ thị phẳng cũng đóng vai trò quan trọng. Giáo trình này không chỉ cung cấp lý thuyết suông mà còn tập trung vào việc áp dụng kiến thức để giải quyết các bài tập lý thuyết đồ thị mô phỏng các vấn đề thực tế, từ đó giúp người học hình thành tư duy phân tích và thiết kế giải pháp một cách hiệu quả.

II. Thách Thức Khi Học Lý Thuyết Đồ Thị Và Cấu Trúc Dữ Liệu

Việc tiếp cận lý thuyết đồ thị đặt ra không ít thách thức, đặc biệt với những người mới bắt đầu. Một trong những khó khăn lớn nhất là tính trừu tượng của các khái niệm. Việc hình dung một bài toán thực tế dưới dạng một đồ thị với các đỉnh và cạnh đòi hỏi tư duy logic và khả năng mô hình hóa cao. Bên cạnh đó, số lượng thuật toán đồ sộ với những đặc điểm và trường hợp áp dụng riêng biệt có thể gây nhầm lẫn. Người học phải phân biệt rõ khi nào nên sử dụng tìm kiếm theo chiều sâu (DFS), khi nào cần tìm kiếm theo chiều rộng (BFS), hay khi nào các thuật toán tham lam như thuật toán Prim hoặc thuật toán Kruskal là lựa chọn tối ưu. Một thách thức khác là việc lựa chọn cấu trúc dữ liệu và giải thuật phù hợp để biểu diễn đồ thị. Quyết định sử dụng ma trận kề hay danh sách kề ảnh hưởng trực tiếp đến hiệu suất của chương trình, đặc biệt với các đồ thị có kích thước lớn. Việc thiếu các tài liệu ôn tập có hệ thống và các bài tập lý thuyết đồ thị đa dạng cũng là một rào cản lớn trong quá trình tự học và củng cố kiến thức.

2.1. Phân biệt các thuật ngữ cơ bản Bậc đường đi và chu trình

Một trong những rào cản đầu tiên khi học lý thuyết đồ thị là hệ thống thuật ngữ dày đặc. Các khái niệm như "bậc", "đường đi" và "chu trình" là nền tảng nhưng dễ gây nhầm lẫn. Bậc của một đỉnh (degree) trong đồ thị vô hướng là số cạnh nối với nó, trong khi khái niệm này được chia thành bán bậc vào và bán bậc ra trong đồ thị có hướng. Đường đi (path) là một dãy các đỉnh kề nhau, trong khi chu trình (cycle) là một đường đi có đỉnh đầu trùng với đỉnh cuối. Tài liệu gốc định nghĩa rất rõ: "Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại". Việc không phân biệt rõ các khái niệm này sẽ dẫn đến sai lầm nghiêm trọng khi triển khai các thuật toán đồ thị, ví dụ như khi xác định tính liên thông hay tìm kiếm chu trình Euler.

2.2. Khó khăn trong việc lựa chọn cấu trúc dữ liệu và giải thuật

Lựa chọn đúng cấu trúc dữ liệu và giải thuật là chìa khóa thành công trong việc giải quyết bài toán đồ thị. Việc chọn giữa ma trận kề và danh sách kề phụ thuộc vào đặc điểm của đồ thị và yêu cầu của thuật toán. Ma trận kề cho phép kiểm tra quan hệ kề giữa hai đỉnh trong thời gian O(1) nhưng tốn bộ nhớ O(n²), phù hợp với đồ thị dày đặc. Ngược lại, danh sách kề tiết kiệm bộ nhớ hơn cho đồ thị thưa (O(n+m)) nhưng việc kiểm tra quan hệ kề lại tốn thời gian hơn. Tương tự, việc lựa chọn giữa tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS) phụ thuộc vào mục tiêu bài toán: DFS phù hợp để tìm kiếm trong không gian sâu, trong khi BFS là lựa chọn tối ưu để tìm đường đi ngắn nhất về số cạnh. Sự lựa chọn sai lầm có thể khiến thuật toán chạy chậm hoặc thậm chí không đưa ra được kết quả đúng.

III. Phương Pháp Biểu Diễn Đồ Thị Hiệu Quả Trên Máy Tính

Để thực hiện các thuật toán đồ thị trên máy tính, việc lựa chọn cấu trúc dữ liệu để biểu diễn đồ thị là vô cùng quan trọng. Quyết định này tác động lớn đến hiệu quả và độ phức tạp của giải thuật. Chương 2 của giáo trình tập trung phân tích các phương pháp biểu diễn cơ bản, giúp người học đưa ra lựa chọn phù hợp cho từng bài toán cụ thể. Các phương pháp phổ biến bao gồm ma trận kề, danh sách kề, ma trận trọng số, và danh sách cạnh. Mỗi phương pháp có ưu và nhược điểm riêng, phù hợp với các loại đồ thị và yêu cầu thuật toán khác nhau. Ví dụ, tài liệu nhấn mạnh: "Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề... là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau... hay không, chúng ta chỉ phải thực hiện một phép so sánh". Tuy nhiên, nhược điểm là yêu cầu bộ nhớ lớn. Việc nắm vững các phương pháp này là kỹ năng cơ bản để triển khai hiệu quả các cấu trúc dữ liệu và giải thuật liên quan đến đồ thị.

3.1. Phân tích ưu nhược điểm của ma trận kề và danh sách kề

Ma trận kề là một ma trận vuông cấp n (với n là số đỉnh), trong đó phần tử A[i,j] = 1 nếu có cạnh nối đỉnh i và j, và bằng 0 nếu ngược lại. Phương pháp này cho phép kiểm tra sự tồn tại của một cạnh một cách nhanh chóng. Tuy nhiên, nó luôn đòi hỏi không gian lưu trữ O(n²), không hiệu quả cho các đồ thị thưa (số cạnh ít hơn nhiều so với n²). Ngược lại, danh sách kề lưu trữ cho mỗi đỉnh một danh sách các đỉnh kề với nó. Phương pháp này chỉ yêu cầu không gian O(n+m) (với m là số cạnh), rất phù hợp cho đồ thị thưa. Nhược điểm của nó là để kiểm tra hai đỉnh có kề nhau không, cần phải duyệt qua danh sách kề của một trong hai đỉnh. Sự đánh đổi giữa tốc độ truy cập và không gian lưu trữ là yếu tố cốt lõi cần cân nhắc.

3.2. Sử dụng ma trận trọng số và danh sách cạnh cho bài toán

Trong nhiều bài toán thực tế, các cạnh của đồ thị được gán một giá trị gọi là trọng số. Để biểu diễn loại đồ thị này, người ta sử dụng ma trận trọng số. Cấu trúc của nó tương tự ma trận kề, nhưng thay vì giá trị 0/1, các phần tử lưu trọng số của cạnh. Nếu không có cạnh nối, giá trị có thể được đặt là vô cùng. Đây là cấu trúc dữ liệu đầu vào tiêu chuẩn cho các thuật toán tìm đường đi ngắn nhất như thuật toán Dijkstra hay Bellman-Ford. Một phương pháp khác là danh sách cạnh, đơn giản chỉ là một danh sách tất cả các cạnh (hoặc cung) của đồ thị. Mỗi phần tử trong danh sách thường là một bộ ba (u, v, w) đại diện cho cạnh từ đỉnh u đến v với trọng số w. Cấu trúc này đặc biệt hữu ích cho các thuật toán xử lý cạnh một cách độc lập như thuật toán Kruskal để tìm cây khung tối thiểu.

IV. Hướng Dẫn Các Thuật Toán Đồ Thị Tìm Kiếm Phổ Biến Nhất

Các thuật toán duyệt và tìm kiếm là trái tim của lý thuyết đồ thị. Chúng cung cấp phương pháp có hệ thống để khám phá cấu trúc của một đồ thị, làm tiền đề cho việc giải quyết hàng loạt bài toán phức tạp. Giáo trình giới thiệu chi tiết hai thuật toán nền tảng và phổ biến nhất: tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS). Ý tưởng chính của DFS là ưu tiên đi "sâu" nhất có thể vào một nhánh trước khi quay lui. Ngược lại, BFS hoạt động theo cơ chế khám phá các đỉnh theo từng lớp, bắt đầu từ đỉnh nguồn và lan ra các đỉnh lân cận. Như tài liệu mô tả, DFS sử dụng cấu trúc ngăn xếp (STACK) một cách ngầm định thông qua đệ quy, trong khi BFS "được xây dựng trên cơ sở thay thế ngăn xếp (STACK) bởi hàng đợi (QUEUE)". Việc hiểu rõ nguyên lý, cách cài đặt và độ phức tạp tính toán của hai thuật toán đồ thị này là yêu cầu bắt buộc để giải các bài toán về tìm đường đi, kiểm tra tính liên thông, hay tìm chu trình.

4.1. Nguyên lý hoạt động của tìm kiếm theo chiều sâu DFS

Tìm kiếm theo chiều sâu (DFS) là một thuật toán đồ thị hoạt động dựa trên nguyên tắc "vào sau, ra trước" (LIFO), thường được cài đặt bằng đệ quy. Bắt đầu từ một đỉnh nguồn, thuật toán sẽ đi sâu vào một đỉnh kề chưa được duyệt. Quá trình này tiếp tục cho đến khi gặp một đỉnh không còn đỉnh kề nào chưa duyệt. Tại đây, thuật toán sẽ quay lui (backtrack) về đỉnh trước đó và tiếp tục khám phá các nhánh khác. Ưu điểm của DFS là khả năng tìm ra lời giải nhanh chóng nếu nó nằm sâu trong cây tìm kiếm và yêu cầu bộ nhớ ít hơn BFS trong trường hợp cây tìm kiếm rộng. DFS là nền tảng cho nhiều thuật toán quan trọng khác như tìm thành phần liên thông mạnh, sắp xếp topo, và phát hiện chu trình trong đồ thị có hướng.

4.2. Khám phá thuật toán tìm kiếm theo chiều rộng BFS

Tìm kiếm theo chiều rộng (BFS) duyệt đồ thị theo từng mức, dựa trên nguyên tắc "vào trước, ra trước" (FIFO) và được cài đặt bằng cách sử dụng hàng đợi (queue). Bắt đầu từ đỉnh nguồn, thuật toán sẽ duyệt tất cả các đỉnh kề với nó. Sau đó, với mỗi đỉnh vừa được duyệt, thuật toán lại tiếp tục duyệt tất cả các đỉnh kề chưa được ghé thăm của chúng. Quá trình này lặp lại cho đến khi tất cả các đỉnh có thể đến được từ đỉnh nguồn đều đã được duyệt. Một ứng dụng quan trọng và trực tiếp của BFS là tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị không có trọng số. Theo ghi chú trong tài liệu: "Đường đi tìm được theo thuật toán tìm kiếm theo chiều rộng là đường đi ngắn nhất (theo số cạnh)". Điều này làm cho BFS trở thành công cụ không thể thiếu trong các bài toán mạng và định tuyến.

V. Cách Áp Dụng Lý Thuyết Đồ Thị Euler và Hamilton Thực Tế

Đồ thị Euler và đồ thị Hamilton là hai dạng đồ thị đặc biệt với những ứng dụng thực tiễn quan trọng, mặc dù bản chất của chúng rất khác nhau. Giáo trình dành riêng một chương để nghiên cứu hai loại đồ thị này, tập trung vào các định lý nhận dạng và ý nghĩa ứng dụng. Một chu trình Euler là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần. Bài toán này có nguồn gốc từ bài toán "Bảy cây cầu ở Konigsberg" và có ứng dụng trong việc lập kế hoạch cho các tuyến đường tối ưu, ví dụ như xe thu gom rác hoặc máy kiểm tra mạch in. Ngược lại, một chu trình Hamilton là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần. Bài toán tìm chu trình Hamilton phức tạp hơn nhiều và thuộc lớp bài toán NP-đầy đủ, nhưng lại có ứng dụng rộng rãi trong logistics (bài toán người giao hàng), giải mã gen và thiết kế mạng. Việc phân biệt rõ hai khái niệm này và các điều kiện liên quan là mục tiêu cốt lõi của học phần này.

5.1. Nhận biết đồ thị Euler qua định lý về bậc của đỉnh

Việc xác định một đồ thị có phải là đồ thị Euler hay không tương đối đơn giản nhờ vào định lý do Euler phát hiện. Đối với đồ thị vô hướng liên thông, nó có một chu trình Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn. Nó sẽ có một đường đi Euler (đi qua mỗi cạnh đúng một lần nhưng không phải chu trình) khi và chỉ khi nó có đúng hai đỉnh bậc lẻ. Đối với đồ thị có hướng liên thông mạnh, nó là đồ thị Euler khi và chỉ khi tại mọi đỉnh, bán bậc vào bằng bán bậc ra (deg⁺(v) = deg⁻(v)). Những định lý này cung cấp một tiêu chuẩn rõ ràng và hiệu quả để kiểm tra sự tồn tại của chu trình Euler, giúp giải quyết nhanh chóng các bài toán liên quan mà không cần phải thử tất cả các khả năng.

5.2. Điều kiện đủ và thách thức với chu trình Hamilton

Trái ngược với đồ thị Euler, cho đến nay vẫn chưa có một điều kiện cần và đủ đơn giản để xác định sự tồn tại của một chu trình Hamilton. Đây là một trong những bài toán mở nổi tiếng nhất trong lý thuyết đồ thị. Tuy nhiên, có một số điều kiện đủ đã được chứng minh. Định lý Dirak (1952) là một kết quả kinh điển, phát biểu rằng: một đơn đồ thị vô hướng với n đỉnh (n ≥ 3), nếu bậc của mọi đỉnh đều không nhỏ hơn n/2, thì đồ thị đó là đồ thị Hamilton. Mặc dù điều kiện này rất chặt, nó cung cấp một công cụ hữu ích để khẳng định tính Hamilton cho một lớp đồ thị dày đặc. Do sự phức tạp của bài toán, việc tìm chu trình Hamilton trong thực tế thường phải dựa vào các thuật toán heuristic hoặc quay lui, vốn có độ phức tạp tính toán rất cao.

VI. Bí Quyết Ôn Tập Hiệu Quả Với Tài Liệu Lý Thuyết Đồ Thị

Để chinh phục học phần lý thuyết đồ thị, việc ôn tập có phương pháp là yếu tố quyết định. Thay vì học thuộc lòng các định lý, người học cần tập trung vào việc hiểu sâu bản chất và mối liên hệ giữa các khái niệm. Một bí quyết quan trọng là kết hợp giữa lý thuyết và thực hành. Sau khi học một thuật toán đồ thị mới, hãy tự mình cài đặt nó bằng một ngôn ngữ lập trình và thử nghiệm với nhiều bộ dữ liệu khác nhau. Việc này không chỉ giúp củng cố kiến thức mà còn rèn luyện kỹ năng lập trình. Bên cạnh đó, việc hệ thống hóa kiến thức thông qua sơ đồ tư duy hoặc bảng so sánh các thuật toán (ví dụ so sánh DFS và BFS, so sánh thuật toán Prim và thuật toán Kruskal) sẽ giúp ghi nhớ lâu hơn. Tận dụng các tài liệu ôn tập chất lượng và chủ động giải quyết các bài tập lý thuyết đồ thị sẽ xây dựng một nền tảng kiến thức vững chắc và sự tự tin khi đối mặt với các kỳ thi.

6.1. Hệ thống bài tập lý thuyết đồ thị từ cơ bản đến nâng cao

Cách tốt nhất để nắm vững lý thuyết đồ thị là thông qua việc giải bài tập. Bắt đầu với các bài tập cơ bản như biểu diễn đồ thị bằng ma trận kề hoặc danh sách kề, tính bậc của đỉnh, xác định đường đi. Sau đó, chuyển sang các bài tập cài đặt thuật toán như DFS và BFS để kiểm tra tính liên thông hoặc tìm đường đi. Cuối cùng, thử thách bản thân với các bài toán ứng dụng phức tạp hơn, yêu cầu áp dụng các thuật toán như thuật toán Dijkstra để tìm đường đi ngắn nhất, hoặc các thuật toán tìm cây khung tối thiểu. Các bài tập lý thuyết đồ thị được cung cấp trong giáo trình là nguồn tài nguyên quý giá, giúp người học kiểm tra sự hiểu biết và áp dụng kiến thức vào các tình huống cụ thể, từ đó phát hiện ra những lỗ hổng kiến thức để kịp thời bổ sung.

6.2. Khai thác slide bài giảng lý thuyết đồ thị hiệu quả nhất

Slide bài giảng lý thuyết đồ thị thường cô đọng những kiến thức cốt lõi nhất của học phần. Để khai thác hiệu quả, không nên chỉ đọc lướt qua. Hãy xem mỗi slide như một đề mục cần tìm hiểu sâu. Với mỗi khái niệm hoặc thuật toán được giới thiệu, hãy tìm kiếm thêm thông tin từ giáo trình hoặc các nguồn tài liệu khác để hiểu rõ hơn. Đặc biệt chú ý đến các ví dụ minh họa và mã giả (pseudocode), vì chúng là cầu nối giữa lý thuyết trừu tượng và cài đặt thực tế. Sử dụng slide bài giảng lý thuyết đồ thị như một khung sườn cho quá trình ôn tập, kết hợp với ghi chú cá nhân và giải các bài tập liên quan. Biến tài liệu này thành một tài liệu ôn tập sống động và cá nhân hóa sẽ giúp quá trình học tập trở nên hiệu quả và thú vị hơn rất nhiều.

Nội dung chính

TÀI LIỆU HỌC PHẦN: LÝ THUYẾT ĐỒ THỊ

Đơn vị biên soạn: Trường Cao đẳng Kỹ thuật Lý Tự Trọng TP. Hồ Chí Minh

---

Tổng quan về giáo trình (250-300 từ)

Tài liệu học tập học phần Lý thuyết đồ thị được biên soạn bởi Trường Cao đẳng Kỹ thuật Lý Tự Trọng (trực thuộc UBND Thành phố Hồ Chí Minh), phục vụ công tác giảng dạy và học tập trong chương trình đào tạo khối ngành Công nghệ thông tin và Kỹ thuật máy tính ở bậc Cao đẳng và Đại học. Trong chương trình đào tạo, học phần này giữ vai trò là môn học cơ sở ngành, kết nối giữa khối kiến thức toán rời rạc và các môn học chuyên sâu về cấu trúc dữ liệu, thuật toán và mạng máy tính.

Mục tiêu học tập của giáo trình được thiết kế nhằm trang bị cho người học:

• Hệ thống định nghĩa, tính chất và các định lý nền tảng của lý thuyết đồ thị vô hướng và có hướng.
• Các phương pháp mô hình hóa dữ liệu đồ thị trong bộ nhớ máy tính tương ứng với từng điều kiện đồ thị dày hay thưa.
• Kỹ thuật thiết kế và cài đặt các giải thuật tìm kiếm, duyệt đồ thị, kiểm tra liên thông, xác định chu trình Euler và Hamilton.
• Năng lực chuyển đổi các bài toán thực tiễn (như bài toán định tuyến, lập lịch thi công, thiết kế mạch in) thành bài toán đồ thị và lập trình giải quyết bằng ngôn ngữ C/C++.

Cấu trúc giáo trình phân bổ thời lượng theo nguyên tắc cân bằng giữa lý thuyết và thực hành (50% lý thuyết, 50% thực hành bài tập và lập trình). Cách tiếp cận nội dung đi từ việc hình thành khái niệm toán học thuần túy, minh họa trực quan bằng hình học, chuyển dịch sang cấu trúc dữ liệu trừu tượng, và kết thúc bằng việc hiện thực hóa thuật toán qua mã nguồn cụ thể kèm theo các bộ dữ liệu kiểm thử (test cases). Điểm đặc sắc của tài liệu là việc tích hợp trực tiếp mã nguồn chương trình toàn văn (DFS.CPP, BFS.CPP, PATHDFS.CPP, Lienthong1.CPP) và các bài toán ứng dụng thực tế có cấu trúc tệp dữ liệu vào/ra chuẩn (MH.DAT, INFOR.INP, dothi.inp).

---

Nội dung kiến thức cốt lõi (500-600 từ)

Các chương và chủ đề chính

Nội dung giáo trình được cấu trúc theo tiến trình logic chặt chẽ qua các chương học trọng tâm:

1. Chương 1: Các khái niệm cơ bản của lý thuyết đồ thị (Tuần 1 & 2 - 4 tiết LT, 4 tiết TH):

   • Giới thiệu định nghĩa đơn đồ thị, đa đồ thị, giả đồ thị vô hướng (chứa khuyên) và có hướng (chứa cung lặp).
   • Khái niệm đỉnh kề, cạnh liên thuộc, bậc đỉnh $\text{deg}(v)$, đỉnh cô lập ($\text{deg}=0$), đỉnh treo ($\text{deg}=1$), bán bậc vào $\text{deg}^-(v)$ và bán bậc ra $\text{deg}^+(v)$.
   • Khái niệm đường đi đơn, chu trình đơn, tính liên thông, thành phần liên thông, đỉnh rẽ nhánh (đỉnh khớp) và cạnh cầu; liên thông mạnh và liên thông yếu trong đồ thị có hướng.
   • Các dạng đồ thị đặc biệt: Đồ thị đầy đủ $K_n$ với $\frac{n(n-1)}{2}$ cạnh; Đồ thị hai phía $G=(X \cup Y, E)$; Đồ thị phẳng, định lý Kuratowski liên quan đồ thị con đồng cấu $K_{3,3}$ và $K_5$, công thức Euler $r = m - n + 2$; Bài toán tô màu đồ thị và sắc số.

2. Chương 2: Biểu diễn đồ thị trên máy vi tính (Tuần 3 - 2 tiết LT, 2 tiết TH):

   • Mô tả và phân tích 4 cấu trúc dữ liệu lưu trữ đồ thị: Ma trận kề (đối xứng đối với đồ thị vô hướng, tiêu tốn $n^2$ đơn vị bộ nhớ), Ma trận trọng số (sử dụng các giá trị $0, +\infty, -\infty$), Ma trận liên thuộc đỉnh - cạnh (kích thước $n \times m$, lưu các giá trị $1, -1, 0$), Danh sách cạnh/cung (tiêu tốn $2m$ bộ nhớ, thích hợp cho đồ thị thưa $m \le 6n$), và Danh sách kề $\text{ke}(v)$.

3. Chương 3: Thuật toán tìm kiếm trên đồ thị, tìm đường đi và tính liên thông:

   • Thuật toán tìm kiếm theo chiều sâu (DFS) sử dụng đệ quy/ngăn xếp (Stack), độ phức tạp $O(n+m)$.
   • Thuật toán tìm kiếm theo chiều rộng (BFS) sử dụng hàng đợi (Queue), độ phức tạp $O(n+m)$.
   • Ứng dụng DFS/BFS giải quyết bài toán tìm đường đi giữa hai đỉnh thông qua mảng Truoc[] (BFS cho đường đi ngắn nhất theo số cạnh) và xác định số lượng cũng như liệt kê các đỉnh trong từng thành phần liên thông thông qua biến Inconnect và mảng Index[] (hoặc lienthong[]).

4. Chương 4: Đồ thị Euler và Đồ thị Hamilton (Tuần 6 & 7 - 4 tiết LT, 4 tiết TH):

   • Đồ thị Euler: Khái niệm đường đi/chu trình Euler, điều kiện cần và đủ của Euler (1736), thuật toán mở rộng chu trình và thuật toán Fleury (tránh đi qua cầu).
   • Đồ thị Hamilton: Khái niệm đường đi/chu trình Hamilton, điều kiện đủ Dirac (1952) với đỉnh có bậc $\ge \frac{n}{2}$, tính chất của đồ thị đấu loại (mọi đồ thị đấu loại là nửa Hamilton; đồ thị đấu loại liên thông mạnh là Hamilton).

Kiến thức nền tảng được xây dựng

• Các định lý cơ bản (Fundamental theories):
  • Định lý bắt tay: Trong đồ thị vô hướng $G=(V,E)$ có $m$ cạnh, tổng bậc các đỉnh bằng hai lần số cạnh: $\sum_{v \in V} \text{deg}(v) = 2m$.
  • Hệ quả số đỉnh bậc lẻ trong đồ thị vô hướng luôn là một số chẵn.
  • Định lý bán bậc đồ thị có hướng: Tổng các bán bậc ra bằng tổng các bán bậc vào và bằng số cung: $\sum \text{deg}^+(v) = \sum \text{deg}^-(v) = m$.
  • Định lý đồ thị hai phía: Đơn đồ thị là đồ thị hai phía khi và chỉ khi không chứa chu trình có độ dài lẻ.
  • Định lý Euler cho đồ thị phẳng liên thông: $r = m - n + 2$ (trong đó $r$ là số miền, $m$ là số cạnh, $n$ là số đỉnh).
  • Định lý đặc trưng đồ thị Euler: Đồ thị vô hướng liên thông là Euler khi và chỉ khi mọi đỉnh có bậc chẵn; là nửa Euler khi và chỉ khi có không quá 2 đỉnh bậc lẻ. Đồ thị có hướng liên thông mạnh là Euler khi và chỉ khi $\text{deg}^+(v) = \text{deg}^-(v), \forall v \in V$.
  • Định lý Dirac (1952): Đơn đồ thị vô hướng $n > 2$ đỉnh có bậc mọi đỉnh $\ge \frac{n}{2}$ là đồ thị Hamilton.
• Nguyên lý cốt lõi (Core principles):
  • Đánh đổi không gian và thời gian trong biểu diễn đồ thị (Ma trận kề truy xuất $O(1)$ nhưng tốn $O(n^2)$ bộ nhớ; Danh sách cạnh tốn ít bộ nhớ $O(m)$ nhưng truy xuất lân cận mất $O(m)$).
  • Cơ chế duyệt trạng thái qua ngăn xếp (vào sau ra trước - DFS) và hàng đợi (vào trước ra trước - BFS).
  • Nguyên tắc tham lam (Greedy) trong bài toán tô màu đồ thị và nguyên tắc định tuyến tránh cầu trong thuật toán Fleury.
• Khung cấu trúc thiết yếu (Essential frameworks):
  • Khung biểu diễn ma trận và danh sách trong lập trình cấu trúc C/C++.
  • Khung thuật toán duyệt tổng quát sử dụng mảng đánh dấu chuaxet[] (hoặc daxet[]).

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Cài đặt thành thạo các thuật toán đồ thị bằng C/C++; thao tác xử lý mảng hai chiều, cấu trúc bản ghi struct, danh sách liên kết; xử lý đọc/ghi luồng dữ liệu tệp văn bản (FILE *, fopen, fprintf, fscanf).
• Kỹ năng phân tích (Analytical skills): Phân tích và chứng minh các tính chất đồ thị (tính phẳng, sắc số, tính liên thông, chu trình Euler/Hamilton); đánh giá độ phức tạp thuật toán dựa trên số đỉnh $n$ và số cạnh $m$.
• Năng lực thực hành ứng dụng (Practical competencies): Mô hình hóa và lập trình giải quyết các bài toán kỹ thuật như: kiểm tra tính hợp lệ của ma trận biểu diễn, bài toán phát hiện bế tắc và lập lịch môn học (KT3.CPP), bài toán truyền tin mạng email tối thiểu (INFOR.INP), bài toán định tuyến hai đường truyền an toàn không trùng kênh trên mạng máy tính.

---

Phương pháp giảng dạy và học tập (300-350 từ)

Giáo trình áp dụng phương pháp sư phạm kết hợp chặt chẽ giữa lý thuyết suy diễn và thực nghiệm lập trình. Quy trình học tập được phân bổ cố định: mỗi khối kiến thức lý thuyết đều có số tiết bài tập và thực hành tương đương đi kèm (tỷ lệ 1:1).

[Khái niệm Toán học / Định lý] 
[Mô hình hóa dữ liệu (Ma trận / Danh sách)]
[Thiết kế thuật toán / Mã giả]
[Cài đặt C/C++ & Kiểm thử trên File I/O]

• Bài tập lý thuyết và tình huống nghiên cứu (Case studies):

  • Tình huống kinh điển bài toán 7 cây cầu Konigsberg (Euler 1736) mở đầu lý thuyết đồ thị Euler.
  • Bài toán 3 căn hộ và 3 giếng cấp năng lượng (minh họa đồ thị phẳng $K_{3,3}$).
  • Bài toán sắp xếp 6 cuộc họp $A, B, C, D, E, F$ vào các buổi không trùng lặp (ứng dụng bài toán tô màu đồ thị).
  • Tình huống tổ chức mạng lưới lập trình viên gửi email thông tin (INFOR.INP, INFOR.OUT).

• Bài tập thực hành và lập trình:

  • Viết chương trình kiểm tra tính hợp lệ của ma trận kề đọc từ tệp dothi.inp (kiểm tra đường chéo chính $a[i][i]=0$ và tính đối xứng $a[i][j] = a[j][i]$).
  • Chuyển đổi dữ liệu tương hỗ giữa ma trận kề, ma trận trọng số, ma trận liên thuộc và danh sách cạnh/kề.
  • Lập trình toàn văn các thuật toán duyệt DFS, BFS, tìm đường đi (PATHDFS.CPP), đếm số thành phần liên thông (Lienthong1.CPP với tệp dữ liệu li_thong.inp).
  • Cài đặt bài toán xác định thời gian hoàn thành khóa học và phát hiện bế tắc của $N$ môn học dựa trên quan hệ trước/sau (MH.DAT, TKB.DAT).

• Phương pháp đánh giá: Kết hợp kiểm tra tự luận giải tích (chứng minh định lý, tính số miền $r$, tính số cạnh $m$, vẽ đồ thị phẳng, tô màu xác định sắc số) và chấm điểm mã nguồn chương trình dựa trên độ chính xác của kết quả xuất ra tệp dữ liệu chuẩn.

• Hướng dẫn tự học: Sinh viên thực hiện ôn tập các cấu trúc dữ liệu nền tảng (đệ quy, mảng một chiều, mảng hai chiều, struct, file text) qua hệ thống 18 bài tập chuẩn bị đầu khóa; tự chạy tay từng bước (dry-run/trace) thuật toán trên sơ đồ đỉnh-cạnh trước khi biên dịch mã nguồn C/C++.

---

Điểm nổi bật và cập nhật (250-300 từ)

Tài liệu học phần Lý thuyết đồ thị của Trường Cao đẳng Kỹ thuật Lý Tự Trọng tích hợp các nội dung học thuật từ tài liệu tham khảo tiêu chuẩn: Toán rời rạc (Phần 2: Lý thuyết đồ thị) của nhóm tác giả Nguyễn Đức Nghĩa – Nguyễn Tô Thành (Đại học Bách khoa Hà Nội).

Các điểm cập nhật và liên kết thực tiễn trong giáo trình bao gồm:

• Ứng dụng công nghệ chế tạo mạch in: Tích hợp lý thuyết đồ thị phẳng và định lý Kuratowski vào bài toán thiết kế đường dẫn trên bo mạch điện tử sao cho các đường dây dẫn không cắt nhau ngoài các nút kết nối.
• Mô hình hóa bài toán lập lịch và quản lý dự án: Đưa bài toán quản lý tiến độ $N$ môn học có ràng buộc phụ thuộc trước/sau vào thực hành lập trình, yêu cầu sinh viên xây dựng thuật toán phát hiện chu trình (bế tắc) và xác định số công việc cực đại có thể thực hiện đồng thời trong một đơn vị thời gian.
• Kỹ thuật định tuyến mạng an toàn: Xây dựng bài toán truyền tin an toàn giữa hai nút $s$ và $t$ trên mạng máy tính thông qua hai đường truyền độc lập (không có kênh truyền nào bị dùng chung), tối ưu hóa tổng chi phí đường truyền.
• Tiêu chuẩn hóa mã nguồn: Toàn bộ thuật toán đều được minh họa bằng mã giả chi tiết và mã nguồn C/C++ hoàn chỉnh, có định dạng đọc/ghi tệp tường minh (.inp, .out, .dat), phù hợp với tiêu chuẩn thực hành lập trình thuật toán hiện đại.

---

Đối tượng sử dụng giáo trình (200-250 từ)

• Sinh viên:
  • Sinh viên năm thứ nhất và năm thứ hai theo học các ngành Công nghệ thông tin, Kỹ thuật phần mềm, Truyền thông và Mạng máy tính, Khoa học máy tính tại các trường Cao đẳng và Đại học kỹ thuật.
  • Sinh viên cần tài liệu học tập theo học chế tín chỉ có tích hợp bài tập lập trình thực hành.
• Kiến thức tiên quyết (Prerequisites):
  • Người học cần nắm vững kiến thức môn Toán rời rạc đại cương (tập hợp, logic mệnh đề, quan hệ).
  • Có kỹ năng lập trình căn bản với ngôn ngữ C hoặc C++: hiểu rõ cơ chế đệ quy, xử lý mảng một chiều và hai chiều, cấu trúc struct, kỹ thuật sử dụng con trỏ và thao tác đọc/ghi tệp văn bản.
• Giảng viên: Sử dụng làm đề cương bài giảng chi tiết, khung phân bổ tiết dạy (lý thuyết - thực hành) và ngân hàng câu hỏi bài tập giải tích, bài tập lập trình phục vụ đánh giá quá trình và thi kết thúc học phần.
• Tự học và nghiên cứu: Dành cho người học muốn củng cố nền tảng cấu trúc dữ liệu đồ thị và thuật toán phục vụ lập trình thi đấu hoặc thiết kế hệ thống mạng.

---

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với ai?

Giáo trình được biên soạn chuyên biệt cho sinh viên bậc Cao đẳng và Đại học kỹ thuật khối ngành Công nghệ thông tin và Kỹ thuật máy tính, cũng như người học cần tài liệu chuẩn hóa về thuật toán đồ thị gắn liền với mã nguồn C/C++.

2. Cần kiến thức nền nào để học tốt học phần này?

Người học cần hoàn thành khối kiến thức Toán rời rạc cơ bản và Kỹ thuật lập trình C/C++, đặc biệt là kỹ năng xử lý mảng hai chiều, đệ quy, danh sách, ngăn xếp/hàng đợi và thao tác tệp tin (fopen, fscanf, fprintf).

3. Điểm khác biệt của giáo trình này so với các tài liệu toán thuần túy?

Giáo trình không chỉ trình bày các định lý và chứng minh giải tích mà luôn đi kèm thuật giải chi tiết, mã giả, phân tích độ phức tạp tính toán và cung cấp toàn văn chương trình cài đặt C/C++ có thể biên dịch trực tiếp.

4. Làm sao để tự học và cài đặt thuật toán hiệu quả?

Người học nên làm theo trình tự 4 bước: (1) Nắm vững định nghĩa và định lý, (2) Giải các bài tập vẽ hình và tính toán thủ công trên giấy, (3) Lần vết từng bước (dry-run) thuật toán với mảng đánh dấu chuaxet[], (4) Lập trình giải các bài toán thực hành trên file I/O theo định dạng mẫu trong tài liệu.

5. Có tài liệu bổ trợ nào được khuyến nghị kèm theo giáo trình?

Tài liệu tham khảo chính yếu được trích dẫn trong giáo trình là cuốn Toán rời rạc (Phần 2: Lý thuyết đồ thị) của hai tác giả Nguyễn Đức Nghĩa và Nguyễn Tô Thành.

---

Kết luận (150 từ)

Giáo trình Lý thuyết đồ thị của Trường Cao đẳng Kỹ thuật Lý Tự Trọng cung cấp một hệ thống tri thức hoàn chỉnh từ nền tảng toán học rời rạc đến kỹ thuật lập trình thuật toán trên máy vi tính. Cấu trúc nội dung phân định rõ ràng giữa lý thuyết, cấu trúc dữ liệu lưu trữ, giải thuật duyệt, và các dạng đồ thị chuyên biệt (Euler, Hamilton, đồ thị phẳng, đồ thị hai phía).

Lộ trình học tập đề xuất:

1. Tiếp cận lý thuyết và định lý tại Chương 1.
2. Nắm vững kỹ thuật biểu diễn dữ liệu tại Chương 2.
3. Cài đặt các thuật toán nền tảng DFS/BFS và bài toán liên thông tại Chương 3.
4. Nghiên cứu các dạng đồ thị đặc thù và thuật toán chuyên sâu tại Chương 4.

Nguồn tài nguyên học tập đi kèm bao gồm hệ thống bài tập lý thuyết giải tích, bộ mã nguồn mẫu C/C++ toàn văn và tài liệu tham khảo chuẩn mực Toán rời rạc (Nguyễn Đức Nghĩa – Nguyễn Tô Thành).

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

UBND THANH PHO HO CHi MINH TRUONG CAO DANG KY THUAT LY T U TRO b f//iA/I0ï0//0//0)/0//00i0//8//0/10//08/10) QC PHAN: LY THUYE DO HOA CHƯƠNGI CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐÔ THỊ tập/thực hành) (tuân 1 & 2: T: ống cộng có 4 tiết lý thuyết và 4 tiết hưởng dẫn bài 1. ĐỊNH NGHĨA ĐỎ THỊ đỉnh này. Chúng ta phân biệt Đề 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ào đó của đồ thị. các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai Định nghĩa 1.

và E là tập các cặp không có thứ tự Đơn đồ thị vô hướng G = (V,E) bao gom V la tập các đỉnh, gồm hai phân tử khác nhau của V gọi là các cạnh. không có thứ tự Đa đề thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp và e; được gọi là cạnh lặp nếu gom hai phan tir khac nhau cua V goi la cac canh. Hai canh e; chúng cùng tương ứng với mội cặp đỉnh. tập các cặp không có thứ tự Giả đô thị vô hướng GŒ = (V, E) bao gom V là tập các đỉnh va E là gọi là khuyên gồm hai phần tử (không nhất thiết phải khác nhau) của Ý gọi là cạnh.

Cạnh e được nếu nó có dạng e = (u, 1). la tap các cặp có thứ tự gom hai Don đô thị có hướng GŒ = (. È) bao gồm V là tập các đỉnh va E phân tử khác nhau của V gọi là các cung. la tap cac cap có thit te gm hai Đa đồ thị có hướng Œ = (V, È) bao gôm V là tập các đỉnh va E ứng với cùng một cặp đỉnh được phan tit khdc nhau cua V goi la cac cung.

Hai cung e}, 2 twong gọi là cung lặp. vô hướng và đơn đồ thị có Trong các phần tiếp theo chủ yêu chúng ta sé làm việc với đơn đồ thị chúng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn khi nhắc đến 2. CÁC THUẬT NGỮ CƠ BẢN Định nghĩa 1.

(u,v) là cạnh của đề thị G. Nếu e Hai đỉnh u và v của đề thị vô hướng G được gọi là kê nhau nếu u và v, hoặc cũng nói là noi = (u, v) là cạnh của dé thị ta nói cạnh này là liên thuộc với hai đỉnh của cạnh (u, v). định u va dinh v, đồng thời các đỉnh u va v sé dugc gọi là các đỉnh đâu định nghĩa sau Để có thể biết có vao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào Dinh nghia 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu ; r e d b Hinh 1.

Dé thivé hướng Thi du 1. Xét đồ thị cho trong hinh 1, ta cd deg(a) = 1, deg(b) = 4, deg(c) = 4, deg() = 3, deg(d) = 1, deg(e) = 3, deg(g) = 0 trén đỉnh g là đỉnh Dinh bac 0 goi la dinh cé Idp. Dinh bac | duge goi 1a dinh treo. Trong vi du cô lập, a và d là các đỉnh treo.

Bậc của đỉnh có tính chất sau: Định lý 1. bằng hai Giả sử G = (V, E) la dé thi vô hướng với m cạnh. Khi đó tông bậc của tất cả các đỉnh lần số cạnh. Dé thị với n đỉnh có bậc là 6 có bao nhiêu cạnh? 3n.

Giải: Theo định lý 1 ta có 2m = ốn. Từ đó suy ra tổng các cạnh của đồ thị là Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chăn. và nói cung Nếu e = (u, v) là cung của đề thị có hướng G thì ta nói hai đỉnh u và v là kê nhau, v.

| bán bậc vào Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra và của một đỉnh. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đỗ thị có hướng là số cung của đô thị ẩi ra (v) (deg (v)) khỏi nó (ải vào nó) và ký hiệu là deg’ Hình 2. Đồ thị có hướng Thí dụ 3. Xét đồ thị cho trong hình 2.

bán bậc Do mỗi cung (u, v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần trong | ra của đỉnh u nên ta có: Dinh ly 2. Giả sử G = (V, E) la do thi có hướng. Khi đó Tổng tất cả các bán bậc ra bằng tông tất cả các bán bậc vào bằng số cung. - Đề thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đô thị vô hướng tương ứng với đồ thị có hướng đã cho.

CHU TRÌNH. ĐỎ THỊ LIÊN THÔNG Định nghĩa 1. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên đương, trên đỗ thị vô hướng G = (P, E) là dãy xạ, Xi,. Xu-l, Xn trong đó t = xạ, V = Xa, (Xi, Xa) CL, i= 0, 1, 2,.

Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (xo, X)), (Xã X2),. (Xe, Xu) Dinh u gọi là đỉnh đâu, còn đỉnh v gọi là đỉnh cuối của đường ẩi. Đường ẩi có đỉnh dau trùng nếu -_ với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường di hay chu trình được gọi là đơn như không có cạnh nào bị lặp lại.

Trên đồ thị vô hướng cho trong hinh 1: a, d, c, f, e 1a đường đi đơn độ đài 4. Còn d, e, c, a không là đường đi, đo (c,e) không phải là cạnh của dé thi. Day b, c, £ e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ đài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần.

d e f d e f di trén 46 thi Hình 1. Duing Khái niệm đường đi và chu trình trên dé thị có hướng được định nghĩa hoàn toàn tương tự như trong trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung. Đường ấi độ dài n từ đỉnh u đến đỉnh v, trong đó, n là số nguyên dương, trên đô thị có hưởng Ơ = (, E) là dãy xạ, Xị,. Xn-I, Xn trong đó u = xụ, V= X„ (Xi xa) EE, 1 = Ú, I, 2,.

Đường i nói trên còn có thể biểu diễn dưới dạng dãy các cung: (xo, XI), (XI, X2), ., (Xn-, Xe) Dinh u gọi là đỉnh đầu, còn đình v gọi là đỉnh cuối của đường đi. Đường di cé dinh dau tring với đỉnh cuối (tức là u = v) được goi là chu trình. Đường đi hay chu trình được gọi la don nếu như không có cạnh nào bị lặp lại. Trên đồ thị có hướng cho trong hinh 1: a, d, c, f, e la dwong đi đơn độ dài 4.

Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần. Đà thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

- Ta gọi đồ thị con của đồ thị G = (V, E) là đỗ thị H = (W, F), trong đó W c V và F€E Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những dé thi con liên thông như vậy ta sẽ gọi là các “hành phan lién thông của đồ thị. đô Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi thị làm tăng số thành phân liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phân liên thông của đỗ thị.

i giữa hai Đề thị có hướng G = (V, E) được goi là liên thông mạnh nếu luôn tìm được đường đỉnh bắt kỳ của nó. với nó là Đề thị có hướng G = (V, E) được gọi lò liên thông yếu nếu đỗ thị vô hướng tương ứng vô hướng liên thông. MỘT SỐ DẠNG ĐỎ THỊ ĐẶC BIỆT Đồ thị đầy đủ. Dé thi day đủ n đỉnh, ký hiệu bởi Kạ, là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối.

Cac dé thi Ks, Ka, Ks cho trong hình đưới đây. đồ thị đầy đủ Kạ, Ka, Ks Đồ thị đầy đủ Kạ có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. Đồ thị hai phía. ˆ | Đơn đồ thị G=(V,E) được gọi là hai phía nếu như tập đình V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nảo đó trong X với một đỉnh nào đó X2 Y.

Khi đó ta sẽ sử dụng ký hiệu G=(X © Ÿ, E) để chỉ đỗ thị hai phía với tập đỉnh Định lý sau đây cho phép nhận biết một đơn đồ thị có phải là hai phía hay không. Don dé thị là đô thị hai phía khi và chỉ khi nó không chứa chu trình độ đài lẻ. Đồ thị hai phía Đồ thị phẳng. Đồ thị được gọi là đồ thị phẳng nếu ta có th vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh.

Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị. Thí dụ đồ thị K¿ là phẳng, vì có thể vẽ nó trên mặt phăng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh (xem hình 6). Đồ thị K¿ là đồ thị phẳng Một điều đáng lưu ý nếu đồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với các cạnh nối là các đoạn thắng không cắt nhau ngoài ở đỉnh (ví dụ xem cách vẽ Ka trong hình 6). Để nhận biết xem một đồ thị có phải là đồ thị phẳng có thể sử dụng định lý Kuratovski, mà để phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh (u,v) của đồ thi là việc loại bỏ cạnh này khỏi đỗ thị và thêm vào đô thị một đỉnh mới w cùng với hai cạnh (u,w), (w, u).

Hai đồ thị G(V,E) và H=(W,F) được gọi là đồng cấu nếu chúng có thé thu được từ cùng một đô thị nào đó nhờ phép chia cạnh. Đồ thị là phẳng khi và chỉ khi nó không chita dé thi con déng cau v6i K3,3 hoặc Ks.