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.

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.