Bảng chú giải

Select one of the keywords on the left…

Đồ thị và Mạng lướiGiới thiệu

Reading time: ~15 min
Reveal all steps

Mỗi ngày chúng ta tiếp xúc với muôn vàn những mạng lưới và kết nối khác nhau: hệ thống đường xá, đường ray, mạng điện thoại, internet, mạch điện tử và ngay cả liên kết phân tử. Chúng ta cũng có những kết nối xã hội với bạn bè và gia đình. Tất cả những hệ thống này chứa đựng những điểm gọi là đỉnhvòng tròngiao điểm, trong đó một số điểm được nối với nhau bởi cạnhgiới hạncặp. Trong toán học hệ thống này được gọi là đồ thị.

Lý thuyết về đồ thị là môn học về đồ thị và các đặc tính của nó. Đây là một trong những vấn đề thú vị và trực quan nhất trong toán học, và nó có muôn vàn những ứng dụng quan trọng khác nhau trong đời sống:

Hệ thống đường giao thông và đường ray

Tổ hợp mạch điện

Hệ thống phân phối

Mối quan hệ bạn bè

Mạng tế bào thần kinh

Mạng Internet

Chúng ta có thể vẽ một đồ thị đơn giản sử dụng các đường và vòng tròn. Vị trí của các vòng tròn hay chiều dài của mỗi đường không quan trọng – chúng ta chỉ quan tâm cách chúng kết nối với nhau như thế nào. Các đường có thể cắt nhau và không cần phải là đường thẳng.

Trong một vài biểu đồ, cạnh chỉ đi theo một hướng nhất định. Chúng được gọi là đồ thị có hướng.

Trong những đồ thị khác có chứa nhiều mảng khác nhau không được kết nối bởi cạnh biên. Những đồ thị này gián đoạn.

Một số đồ thị khác có thể có nhiều cạnh kết nối cùng hai đỉnh (đa biên), hay những đỉnh kết nối với chính nó (vòng/khuyên).

Để đơn giản, chúng ta chỉ chú trọng tìm hiểu về những đồ thị kết nối và không định hướng trong bài này, tạm gác qua đồ thị đa biên hay vòng/khuyên.

Chúng ta có thể tạo nhiều đồ thị từ một đồ thị có sẵn bằng cách di chuyển các đỉnh và cạnh. Kết quả có được gọi là đồ thị con. Đây là một số ví dụ về đồ thị và đồ thị con:

Đồ thị có cấp số chính là số đỉnh của nó. Đồ thị cũng có cấp độ là số cạnh gặp nhau ở đỉnh đó.

Cấp số:

Cấp số:

Cấp độ:

Cấp độ:

Các đồ thị có một vòng nối các đỉnh được gọi là [vòng]. Mọi đồ thị vòng đều có cùng một số lượng đỉnh và cạnhnhiều cạnh hơn đỉnhít cạnh hơn đỉnh.