Grafik terdiri daripada bucu dan tepi. Bucu dihubungkan oleh tepi mengikut sifat tertentu - hubungan kejadian, yang menentukan set tepi. Dalam kes ini, gelung dan bucu terpencil dapat terbentuk.
Arahan
Langkah 1
Biarkan sekumpulan tepi grafik diberikan dan hubungan yang memungkinkan untuk menarik tepi dari satu bucu ke bucu yang lain diberikan. Sebagai contoh, kumpulan bucu {1, 2, 3, 4, 5, 6, 7, 8}, dua bucu x dan y berada dalam nisbah x + y <8.
Langkah 2
Bina matriks penekanan bucu. Untuk melakukan ini, bina jadual persegi, bilangan baris dan lajur dalam jadual bertepatan dengan bilangan bucu. Kemudian letakkan 1 di persimpangan baris i-th dan lajur ke-j jika bucu i dan j memenuhi nisbah yang diberikan. Letakkan 0 di persimpangan baris i-th dan lajur ke-j jika nisbah bagi elemen yang sesuai tidak dipenuhi.
Dalam contoh kami, baris pertama diisi seperti berikut:
1 + 1 <8, jadi terdapat 1 di persimpangan baris pertama dan lajur pertama
1 + 2 <8, sekali lagi 1
1 + 3 <8, sekali lagi 1
1 + 7 <8, ketaksamaan yang tidak betul, jadi elemen jadual ini akan menjadi 0
1 + 8 <8, sekali lagi 0
Langkah 3
Untuk mengetahui bilangan tepi, hitung bilangan yang berada dalam matriks adjacency tanpa menduplikasi tepi.
Sebagai contoh, matriks simetri diperoleh, jadi kami menghitung pertama yang berada di atas pepenjuru utama matriks (ditandakan dengan warna biru), dan kemudian yang berada di pepenjuru utama (ditandakan dengan warna merah). Jumlah tulang rusuk adalah 12.
Langkah 4
Membina matriks kejadian (tepi). Untuk melakukan ini, lukis jadual, jumlah baris di dalamnya sama dengan bilangan bucu dalam grafik, dan bilangan lajur sama dengan bilangan tepi. Letakkan unit pada garis yang akan dihubungkan dengan tepi. Tepi yang mengarah dari bucu ke arah itu disebut gelung dan ditambahkan ke hujung matriks. Di lajur yang sesuai dengan gelung, hanya ada satu unit, berbeza dengan tepi yang lain.
Langkah 5
Sekarang lukiskan graf. Letakkan bucu di atas kertas dengan cara apa pun dan sambungkannya dengan tepi menggunakan jadual yang dibina. Bucu yang tidak dihubungkan oleh tepi disebut terpencil.
