Khác biệt giữa bản sửa đổi của “Lý thuyết đồ thị”

=== Các cấu trúc danh sách ===

* '''[[Danh sách liên thuộc]]''' (''Incidence list'') - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng [[mảng]] (''array'') hoặc [[danh sách liên kết động]] (''linked list'')), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh này.

* '''[[Danh sách kề]]''' (''Adjacency list'') - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng, cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó, do các đỉnh này đã được liệt kê tường minh.

 

=== Các cấu trúc ma trận ===

* '''[[Ma trận liên thuộc]]''' (''Incidence matrix'') - Đồ thị được biểu diễn bằng một [[ma trận (toán học)|ma trận]] <math>[b_{ij}]</math> kích thước ''p'' × ''q'', trong đó ''p'' là số đỉnh và ''q'' là số cạnh, <math>b_{ij} = 1</math> chứa dữ liệu về quan hệ giữa đỉnh <math>v_i</math> và cạnh <math>x_j</math>. Đơn giản nhất: <math>b_{ij} = 1</math> nếu đỉnh <math>v_i</math> là một trong 2 đầu của cạnh <math>x_j</math>, bằng 0 trong các trường hợp khác.

* '''[[Ma trận kề]]''' (''Adjaceny matrix'') - một ma trận ''N'' × ''N'', trong đó ''N'' là số đỉnh của đồ thị. Nếu có một cạnh nào đó nối đỉnh <math>v_i</math>với đỉnh <math>v_j</math> thì phần tử <math>M_{i, j}</math> bằng 1, nếu không, nó có giá trị 0. Cấu trúc này tạo thuận lợi cho việc tìm các đồ thị con và để đảo các đồ thị.

* '''[[Ma trận dẫn nạp]]''' (''Admittance matrix'') hoặc '''[[ma trận Laplace|ma trận Kirchhoff]]''' (''Kirchhoff matrix'') hay '''ma trận Laplace''' (''Laplacian matrix'') - được định nghĩa là kết quả thu được khi lấy [[ma trận bậc]] (''degree matrix'') trừ đi [[ma trận kề]]. Do đó, ma trận này chứa thông tin cả về quan hệ kề (có cạnh nối hay không) giữa các đỉnh lẫn bậc của các đỉnh đó.