Đồ thị bao gồm các đỉnh và các cạnh. Các đỉnh được nối với nhau bởi các cạnh theo một thuộc tính nhất định - 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 biệt lập có thể hình thành.
Hướng dẫn
Bước 1
Cho tập hợp các cạnh của đồ thị đã cho và cho trước mối quan hệ mà nó có thể vẽ một cạnh từ đỉnh này sang đỉnh khác. Ví dụ, tập các đỉnh {1, 2, 3, 4, 5, 6, 7, 8}, hai đỉnh x và y theo tỷ lệ x + y <8.
Bước 2
Xây dựng ma trận kề đỉnh. Để làm điều này, hãy xây dựng một bảng vuông, số hàng và cột trong bảng trùng với số đỉ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 thứ i và j thỏa mãn tỷ lệ đã cho. Đặt số 0 tại giao điểm của hàng thứ i và cột thứ j nếu tỷ lệ của các phần tử tương ứng không được đáp ứng.
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 có 1 tại giao điểm của hàng thứ nhất và cột thứ nhất
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, vì vậy phần tử này của bảng sẽ là 0
1 + 8 <8, lại là 0
Bước 3
Để tìm ra số cạnh, hãy đếm số cạnh trong ma trận kề mà không cần nhân đôi các cạnh.
Trong ví dụ, một ma trận đối xứng đã thu được, vì vậy chúng tôi đếm đầu tiên những cái nằm trên đường chéo chính của ma trận (được đánh dấu màu xanh lam), sau đó là những cái nằm trên đường chéo chính (được đánh dấu màu đỏ). Tổng số xương sườn là 12 chiếc.
Bước 4
Xây dựng 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ố hàng trong đó bằng số đỉnh trong đồ thị và số cột bằng số cạnh. Đặt các đơn vị trên những đường sẽ được nối với nhau bằng một cạnh. Các cạnh dẫn từ đỉnh đến nó được gọi là 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ị, ngược lại với các cạnh còn lại.
Bước 5
Bây giờ hãy vẽ một đồ thị. Đặt các đỉnh trên giấy theo bất kỳ cách nào và nối chúng với các cạnh bằng cách sử dụng các bảng đã dựng. Các đỉnh không được nối với nhau bằng các cạnh được gọi là cô lập.
