Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 31

[30-32 soruları için açıklama]
Matrisler bilgisayar alanında çok fazla kullanılmaktadır. 3x2 bir matris \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix}\) şeklinde ifade edilebilir.
Verilen matrisin 1. satır-1. sütununda 1 değeri ve 3. satır-1. sütununda 5 değeri bulunmaktadır. Matrisleri bir tam sayı ile çarpmak istediğimizde tüm elemanları verilen tam sayı ile çarpmamız gerekmektedir. Bundan daha zor olan işlem ise verilen iki matrisi birbiriyle çarpmaktır. Bunun için bazı şartların uygun olması gerekmektedir. mx2 boyutlarında bir matris ancak 2xn boyutlarında bir matris ile çarpılabilir. Yani ilk matrisin sütun sayısı ile ikinci matrisin satır sayısının aynı olması gerekmektedir. Elde edilen matris de mxn boyutlarında olacaktır. Elimizde iki adet matris verilmiş olsun;
\[A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 4 & 6 \end{bmatrix} \text{ ve } B = \begin{bmatrix} 3 & 4 \\ 5 & 6 \end{bmatrix} \text{ bu durumda } A \times B = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ c_{31} & c_{32} \end{bmatrix} \text{ olacaktır}\]
A matrisinin ilk satırı B matrisinin ilk sütunundaki değerlerle sırayla çarpılıp \(c_{11}\) değeri (\(c_{11} = 1 * 3 + 2 * 5 = 13\)), A matrisinin ilk satırı B matrisinin ikinci sütunu ile çarpılıp \(c_{12}(c_{12} = 1 * 4 + 2 * 6 = 16)\) değeri elde edilecektir. Aynı şekilde A matrisinin ikinci satırı B matrisinin ilk sütunu ile çarpılıp \(c_{21}\) değeri, A matrisinin ikinci satırı B matrisinin ikinci sütunu ile çarpılıp \(C_{22}\) değeri elde edilecektir. Aynı işlem diğer satırlar için de tekrarlanmalıdır.

---

Bu konular üzerinde çalışan Samet çizgelerin komşuluk matrisi ile gösterilebildiğini fark etti. Her bir düğüm bir satır ve aynı zamanda her bir sütunu temsil ederse verilen bir çizgede hangi iki düğüm arasında bağlantı olduğunu kolayca tutabiliyorduk. Bu bilgiyi matris çarpımıyla birleştiren Samet, iki düğüm arasında iki adımda gidilebilecek yol sayısını bağlantı matrisinin karesini alarak bulabileceğini fark etti. Daha genel ifade edilecek olursa; verilen bir A matrisinde herhangi iki düğüm arasında n adımda gidilebilecek yol sayısı \(A^n\) işlemi ile hesaplanabilir olacaktır. Buradaki üs fonksiyonu matris çarpımını ifade etmektedir.
[GÖRSEL]
Verilen çizge için **2 adımda gidilebilecek yol** sayıları hakkında aşağıdakilerden hangisi doğrudur?

Şıklar:
A) A'dan B'ye gidilen yol sayısı D'den B'ye gidilen yol sayısından fazladır | B) B'den D'ye iki adımda gidilemez | C) D'den iki adımda hiçbir düğüme gidilemez | D) Ulaşılabilir düğüm sayısı en çok C düğümünden başlanarak elde edilebilir | E) En çok alternatif B'den A'ya gidilecek yol sayısındadır

Cevap: D Ulaşılabilir düğüm sayısı en çok C düğümünden başlanarak elde edilebilir

Çözüm:
Verilen şeklin matris gösterimi şu şekildedir: \(A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}\) 2 Adımda gidilebilecek yolların sayısını bulmak için AxA matris çarpımı uygulanmalıdır. Verilen işlem adımları uygulandığında elde edilecek sonuç
\(AxA = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}\) olacaktır. Bu durumda verilen seçenekler arasından doğru olan E şıkkı dolacaktır. Çünkü matrisin B-A değeri 2 olarak en büyük değere sahiptir.
Bir önceki soruda bulunan AxA matrisi A ile tekrar çarpılarak 3 adımda gidilebilen yol sayısı hesaplanmış
olacaktır. Verilen işlem adımları uygulandığında elde edilecek sonuç AxAxA =  \( \begin{bmatrix} 2 & 1 & 0 & 1 \\ 2 & 2 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix} \)  olacaktır. Bu
durumda verilen seçenekler arasından yanlış olan D seçeneğinde verilen bilgidir. C'den gidilebilecek yol sayısı toplamda 4 olmalıdır.