Grafik köşeler ve kenarlardan oluşur. Köşeler, belirli bir özelliğe göre kenarlarla bağlanır - kenar kümesini tanımlayan geliş ilişkisi. Bu durumda, döngüler ve izole köşeler oluşabilir.
Talimatlar
Aşama 1
Grafiğin kenar kümesi ve bir köşeden diğerine kenar çizmenin mümkün olduğu ilişki verilsin. Örnek olarak, {1, 2, 3, 4, 5, 6, 7, 8} köşe kümesi, iki x ve y köşesi x + y <8 oranındadır.
Adım 2
Bir köşe komşuluk matrisi oluşturun. Bunu yapmak için kare bir tablo oluşturun, tablodaki satır ve sütun sayısı köşe sayısıyla çakışıyor. Ardından, i ve j köşeleri verilen oranı sağlıyorsa, i. satır ve j. sütunun kesişimine 1 koyun. Karşılık gelen öğelerin oranı karşılanmıyorsa, i. satır ve j. sütunun kesişimine 0 koyun.
Örneğimizde, ilk satır aşağıdaki gibi doldurulur:
1 + 1 <8, yani 1. satır ve 1. sütunun kesişiminde 1 var
1 + 2 <8, tekrar 1
1 + 3 <8, tekrar 1
1 + 7 <8, yanlış eşitsizlik, yani tablonun bu elemanı 0 olacak
1 + 8 <8, tekrar 0
Aşama 3
Kenarların sayısını bulmak için, kenarları çoğaltmadan komşuluk matrisindekilerin sayısını sayın.
Örnekte simetrik bir matris elde edildi, bu nedenle önce matrisin ana köşegeninin üzerindekileri (mavi ile işaretli) ve sonra ana köşegen üzerindekileri (kırmızı ile işaretli) saydık. Toplam kaburga sayısı 12'dir.
4. Adım
Olaylardan (kenarlardan) oluşan bir matris oluşturun. Bunu yapmak için bir tablo çizin, içindeki satır sayısı grafikteki köşe sayısına eşittir ve sütun sayısı kenar sayısına eşittir. Bir kenarla bağlanacak olan bu hatlara birimleri koyun. Köşeden ona giden kenarlara döngü denir ve matrisin sonuna eklenir. Döngülere karşılık gelen sütunlarda, diğer kenarların aksine sadece bir birim vardır.
Adım 5
Şimdi bir grafik çizin. Köşeleri kağıdın üzerine herhangi bir şekilde yerleştirin ve oluşturulan tabloları kullanarak bunları kenarlarla birleştirin. Kenarlarla bağlanmayan köşelere izole denir.
