Graf terdiri dari simpul dan tepi. Simpul dihubungkan oleh tepi sesuai dengan properti tertentu - hubungan kejadian, yang mendefinisikan himpunan tepi. Dalam hal ini, loop dan simpul terisolasi dapat terbentuk.
instruksi
Langkah 1
Biarkan himpunan sisi dari grafik diberikan dan hubungan yang memungkinkan untuk menggambar sisi dari satu titik ke titik lainnya diberikan. Sebagai contoh, himpunan simpul {1, 2, 3, 4, 5, 6, 7, 8}, dua simpul x dan y memiliki perbandingan x + y <8.
Langkah 2
Bangun matriks ketetanggaan simpul. Untuk melakukan ini, buat tabel persegi, jumlah baris dan kolom dalam tabel bertepatan dengan jumlah simpul. Kemudian letakkan 1 pada perpotongan baris ke-i dan kolom ke-j jika simpul-simpul ke-i dan j memenuhi rasio yang diberikan. Letakkan 0 pada perpotongan baris ke-i dan kolom ke-j jika rasio elemen-elemen yang bersesuaian tidak terpenuhi.
Dalam contoh kita, baris pertama diisi sebagai berikut:
1 + 1 <8, jadi ada 1 di persimpangan baris ke-1 dan kolom ke-1
1 + 2 <8, lagi 1
1 + 3 <8, lagi 1
1 + 7 <8, pertidaksamaan salah, jadi elemen tabel ini adalah 0
1 + 8 <8, lagi 0
Langkah 3
Untuk mengetahui jumlah sisi, hitung jumlah sisi dalam matriks ketetanggaan tanpa menduplikasi sisi-sisinya.
Dalam contoh, matriks simetris diperoleh, jadi kami menghitung terlebih dahulu yang di atas diagonal utama matriks (ditandai dengan warna biru), dan kemudian yang di diagonal utama (ditandai dengan warna merah). Jumlah rusuk seluruhnya adalah 12.
Langkah 4
Membangun matriks insiden (tepi). Untuk melakukan ini, gambar tabel, jumlah baris di dalamnya sama dengan jumlah simpul dalam grafik, dan jumlah kolom sama dengan jumlah tepi. Letakkan unit pada garis-garis yang akan dihubungkan oleh tepi. Tepi yang mengarah dari simpul ke sana disebut loop dan ditambahkan ke ujung matriks. Di kolom yang sesuai dengan loop, hanya ada satu unit, berbeda dengan tepi lainnya.
Langkah 5
Sekarang gambarlah grafiknya. Tempatkan simpul di atas kertas dengan cara apa pun dan hubungkan dengan tepi menggunakan tabel yang dibuat. Simpul yang tidak dihubungkan oleh sisi disebut terisolasi.
