Təhlükəsiz Kilid Nümunəsində Yayılma Ağacları#6942
Smartfonlarda ekranın blokunu açmaq üçün naxış istifadə olunur. Bu naxış, 3×3 ölçülü bir şəbəkədə yerləşən 9 zirvədən ibarətdir. Bu məsələdə, şəbəkənin ölçüsünü 2×2 ilə m×m arasında dəyişməyə imkan verəcəyik və yalnız qonşu zirvələr arasında məhdud sayda əlaqələrə icazə veriləcək. Bu modifikasiya olunmuş şəbəkə qrafını G, zirvələr toplusunu V, və kənarların (əlaqələrin) toplusunu E adlandıraq. 2×2, 3×3 və 4×4 şəbəkə qraflarının nümunələri şəkillərdə göstərilmişdir. Künc zirvələri ən çox 3 əlaqəyə, mərkəzi zirvələr isə 8 əlaqəyə malikdir. Yalnız qonşu zirvələr arasında əlaqələrə icazə verilir.
Ostov ağacı, qrafın dövrə yaratmayan kənarları toplusu kimi müəyyən edilir və onun vasitəsilə istənilən iki zirvə arasında keçmək mümkündür. Ostov ağacı m^2 = n zirvələr və n – 1 kənara malikdir. Qrafda ostov ağacları müxtəlif növ və formalara malik ola bilər.
G qrafında ostov ağaclarının sayını hesablamaq üçün G zirvələrini v_1, ..., v_n etiketləri ilə işarələyək. T = [t_ij] ağacının n×n ölçülü matrisini aşağıdakı kimi təşkil edək.
Əgər i = j, onda t_ii G-də v_i ilə bitişik kənarların sayına bərabərdir.
Əgər i ≠ j, onda t_ij = 0 əgər G-də v_i və v_j arasında kənar yoxdursa.
Əgər i ≠ j, onda t_ij = -1 əgər G-də v_i və v_j arasında kənar varsa.
Onda G-də ostov ağaclarının sayı
cofactor of a_ij = (-1)^{i+j}M_ij
burada M_ij - T ağac matrisindən i sətirini və j sütununu çıxarmaqla əldə edilən (n-1)×(n-1) ölçülü matrisin determinantıdır. T matrisinin istənilən alqebraik əlavəsinin dəyəri eyni nəticəni verir.
Misal 1: 2×2 şəbəkə qrafı üçün T ağac matrisinin dəyəri
T ağacının alqebraik əlavəsini hesablayaq. Məsələn, 1 sətirini və 1 sütununu çıxardıqda, əldə edirik
Buna görə də ostov ağaclarının sayı 16-ya bərabərdir.
Misal 2: 3×3 şəbəkə qrafı üçün T ağac matrisinin görünüşü
T matrisinin istənilən alqebraik əlavəsinin dəyəri eynidir və ostov ağaclarının sayına bərabərdir.
İpucu: Determinantı hesablamaq üçün sətir üzərində elementar əməliyyatlardan istifadə edin:
Başlanğıc matrisini yuxarı üçbucaq formasına gətirmək lazımdır (əsas diaqonalın altındakı bütün elementlər sıfıra bərabərdir). Matrisini sətir-sətir elementar sətir əməliyyatları ilə dəyişdirin, nəticədə əsas diaqonalın altındakı bütün elementlər sıfır olacaq. Sonra əsas diaqonalın elementlərini bir-birinə vurun və determinantın dəyərini əldə edin.
Müəyyən edilmiş m×m ölçülü modifikasiya olunmuş şəbəkə qrafı üçün ostov ağaclarının sayını hesablayan proqram yazın.
Birinci sətir testlərin sayını n (1 ≤ n ≤ 5) ehtiva edir. Hər bir test bir tam ədəd m (2 ≤ m ≤ 6) - mxm ölçülü şəbəkə - qrafın ölçüsünü ehtiva edir.
Hər bir test üçün proqramınız verilmiş modifikasiya olunmuş şəbəkə qrafı üçün ostov ağaclarının sayını, yəni ostov ağaclarının neçə naxışının olduğunu çıxarmalıdır. Hər bir test üçün bir sətir çap edin.
Nümunə 1
Misalda yalnız bir test var (n = 1). Birinci test üçün m = 2 olduqda 16 müxtəlif ostov ağacı mövcuddur. Onların hamısı aşağıda göstərilmişdir. Proqramınız bütün şəkilləri çəkməyə ehtiyac yoxdur.
