Cách tạo biểu đồ

Biểu đồ bao gồm các đỉnh và cạnh. Các đỉnh được kết nối bởi các cạnh theo một thuộc tính nhất định - mối quan hệ tỷ lệ, xác định tập hợp các cạnh. Trong trường hợp này, các vòng lặp và các đỉnh bị cô lập có thể hình thành.

Hướng dẫn sử dụng

Đặt một tập hợp các cạnh của đồ thị và một mối quan hệ được đưa ra theo đó người ta có thể vẽ một cạnh từ đỉnh này sang đỉnh khác. Ví dụ: tập hợp các đỉnh {1, 2, 3, 4, 5, 6, 7, 8}, hai đỉnh x và y theo tỷ lệ x + y <8.

Xây dựng một ma trận kề kề đỉnh. Để làm điều này, xây dựng một bảng vuông, số lượng hàng và cột trong bảng khớp với số lượng đỉnh. Sau đó đặt 1 tại giao điểm của hàng thứ i và cột thứ j, nếu các đỉnh i và j thỏa mãn tỷ lệ đã cho. Đặt 0 tại giao điểm của hàng thứ i và cột thứ j, nếu tỷ lệ cho các phần tử tương ứng không được thỏa mãn.

Trong ví dụ của chúng tôi, dòng đầu tiên được điền như sau:

1 + 1 <8, vì vậy tại giao điểm của hàng 1 và cột 1 là 1

1 + 2 <8, lại 1

1 + 3 <8, lại 1

…

1 + 7 <8, bất đẳng thức không chính xác, thì phần tử bảng này sẽ là 0

1 + 8 <8, lại 0

Để tìm ra số cạnh, hãy đếm số lượng đơn vị trong ma trận kề, trong khi không trích xuất các cạnh.

Trong ví dụ, do đó, một ma trận đối xứng đã thu được, do đó, đầu tiên các đơn vị được tính trên đường chéo chính của ma trận (được đánh dấu màu xanh lam), và sau đó là các đơn vị trên đường chéo chính (được đánh dấu màu đỏ). Tổng số xương sườn là 12.

Xây dựng một ma trận các sự cố (các cạnh). Để làm điều này, hãy vẽ một bảng, số lượng hàng trong đó bằng số đỉnh của đồ thị và số cột bằng với số cạnh. Đặt các đơn vị trong các dòng sẽ được kết nối bởi một cạnh. Các cạnh dẫn từ đỉnh đến nó được gọi là các vòng lặp và được thêm vào cuối ma trận. Trong các cột tương ứng với các vòng lặp, chỉ có một đơn vị, không giống như các cạnh khác.

Bây giờ vẽ một biểu đồ. Sắp xếp các đỉnh trên giấy tùy ý và kết nối chúng với các cạnh bằng các bảng được xây dựng. Các đỉnh không được kết nối bởi các cạnh được gọi là cô lập.