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

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:

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.

Để đơ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á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.