Graph representation là gì?

Trong lý thuyết đồ thị (graph theory), biểu diễn đồ thị (graph representation) là một kỹ thuật để lưu trữ đồ thị vào bộ nhớ (memory) của máy tính.)

Để biểu diễn một đồ thị, chúng ta chỉ cần tập hợp các đỉnh (vertex) và đối với mỗi đỉnh là các hàng xóm (neighbor) của đỉnh (các đỉnh được nối trực tiếp với nó bằng một cạnh). Nếu nó là một đồ thị có trọng số (weighted graph), thì trọng số (weight ) sẽ được liên kết với mỗi cạnh (edge).

Có nhiều cách khác nhau để biểu diễn đồ thị một cách tối ưu, tùy thuộc vào mật độ các cạnh của nó, loại phép toán được thực hiện và mức độ dễ sử dụng.Ví dụ biểu diễn bằng ma trận kề (adjacency matrix), danh sách kề (adjacency list), ma trận liên thuộc (incidence matrix).