Grafik köşelerden ve kenarlardan oluşur. Köşeler, kenarlar kümesini tanımlayan insidans ilişkisi olan belirli bir özelliğe göre kenarlarla bağlanır. Bu durumda, ilmekler ve izole köşeler oluşabilir.
Kullanım kılavuzu
1
Bir grafiğin kenarlarının bir kümesinin ve bir kenarın bir tepe noktasından diğerine bir kenar çizebileceği bir ilişkinin verilmesine izin verin. Örnek olarak, {1, 2, 3, 4, 5, 6, 7, 8} köşeleri, iki x ve y köşeleri x + y <8 oranındadır.
2
Bir tepe bitişiklik matrisi oluşturun. Bunu yapmak için, kare bir tablo oluşturun, tablodaki satır ve sütun sayısı köşelerin sayısıyla eşleşir. Daha sonra, eğer i ve j köşeleri verilen oranı karşılıyorsa, i-th satırının ve j-th sütununun kesişimine 1 koyun. Karşılık gelen öğelerin oranı karşılanmazsa, i-th satırının ve j-th sütununun kesişimine 0 koyun.
Örneğimizde, ilk satır aşağıdaki gibi doldurulmuştur:
1 + 1 <8, bu nedenle 1. sıranın ve 1. sütunun kesişiminde 1
1 + 2 <8, tekrar 1
1 + 3 <8, tekrar 1
…
1 + 7 <8, yanlış eşitsizlik, o zaman bu tablo öğesi 0 olur
1 + 8 <8, tekrar 0
3
Kenar sayısını bulmak için, kenarları yırtmazken bitişiklik matrisindeki birim sayısını sayın.
Örnekte simetrik bir matris elde edildi, bu nedenle önce birimler matrisin ana diyagonalinin üstünde (mavi ile işaretlenmiş) ve daha sonra ana diyagonaldeki (kırmızı ile işaretlenmiş) birimler hesaplandı. Toplam kaburga sayısı 12'dir.
4
Olaylar matrisi oluşturun (kenarlar). Bunu yapmak için bir tablo çizin, içindeki satır sayısı grafiğin köşe sayısına eşittir ve sütun sayısı kenar sayısına eşittir. Birimleri bir kenarla bağlanacak hatlara yerleştirin. Üstten gelen kenarlara döngüler denir ve matrisin sonuna eklenir. Döngülere karşılık gelen sütunlarda, diğer kenarlardan farklı olarak yalnızca bir birim vardır.
5
Şimdi bir grafik çizin. Kağıt üzerindeki köşeleri keyfi olarak düzenleyin ve oluşturulan tabloları kullanarak kenarlarla birleştirin. Kenarlarla bağlanmayan tepe noktalarına izole denir.
Dikkat et
Şekil, açıklık için kaburgaları göstermektedir. Genellikle, kaburga ağırlığı kaburga üzerine yazılır.
