▶BÀI ❶. MỘT VÀI KHÁI NIỆM CƠ BẢN VỀ LÝ THUYẾT ĐỒ THỊ
-6839064135Ⓐ. Tóm tắt kiến thức
❶. Đồ thịa) Khái niệm đồ thịMột đồ thị là một tập hợp hữu hạn các điềm (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.Chú ý. Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng, mà bản chất là đổ thị có bao nhiêu đĩnh, bao nhiêu cạnh và đïnh nào được nối với đỉnh nào.Ta thường kí hiệu V(G) là tập hợp các đỉnh và E(G) là tập hợp các cạnh của đồ thị G, và viết G=(V,E). Cạnh nối hai đỉnh A và B thường được kí hiệu là AB hoặc BA, và khi đó A và B gọi là hai đỉnh kề nhau. Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C thì ta gọi cạnh ấy là một khuyên, kí hiệu là CC.Hình 2.1 cho ta một đồ thị có 4 đỉnh là A,B,C,D và 5 cạnh là AB,AC,AD,BC và CC.b) Đơn đồ thị và đa đồ thịMột đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là một đơn đồ thị.Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối bằng nhiều cạnh, gọi là một đa đồ thị.Chú ý. Trong cuốn sách này, khi chỉ nói từ đồ thị thì ta hiểu là đơn đồ thị. Khi nào cần xét đa đồ thị thì ta sẽ nói rõ.c) Đồ thị đầy đủMột đồ thị là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó đều được nối bằng một cạnh.Nhận xét. Một đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh của nó đều là kề nhau. Một đồ thị đầy đủ hoàn toàn được xác định bởi số đỉnh của nó. Đồ thị đầy đủ có n đỉnh thường được kí hiệu là Kn. ❶. Đồ thịa) Khái niệm đồ thịMột đồ thị là một tập hợp hữu hạn các điềm (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.Chú ý. Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng, mà bản chất là đổ thị có bao nhiêu đĩnh, bao nhiêu cạnh và đïnh nào được nối với đỉnh nào.Ta thường kí hiệu V(G) là tập hợp các đỉnh và E(G) là tập hợp các cạnh của đồ thị G, và viết G=(V,E). Cạnh nối hai đỉnh A và B thường được kí hiệu là AB hoặc BA, và khi đó A và B gọi là hai đỉnh kề nhau. Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C thì ta gọi cạnh ấy là một khuyên, kí hiệu là CC.Hình 2.1 cho ta một đồ thị có 4 đỉnh là A,B,C,D và 5 cạnh là AB,AC,AD,BC và CC.b) Đơn đồ thị và đa đồ thịMột đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là một đơn đồ thị.Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối bằng nhiều cạnh, gọi là một đa đồ thị.Chú ý. Trong cuốn sách này, khi chỉ nói từ đồ thị thì ta hiểu là đơn đồ thị. Khi nào cần xét đa đồ thị thì ta sẽ nói rõ.c) Đồ thị đầy đủMột đồ thị là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó đều được nối bằng một cạnh.Nhận xét. Một đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh của nó đều là kề nhau. Một đồ thị đầy đủ hoàn toàn được xác định bởi số đỉnh của nó. Đồ thị đầy đủ có n đỉnh thường được kí hiệu là Kn.
