Graph và một số ứng dụng trong chương trình trung học phổ thông

DANH MỤC HÌNH VẼ Trang Hình 1.1 Đồ thị hàm số y = sinx 4 Hình 1.2 Đồ thị biểu diễn ví dụ 1 5 Hình 1.3 Đồ thị biểu diễn ví dụ 2 6 Hình 1.4 Đồ thị biểu diễn ví dụ 3 6 Hình 1.5 Biểu diễn phẳng của Graph 7 Hình 1.6 Biểu diễn Graph con và Graph thành phần 8 Hình 1.7 Biểu diễn bậc của đỉnh 9 Hình 1.8 Dãy cạnh kế tiếp 9 Hình 1.9 Biểu diễn cạnh có hướng 12 Hình 2.1 Ma trận kề đồ thị vô hướng không trọng số và đồ thị có hướng có tróng số 14 Hình 2.2 Biểu diễn cài đặt đồ thị bằng danh sách cạnh trên mảng và trên danh sách móc nối 17 Hình 2.3 Đồ thị vô hướng không trọng số 20 Hình 2.4 Biểu diễn Graph bằng danh sách kề 22 Hình 2.5 Đồ thị vô hướng 24 Hình 2.6 Ma trận kề đồ thị trọng số vô hướng và đồ thị trọng số có hướng 31 Hình 2.7a Đồ thị trọng số có hướng 31 Hình 2.7b Biểu diễn đồ thị trọng số bằng danh sách lân cận kề 31 Hình 2.8 Đồ thị vô hướng có trọng số ví dụ 4 33 Hình 2.9 Cây khung DFS(1) và cây khung BFS(1) 37 Hình 2.10 Đồ thị vô hướng có trọng số ví dụ 5 40 MỤC LỤC Trang MỞ ĐẦU 1. Lý do chọn đề tài Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thụy Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng. Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong khoảng vài chục năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học v.v... Một trong các mục tiêu khi đưa tin học vào nhà trường là nhằm giúp cho học sinh có khả năng phân tích, tổng hợp, trừu tượng hóa, khái quát hóa vấn đề và đặc biệt là phát triển tư duy. Hiện nay, có nhiều bài toán trong chương trình trung học phổ thông được giải quyết nhờ vận dụng lý thuyết đồ thị. Để tìm hiểu sâu về lý thuyết đồ thị và ứng dụng của nó trong chương trình tin học phổ thông nên em đã chọn đề tài “Graph và một số ứng dụng trong chương trình trung học phổ thông”. 2. Mục đích nghiên cứu Tìm hiểu một số vấn đề về Graph như các khái niệm cơ bản về Graph, phân loại Graph… Để hiểu sâu sắc hơn lý thuyết Graph, cài đặt một số thuật toán, từ đó ứng dụng lý thuyết Graph vào chương trình tin học phổ thông để giải quyết một số bài toán liên quan. 3. Nội dung tìm hiểu, nghiên cứu Một số vấn đề về lý thuyết về Graph. Một số thuật toán cơ bản trên Graph. Ứng dụng lý thuyết Graph vào giải quyết một số bài toán cụ thể trong chương trình tin học phổ thông. 4. Phương pháp nghiên cứu Nghiên cứu tài liệu: Nghiên cứu các tài liệu về lý thuyết đồ thị và các bài toán liên quan. Phương pháp thực nghiệm: Lập trình kiểm thử, tìm hiểu thông tin trong một số Website trên mạng. Tổng kết kinh nghiệm: Tổng kết các kiến thức đã học tập được. Tham khảo ý kiến chuyên gia: Tiếp thu ý kiến đóng góp của các thầy cô và ý kiến của các bạn bè. Cấu trúc của đề tài Mở đầu: Nêu ra lý do chọn đề tài, phương pháp, nội dung tìm hiểu và mục đích nghiên cứu, cấu trúc đề tài. Chương 1: Một số vấn đề về lý thuyết Graph. Chương 2: Một số thuật toán cơ bản trên Graph: Tìm hiểu và cài đặt các thuật toán cơ bản trên Graph cụ thể như: biểu diễn Graph trên máy tính, phép duyệt Graph, tìm đường đi và kiểm tra tính liên thông của Graph….Các thuật toán được cài đặt trên ngôn ngữ lập trình Pascal. Chương 3: Ứng dụng của Graph vào chương trình Tin học phổ thông: Đưa ra và vận dụng lý thuyết Graph vào cài đặt một số bài toán cụ thể trong chương trình tin học phổ thông theo từng dạng: Bài toán duyệt đồ thị, bài toán về đường đi trên đồ thị, bài toán về cây khung đồ thị. Kết luận: Nêu ra những vấn đề đã tìm hiểu, một số công việc chính đã được thực hiện, hướng phát triển tiếp theo của đề tài trong tương lai. Em xin chân thành cảm ơn Thầy giáo, TS Nguyễn Mạnh Đức - Giảng viên Tin học, Khoa Toán, Đại học Sư phạm Thái Nguyên, người đã trực tiếp hướng dẫn và tận tình chỉ bảo em trong suốt quá trình làm đề tài. Em xin chân thành cảm ban chủ nhiệm Khoa Toán cùng các Thầy, Cô trong khoa đã tạo điều kiện để em thực hiện đề tài này. Tôi cũng xin cảm ơn các bạn sinh viên, người thân đã động viên, giúp đỡ trong thời gian thực hiện đề tài. Thái Nguyên, tháng 4 năm 2013 Sinh viên Vi Văn Sơn Chương 1MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT GRAPH  1.1. Khái niệm cơ bản về graph 1.1.1. Những bài toán và vấn đề dẫn đến khái niệm graph [1] Hình 1.1. Đồ thị hàm số y =sinx Hai chữ “đồ thị” vẫn thường xuyên xuất hiện trong toán học và cả trong đời sống hàng ngày. Trong các giờ học toán, chúng ta có nói tới đồ thị của các hàm số. Chẳng hạn, trong hình dưới có biểu diễn đồ thị của hàm số y=sinx. Trong các công sở, các nhân viên phải lập các biểu đồ theo dõi số lượng tiêu thụ điện hoặc xăng dầu hàng tháng,và họ cũng có thể gọi những biểu đồ đó là đồ thị... Tóm lại khái niệm đồ thị là một khái niệm toán học khá quen thuộc đối với chúng ta nhằm biểu diễn tương quan đi lại hai đối tượng hoặc nhiều đối tượng toán học khác nhau. Lý thuyết đồ thị (theo tiếng Anh và tiếng Đức đọc là: “graph”) nghiên cứu những tính chất toán học, những quan hệ mà không phụ thuộc vào bản chất riêng của những mối quan hệ này. Để tránh khỏi bị nhầm là đồ thị của hàm số, ta sử dụng thuật ngữ “graph” trong tài liệu này ở các phần tiếp theo. Graph là một mô hình toán học có thể dùng để giải quyết khá nhiều bài toán và vấn đề toán học. Một graph có thể hiểu đơn giản là một hệ thống các đỉnh và các cạnh nối với nhau. Gần với mô hình lí thuyết graph là các bài toán thoáng qua như những bài toán hình học mà thực chất việc giải quyết chúng không thể chỉ sử dụng những kiến thức hình học thông thường. Trên mặt phẳng, có những bài toán dường như là bài toán hình học như thế, nhưng chúng ta có thể xem xét một số ví dụ để thấy không chỉ có thể dùng kiến thức hình học để giải quyết được chúng. Việc muốn giải quyết những bài toán này cần đi sâu hơn nữa vào những mối quan hệ toán học của các đối tượng toán học trong bài toán. Một số ví dụ có nguồn gốc phát sinh từ các bài toán hình học mà bản chất thực sự của nó là các bài toán về lí thuyết grap. Ví dụ 1: Hình 1.2. Đồ thị biểu diễn ví dụ 1 Có ba cái nhà và ba cái giếng. Mỗi nhà có ba đường đi từ nó tới ba cái giếng đó. Hỏi có thể làm những con đường đi như vậy sao cho không có hai con đường nào cắt nhau hay không? Để giải quyết bài toán này, chúng ta có thể giả sử là các nhà là các điểm A1, A2, A3 trên mặt phẳng và các giếng là các điểm B1, B2, B3 nào đó. Các con đường đi là các đường (liên tục) nối các đỉnh Ai với các đỉnh Bi. Khi đó, câu hỏi của bài toán là liệu có những điểm Ai tới các điểm Bi trên mặt phẳng sao cho không có hai con đường nào cắt nhau hay không? Bằng cách thiết lập mô hình này, chúng ta đã thiết lập một graph có 6 đỉnh và 9 cạnh. Chúng ta thấy rằng để giải bài toán này, các kiến thức hình học không còn giúp gì được cho chúng ta nữa. Bài toán đòi hỏi phải có kiến thức sâu sắc hơn về mối quan hệ nào đó của quan hệ các đỉnh và các cạnh. [1] Nhưng không phải chỉ với một số bài toán hoặc một số vấn đề toán học có nguồn gốc hình học mới có thể đưa về mô hình đỉnh – cạnh như trên. Mô hình đỉnh – cạnh của chúng ta tỏ ra là mô hình rất hiệu quả để nắm bắt được chính xác bản chất toán học thật sự của nhiều đối tượng toán học. Các đỉnh được biểu diễn cho các đại lượng tham gia và các cạnh nối chúng biểu diễn mối quan hệ đi lại của chúng theo một tiêu chuẩn nào đó được đưa ra. Ví dụ 2: Hãy biểu thị graph quan hệ không nguyên tố cùng nhau của các số trong tập hợp { 1, 2, 3, 4, 5, 6 }. Bài toán này được giải quyết bằng phương pháp graph như sau: Trước hết ta chọn 6 điểm trên mặt phẳng biểu diễn cho 6 số 1, 2, 3, 4, 5 và 6. Các điểm này được tô đậm để phân biệt với giao điểm của các cạnh của graph. Hình 1.3. Đồ thị biểu diễn ví dụ 2 Chúng ta nối hai đỉnh của graph bởi một đường nối (hình 1.3) nếu hai số tương ứng với hai đỉnh của chúng không nguyên tố cùng nhau. Trong biểu diễn graph như vậy, chúng ta có thể nhận ra ngay rằng có 3 số đôi một không nguyên tố cùng nhau. Mối quan hệ giữa các đại lượng ta xét rất có thể còn là các mối quan hệ trong đời sống. Chẳng hạn, cũng graph trong hình 2 biểu thị các mối quan hệ quen biết của 6 người, được đánh số từ 1 đến 6, nếu cho biết họ quen nhau khi số thứ tự tương ứng của họ không nguyên tố cùng nhau. Trong các ví dụ trên, các đỉnh của graph được nối bởi các cạnh cũng có thể có hướng và chỉ nối các đỉnh khác nhau với nhau. Trong lý thuyết graph các cạnh cũng có thể có hướng. Ví dụ 3: Có một trận đấu bóng bàn có một số đấu thủ cùng tham gia. Hai đấu thủ bất kì phải đấu với nhau đúng một hiệp. Điểm được cho mỗi hiệp là thắng 1 điểm, thua 0 điểm (không có hòa). Hỏi có khi nào trận đấu kết thúc với kết quả là tất cả các đấu thủ đều bằng điểm nhau hay không? Ta biểu diễn các đấu thủ tương ứng thành các đỉnh của một graph Hình 1.4. Đồ thị biểu diễn ví dụ 3 Hai đỉnh x và y của graph được nối bởi một cạnh có hướng đi từ x tới y nếu như đấu thủ x thắng đấu thủ y. Bài toán được đặt ra là có thể có graph tương ứng với n đấu thủ sao cho các đỉnh có số cạnh xuất phát từ chúng bằng nhau. Trong hình 1.4 là một graph thỏa mãn yêu cầu của bài toán với n=5. Trong nhiều trường hợp, chúng ta chấp nhận những cạnh nối một đỉnh đã cho với chính nó. Loại này được gọi là cạnh khuyên trong graph. Trong lý thuyết graph có cho phép giữa hai đỉnh có thể có nhiều cạnh nối. Trong trường hợp có nhiều cạnh (ít nhất là hai) nối 2 đỉnh khác nhau nào đó của một graph, thì ta gọi cạnh đó là cạnh kép. 1.1.2. Định nghĩa graph và các khái niệm cơ bản Thông thường chúng ta hay kí hiệu một graph bởi chữ G (chữ cái đầu của từ “Graph” trong tiếng Đức, ngôn ngữ dùng để viết cuốn sách đầu tiên về lí thuyết graph). Còn tập đỉnh thường được kí hiệu bởi chữ V (là chữ cái đầu tiên của từ “Vertices”) và tập cạnh bởi chữ cái E (chữ cái đầu của từ “Edges”). Graph không có cạnh có hướng thường được kí hiệu là G=(V,E), còn graph có các cạnh có hướng được kí hiệu là G=[V,E]. Việc dùng kí hiệu này không bắt buộc, mà chỉ là một thói quen mà thôi. Định nghĩa đồ thị: Một đồ thị G = (V, E) bao gồm một tập hữu hạn V = {v1, v2,…vn} các đỉnh (nút) và 1 tập hữu hạn E = {(vi, vj), vi, vj V} các cặp đỉnh gọi là cung (hay cạnh). Nếu (vi, vj) E thì ta nói có một cung nối vi với vj. Nếu cung (vi, vj) khác cung (vj, vi) thì G là đồ thị có hướng, ngược lại là không hướng. Một graph được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh). Hình vẽ như thế được gọi là một biểu diễn phẳng của graph. Hình 1.5. Biểu diễn phẳng của Graph Như chúng ta đã thấy trong các ví dụ trên, graph thường được biểu diễn trên mặt phẳng: các đỉnh được tô đậm và các cạnh nối các đỉnh là các đoạn thẳng hoặc là các đường cong nối các đỉnh này với nhau. Ngoài ra, chúng ta phải lưu ý rằng một graph có thể có nhiều biểu diễn trên mặt phẳng khác nhau. Trong hình 1.5 chúng ta có hai biểu diễn trên mặt phẳng khác nhau của một graph. Graph được phân loại theo tính chất cạnh của chúng. Trong mỗi graph các cạnh của graph thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào, đều không phải là điều quan trọng. Mà điều quan trọng là graph có bao nhiêu cạnh và đỉnh nào được nối với đỉnh nào. Một graph được gọi là graph vô hướng nếu tất cả các cạnh của nó đều là cạnh vô hướng. Graph được gọi là graph có hướng nếu tất cả các cạnh của nó đều là cạnh có hướng. Đỉnh xuất phát của một cạnh có hướng được gọi là đỉnh đầu, và đỉnh kết thúc của cạnh được gọi là đỉnh cuối của nó. Trong trường hợp graph có cả cạnh vô hướng cũng như cạnh có hướng thì graph được gọi là graph hỗn hợp. Một graph được gọi là graph đơn nếu nó không có khuyên và không có cạnh kép. Ngoài ra, ta gọi graph điểm là graph có đúng một đỉnh và không có cạnh nào. Graph rỗng dùng để gọi một graph không có đỉnh và cạnh nào cả. Hình 1.6. Biểu diễn Graph con và Graph thành phần 1.1.3. Graph con và graph thành phần Cho trước một graph G với tập đỉnh X và tập cạnh E. Một graph G’ với tập đỉnh X’ và tập cạnh E’ được gọi là graph con của graph G nếu X’ X và E’ E. Trong trường hợp X’ là tập con của X vả E’ là tập hợp tất cả các cạnh của G nối hai đỉnh của X’, thì G’ được gọi là graph thành phần của G và còn được gọi là graph sinh bởi tập đỉnh X’. Graph trong hình 1.6 có các cạnh được tô đậm là graph con của graph được biểu diễn trong hình. Nếu thêm vào nó hai cạnh a và b thì ta được một graph thành phần đã cho. Graph rỗng là graph thành phần của mọi graph cho trước. 1.2. Phân loại graph 1.2.1. Graph vô hướng Hình 1.7. Biểu diễn bậc của đỉnh 1.2.1.1. Bậc của đỉnh Trong phần này chúng ta chỉ xét những graph vô hướng, tức là những graph mà các cạnh của chúng không có hướng. Ta gọi bậc của một đỉnh là số cạnh xuất phát từ đỉnh đó (các khuyên được tính gấp đôi). Bậc của một đỉnh là một số không âm. Một đỉnh được gọi là đỉnh cô lập nếu nó không có cạnh nào cả, tức là khi đỉnh có bậc là 0. Đỉnh có bậc bằng 1 là đỉnh treo. Graph trong hình 1.7 có A là đỉnh cô lập, D là đỉnh treo. Đỉnh B có bậc là 3, đỉnh C có bậc là 2. Hình 1.8. Dãy cạnh kế tiếp Lưu ý rằng : trong một graph đơn vô hướng với n đỉnh thì bậc của một đỉnh bất kì luôn là một số nguyên không âm không vượt n-1. 1.2.1.2. Dãy cạnh kế tiếp Cho trước một graph G với tập đỉnh V và tập cạnh E. Hai cạnh của một graph cho trước gọi là hai cạnh kề nhau nếu như chúng có một đỉnh chung. Một dãy m cạnh ei = (Ai, Ai+1) với i=1, 2,…,m được gọi là một dãy cạnh nối tiếp và thường được kí hiệu là: H = (A1, e1, A2, e2 ,…, ek ,Ak+1) Trong trường hợp G là một graph đơn thì ta có thể biểu diễn một dãy cạnh kế tiếp qua các đỉnh của chúng, chẳng hạn dãy cạnh kế tiếp của H của ta ở trên được kí hiệu đơn giản là: H = (A1, A2, A3,…,Ak+1) Theo định nghĩa thì một dãy các cạnh liên tiếp kề nhau (mỗi cạnh kề với cạnh tiếp theo) chưa hẳn đã là dãy cạnh kế tiếp. Một dãy các cạnh liên tiếp kề nhau là một dãy các cạnh kế tiếp chỉ khi đỉnh chung của một cạnh bất kì (không phải là khuyên) với cạnh đứng trước nó và cạnh đứng sau nó khác nhau. Trong một dãy cạnh kế tiếp, một cạnh của graph có thể xuất hiện nhiều lần. Số m các cạnh được gọi là là độ dài của dãy cạnh kế tiếp. Cho trước dãy cạnh kế tiếp H = (A1, e1, A2, e2 ,…, ek ,Ak+1), đỉnh A1 được gọi là đỉnh đầu vả đỉnh Ak+1 được gọi là đỉnh cuối của H. H còn được gọi là dãy cạnh kế tiếp nối A1 với Ak+1. Trong trường hợp A1 ≠ Ak, dãy cạnh kế tiếp H được gọi là dãy cạnh kế tiếp không khép kín. Còn khi A1 = Ak thì H được gọi là dãy cạnh kế tiếp khép kín [1]. Một dãy cạnh kế tiếp e1, e2,…, ek với ei ≠ ej cho mọi i ≠ j được gọi là một xích đơn. Một xích đơn với đỉnh đầu là A và đỉnh cuối là B được gọi là một xích đơn nối A với B. 1.2.1.3. Chỉ số liên thông Khi biểu diễn một graph trên mặt phẳng, chúng ta đã thấy rằng có nhiều khi hình biểu diễn của chúng là những cụm tách rời nhau không được nối với nhau. Tương ứng với mỗi hình rời nhau như vậy là một graph thành phần của graph đã cho mà ta sẽ gọi là một phần liên thông của graph cho trước. Để chính xác hóa khái niệm liên thông, trước hết chúng ta nói hai đỉnh của một graph cho trước là liên thông với nhau nếu có một dãy cạnh kế tiếp nối chúng với nhau trong graph đã cho. Một đỉnh cho trước luôn được coi là liên thông với chính nó (được nối với chính nó bởi một dãy cạnh kế tiếp có độ dài 0). Một graph được gọi là liên thông nếu hai đỉnh bất kì của nó liên thông với nhau. Quan hệ “liên thông” có những tính chất cơ bản sau [1]: Mỗi đỉnh a của graph liên thông với chính nó. Nếu a liên thông với b thì b liên thông với a. Nếu a liên thông với b và b liên thông với c, thì a liên thông với c. Thực chất đây là một quan hệ tương đương trong tập hợp các đỉnh của graph. Quan hệ tương đương này chia tập đỉnh của graph thành các lớp có hai tính chất sau: Các đỉnh thuộc cùng một lớp thì liên thông với nhau. Các đỉnh không cùng thuộc một lớp không liên thông với nhau. Các lớp đỉnh này là đỉnh của graph thành phần liên thông trong graph cho trước, được gọi là thành phần liên thông của graph đã cho. 1.2.1.4. Đường đi trong graph Trong thực tế ứng dụng của cuộc sống, ta thường gặp một khái niệm khác của dãy cạnh kế tiếp là những dãy cạnh kế tiếp được tuân thủ nguyên tắc tối ưu là chúng không đi qua đỉnh nào của graph quá một lần. Một dãy cạnh kế tiếp trong một graph cho trước được gọi là một đường đi nếu chúng không đi qua đỉnh nào của graph quá 1 lần. Cũng tương tự như với dãy cạnh kế tiếp, nếu a và b là hai đỉnh đầu tiên và đỉnh cuối cùng của đường W, thì ta nói rằng W nối a với b. Chúng được gọi là đỉnh đầu và đỉnh cuối của con đường và được xem là phải khác nhau. Thông thường, đường đi được biểu diễn thông qua các đỉnh và các cạnh nối chúng, chẳng hạn: W = (p1, e1, p2, e2, p3, e3,…, ek-1, Pk) với pi là các đỉnh và ei là các cạnh của W. Đặc biệt, khi graph cho trước là graph đơn, thì ta có thể biểu diễn một đường đi thông qua tập đỉnh của nó, chẳng hạn: W = (p1 , p2 , p3 ,…, Pk) Số cạnh của một đường đi được gọi là độ dài của nó. 1.2.1.5. Chu trình của graph Khi định nghĩa đường đi nối hai đỉnh a và b của một graph, ta luôn giả thiết rằng các đỉnh a và b này phải khác nhau. Trong trường hợp a và b được nối với nhau bởi một cạnh, thì khi thêm cạnh (a, b) vào, ta thu được từ con đường đã cho một chu trình. Như vậy chu trình là một dãy cạnh kế tiếp khép kín sao cho mỗi đỉnh của graph được đi qua không quá một lần. Chu trình được kí hiệu bởi việc đưa ra các cạnh và các đỉnh liên tiếp nhau trên chu trình. Chẳng hạn, nếu chu trình C đi qua các đỉnh p1, p2, …, pk và các cạnh e1, e2, …, ek thì ta viết: C = (p1 , e1 , p2 , e2 , …, pk , ek , p1) Trong trường hợp graph là một đơn graph, thì thay vì viết rõ các cạnh và các đỉnh, chu trình được xác định duy nhất qua việc gọi tên các đỉnh nó đi qua. Chẳng hạn chu trình C ở trên có thể viết thành: C = (p1 , p2 ,…, pk , p1). Số cạnh của chu trình được gọi là độ dài của chu trình và thông thường hay được kí hiệu bởi l(C). Một khuyên lập thành một chu trình có độ dài 1. Một graph cho trước chỉ có chu trình có độ dài 2 nếu như nó có cạnh kép. Trong một graph đơn mỗi chu trình có độ dài ít nhất là 3. Một graph không đơn hiển nhiên luôn có ít nhất một chu trình (có độ dài 1 hoặc 2). Trong graph đơn không phải lúc nào ta cũng có thể tìm thấy một chu trình. Chẳng hạn các graph biểu diễn sơ đồ cấp điện, hoặc các sơ đồ cấp nước chẳng hạn. 1.2.2. Graph có hướng 1.2.2.1. Khái niệm cơ sở của graph có hướng x y u Hình 1.9. Biểu diễn cạnh có hướng Một graph được gọi là graph (hữu hạn) có hướng khi nó chỉ có các cạnh có hướng mà ta còn gọi là các cung. Một cung u được xác định nhờ điểm đầu x và điểm cuối y, mà ta thường kí hiệu u = [x, y], trong đó x được gọi là đỉnh xuất phát và y được gọi là đỉnh đích của u. Chúng ta cũng nói rằng u liên hợp với đỉnh x và đỉnh y. Graph có hướng G với tập đỉnh X và tập cạnh E thường được kí hiệu bởi G = [X, E]. Một graph có hướng cũng được biểu diễn trên mặt phẳng bởi một hình, trong đó các đỉnh được biểu diễn thành các điểm tô đậm, các cạnh có hướng và các cung là các đường liên tục và được bổ sung bởi mũi tên thể hiện chiều đi từ đỉnh xuất phát tới đỉnh đích. Các cung có cùng đỉnh xuất phát và đỉnh đích được gọi là các cung song song. Nếu đỉnh xuất phát và đỉnh đích có cùng một cung u trùng nhau thì cung u này được gọi là khuyên có hướng. Một graph không có cung song song và khuyên có hướng nào cả được gọi là graph có hướng đơn. Ta nói rằng cung u liên hợp với đỉnh x, nếu như x là đỉnh xuất phát hoặc là đỉnh đích của cung u. Nếu cung u liên hợp với đỉnh x, thì cung u được gọi là liên hợp hướng ra ngoài (liên hợp hướng vào trong) đối với đỉnh x là đỉnh xuất phát (đỉnh đích) của cung u. 1.3. Kết luận c