Một phương pháp tiêu chuẩn để xử lý các vấn đề đẳng cấu của đồ thị là ánh xạ mỗi đồ thị thành một biểu diễn chuỗi cụ thể được gọi là mã hoặc nhãn chính tắc của nó. Nhãn chuẩn có đặc tính là nếu hai biểu đồ là đồng cấu, thì mã của chúng phải bằng nhau.
Thuộc tính này cho phép chúng tôi kiểm tra tính đẳng cấu của đồ thị bằng cách phân tích các nhãn chính tắc của đồ thị. Giai đoạn đầu tiên hướng tới việc xây dựng nhãn chuẩn của biểu đồ là khám phá mô tả ma trận kề cho biểu đồ. Nó hiển thị một ví dụ của một ma trận như vậy cho đồ thị đã cho.
Một đồ thị có thể có nhiều hơn một mô tả ma trận kề vì có một số phương pháp để sắp xếp thứ tự các đỉnh trong ma trận kề. Hàng và cột đầu tiên tương quan với đỉnh a có 3 cạnh, hàng và cột thứ hai tương quan với đỉnh a khác có 2 cạnh, v.v. Nó có thể thay đổi lấy tất cả các mô tả ma trận kề cho một đồ thị, nó bắt buộc phải là đã xử lý tất cả các hoán vị có thể có của các hàng của ma trận.
Ví dụ - Xem xét ma trận sau
M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Ma trận hoán vị sau có thể được sử dụng để biến đổi hàng (và cột) đầu tiên với hàng thứ ba của M -
P13 = 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
trong đó P 13 có được bằng cách trao đổi hàng đầu tiên và hàng thứ ba của ma trận nhận dạng. Nó có thể trao đổi hàng đầu tiên và hàng thứ ba (và cột), ma trận hoán vị được nhân với M -
M′ = P13T X M X P13= 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16
Bước thứ hai là quyết định mô tả chuỗi cho mỗi ma trận kề. Vì ma trận kề là đối xứng nên việc tạo ra mô tả chuỗi phụ thuộc vào phần tam giác phía trên của ma trận là hiệu quả.
Mã có được bằng cách liên kết các mục của ma trận tam giác trên theo kiểu cột. Bước cuối cùng là so sánh tất cả các mô tả chuỗi của biểu đồ và chọn một chuỗi có giá trị từ vựng thấp nhất (hoặc cao nhất).
Cách tiếp cận trước đây có vẻ tốn kém vì nó cần chúng tôi xác định tất cả các ma trận kề có thể có của biểu đồ và đánh giá từng mô tả chuỗi của chúng để khám phá nhãn chuẩn. Hơn nữa, có kl hoán vị cần được xử lý cho mỗi đồ thị bao gồm k đỉnh.
Có nhiều phương pháp khác nhau được phát triển để giảm độ phức tạp của tác vụ này, chứa vào bộ nhớ đệm nhãn chuẩn đã tính toán trước đó và giảm số lượng hoán vị cần thiết để quyết định nhãn chuẩn bằng cách kết hợp nhiều dữ liệu hơn bao gồm nhãn đỉnh và mức độ của đỉnh.