Grafik terdiri dari simpul dan tepi. Verteks dihubungkan oleh tepi sesuai dengan properti tertentu - hubungan kejadian, yang mendefinisikan himpunan tepi. Dalam hal ini, loop dan simpul yang terisolasi dapat terbentuk.
Instruksi manual
1
Biarkan satu set tepi grafik diberikan dan relasi yang diberikan dimana seseorang dapat menggambar tepi dari satu titik ke titik lainnya. Sebagai contoh, himpunan simpul {1, 2, 3, 4, 5, 6, 7, 8}, dua simpul x dan y berada dalam rasio x + y <8.
2
Membangun matriks adjacency vertex. Untuk melakukan ini, buat tabel persegi, jumlah baris dan kolom dalam tabel cocok dengan jumlah simpul. Kemudian letakkan 1 di persimpangan baris ke-i dan kolom ke-j, jika simpul i dan j memenuhi rasio yang diberikan. Letakkan 0 di persimpangan baris ke-i dan kolom ke-j, jika rasio untuk elemen yang sesuai tidak terpenuhi.
Dalam contoh kita, baris pertama diisi sebagai berikut:
1 + 1 <8, jadi di persimpangan baris 1 dan kolom 1 adalah 1
1 + 2 <8, lagi 1
1 + 3 <8, lagi 1
…
1 + 7 <8, ketimpangan salah, maka elemen tabel ini akan menjadi 0
1 + 8 <8, lagi 0
3
Untuk mengetahui jumlah tepi, hitung jumlah unit dalam matriks adjacency, sementara tidak merobek tepi.
Dalam contoh, matriks simetris diperoleh, oleh karena itu, pertama unit dihitung di atas diagonal utama dari matriks (ditandai dengan warna biru), dan kemudian unit pada diagonal utama (ditandai dengan warna merah). Jumlah tulang rusuk adalah 12.
4
Bangun matriks insiden (tepian). Untuk melakukan ini, gambarkan sebuah tabel, jumlah baris di dalamnya sama dengan jumlah simpul grafik, dan jumlah kolom sama dengan jumlah tepi. Letakkan unit di garis yang akan dihubungkan oleh tepi. Tepi yang mengarah dari atas disebut loop dan ditambahkan ke ujung matriks. Di kolom yang sesuai dengan loop, hanya ada satu unit, tidak seperti tepi lainnya.
5
Sekarang gambarlah sebuah grafik. Atur simpul di atas kertas secara sewenang-wenang dan hubungkan dengan tepi menggunakan tabel yang dibuat. Vertikal yang tidak terhubung dengan tepi disebut terisolasi.
Perhatikan
Gambar tersebut menunjukkan tulang rusuk untuk kejelasan. Biasanya, berat iga ditulis di atas iga.
