Komşuluk matrisi - Adjacency matrix

Olarak grafik teorisi ve bilgisayar biliminin , bir komşuluk matrisi a, kare matris sonlu temsil etmek için kullanılan bir grafik . Matris elemanları çiftlerinin olmadığını göstermek köşe olan bitişik grafikte ya da değil.

Sonlu basit grafiğin özel durumunda , komşuluk matrisi, köşegeninde sıfır olan bir (0,1) matrisidir . Grafik yönsüzse (yani tüm kenarları çift ​​yönlüyse), bitişiklik matrisi simetriktir . Bir grafik ile onun komşuluk matrisinin özdeğerleri ve özvektörleri arasındaki ilişki , spektral çizge teorisinde incelenir .

Bir grafik komşuluk matrisi olarak ayırt edilmelidir sıklığı matrisi , öğelerinin tepe kenar çifti olup olmadığını göstermektedir, farklı bir matris gösterimi olay ya da değil, ve derecesi matris hakkında bilgi içerir, derece Tepe noktalarının.

Tanım

Tepe grubu ile basit grafik için U = { u ₁ , ..., u _{, n} }, komşuluk matrisi bir kare , n x n matrisini bir onun elemanı, örneğin bir _ij tepe arasında bir kenar olduğunda biri u _ı vertex u _j , ve kenar olmadığında sıfır. Matrisin köşegen elemanlarının tümü sıfırdır, çünkü basit grafiklerde bir tepe noktasından kendisine ( döngüler ) kenarlara izin verilmez. Cebirsel çizge teorisinde bazen sıfırdan farklı öğeleri cebirsel değişkenlerle değiştirmek de yararlıdır . Aynı kavram , karşılık gelen matris elemanında her iki köşe arasındaki kenar sayısını depolayarak ve sıfır olmayan diyagonal elemanlara izin vererek döngülü grafiklere ve çoklu grafiklere genişletilebilir . Döngüler, tutarlı bir kural izlendiği sürece, bir kez (tek bir kenar olarak) veya iki kez (iki köşe kenarı olayı olarak) sayılabilir. Yönlendirilmemiş grafikler genellikle sayma döngülerinin ikinci kuralını iki kez kullanırken, yönlendirilmiş grafikler tipik olarak önceki kuralı kullanır.

İki parçalı bir grafiğin

Komşuluk matrisi bir a bipartit grafik , iki parça vardır r ve s köşe şeklinde yazılabilir

${\displaystyle A={\başlangıç{pmatrix}0_{r,r}&B\\B^{\mathsf {T}}&0_{s,s}\end{pmatrix}},}$

burada B bir r × s matrisidir ve 0 _{r , r} ve 0 _{s , s} r × r ve s × s sıfır matrislerini temsil eder . Bu durumda, daha küçük olan B matrisi grafiği benzersiz bir şekilde temsil eder ve A'nın kalan kısımları fazlalık olarak atılabilir. B bazen çift ​​bitişiklik matrisi olarak adlandırılır .

Biçimsel olarak, izin G = ( U , V , E ) bir olduğu bipartit grafik parçaları ile U = { u ₁ , ..., u _r } V = { v ₁ , ..., v _s } ve kenarları E . Biadjacency matrisi r × s 0–1 B matrisidir ve burada b _{ben , j} = 1 ve ancak ( u _ben , v _j ) ∈ E ise .

Eğer G bir bipartit olan ufak matbaa veya ağırlıklı grafik , daha sonra elemanlar b _{i, j,} köşe ya da kenar ağırlığı arasındaki kenar sayısı olarak alınır ( u _ı , v _j ) , sırasıyla.

Varyasyonlar

Basit bir grafiğin bir ( a , b , c ) - komşuluk matrisi A'nın köşegeninde A _{i , j} = a if ( i , j ) bir kenar, değilse b ve köşegende c vardır . Seidel komşuluk matrisi a, (1, 1, 0) -adjacency matrisi. Bu matris, güçlü düzenli grafikler ve iki-grafiklerin incelenmesinde kullanılır .

Mesafe matris pozisyonda yer alır ( i , j ) uçları arasında bir mesafe v _i ve h _j . Mesafe, köşeleri birleştiren en kısa yolun uzunluğudur. Kenar uzunlukları açıkça belirtilmedikçe, bir yolun uzunluğu, içindeki kenarların sayısıdır. Mesafe matrisi, komşuluk matrisinin yüksek gücüne benzer, ancak yalnızca iki köşenin bağlı olup olmadığını söylemek yerine (yani, boole değerlerini içeren bağlantı matrisi ), aralarındaki tam mesafeyi verir.

Örnekler

Yönsüz grafikler

Burada izlenen kural (yönsüz grafikler için), her kenarın matristeki uygun hücreye 1 eklemesi ve her döngünün 2 eklemesidir. bitişiklik matrisindeki ilgili satır veya sütun.

etiketli grafik	komşuluk matrisi
	${\displaystyle {\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0\end{pmatrix}$ Koordinatlar 1–6'dır.
Nauru grafiği	Koordinatlar 0–23'tür. Beyaz alanlar sıfır, renkli alanlar birdir.

Yönlendirilmiş grafikler

Yönlendirilmiş bir grafiğin komşuluk matrisi asimetrik olabilir. Yönlendirilmiş bir grafiğin komşuluk matrisi şu şekilde tanımlanabilir:

1. sıfır olmayan bir eleman bir _ij bir kenarı gösterir i için j veya
2. Bu bir avantaj gösterir j için i .

İlk tanım, grafik teorisinde ve sosyal ağ analizinde (örn. sosyoloji, siyaset bilimi, ekonomi, psikoloji) yaygın olarak kullanılır. İkincisi, A'nın bazen grafiklerde doğrusal dinamikleri tanımlamak için kullanıldığı diğer uygulamalı bilimlerde (örneğin dinamik sistemler, fizik, ağ bilimi) daha yaygındır .

İlk tanımı kullanarak, bir tepe noktasının dereceleri , karşılık gelen sütunun girişlerini toplayarak ve tepe noktasının dış derecesi karşılık gelen satırın girişlerini toplayarak hesaplanabilir. İkinci tanımı kullanırken, bir tepe noktasının derecesi karşılık gelen satır toplamı tarafından verilir ve dış derece, karşılık gelen sütun toplamı tarafından verilir.

etiketli grafik	komşuluk matrisi
Yönlendirilmiş Cayley grafik arasında S 4	Koordinatlar 0–23'tür. Grafik yönlendirildiği için, matris mutlaka simetrik değildir .

önemsiz grafikler

Tam bir grafiğin komşuluk matrisi , yalnızca sıfırların olduğu köşegen boyunca olanlar hariç, hepsini içerir. Boş bir grafiğin komşuluk matrisi bir sıfır matrisidir .

Özellikler

spektrum

Yönlendirilmemiş basit bir grafiğin komşuluk matrisi simetriktir ve bu nedenle tam bir gerçek özdeğerler kümesine ve bir ortogonal özvektör tabanına sahiptir. Bir grafiğin özdeğer kümesi, grafiğin spektrumudur . Özdeğerleri şu şekilde belirtmek yaygındır:${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}$

En büyük özdeğer , yukarıda maksimum derece ile sınırlandırılır. Bu, Perron-Frobenius teoreminin sonucu olarak görülebilir , ancak kolayca kanıtlanabilir. Let h bir özvektör bağlantılı olabilir ve x ki burada bileşen v maksimum mutlak değere sahiptir. Genelliği kaybetmeden v _x'in pozitif olduğunu varsayın çünkü aksi takdirde sadece , ile ilişkili özvektörü alırsınız . Sonra ${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{1}}$${\görüntüleme stili -v}$${\displaystyle \lambda _{1}}$

${\displaystyle \lambda _{1}v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{ y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x).}$

İçin d -Normal grafikler, d birinci özdeğeridir A vektörü, v = (1, ..., 1) (bunun bir özdeğer olup olmadığının kontrol edilmesi kolay olan ve bunun, bağımlı yukarıdaki maksimumdur). Bu özdeğerin çokluğu, özellikle bağlantılı grafikler için G'nin bağlı bileşenlerinin sayısıdır . Her özdeğer için olduğu gösterilebilir , zıt da bir özdeğeridir A ise G, a, bipartit grafiktir . Özellikle - d , iki parçalı grafiklerin bir özdeğeridir. ${\displaystyle \lambda _{1}>\lambda _{2}}$${\displaystyle \lambda _{i}}$${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$

Fark olarak adlandırılır spektral aralık ve ilgilidir genişleme bölgesinin G . ile gösterilen spektral yarıçapı tanıtmak da yararlıdır . Bu sayı ile sınırlıdır . Bu sınır, birçok alanda uygulamaları olan Ramanujan grafiklerinde sıkıdır . ${\displaystyle \lambda _{1}-\lambda _{2}}$${\görüntüleme stili A}$${\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\sağ|<d}|\lambda _{i}|}$${\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}$

İzomorfizm ve değişmezler

A ₁ ve A ₂ bitişik matrisleri ile G ₁ ve G ₂ yönlendirilmiş veya yönlendirilmemiş iki grafiğin verildiğini varsayalım . G ₁ ve G ₂ , ancak ve ancak, öyle bir permütasyon matrisi P varsa izomorfiktir .

${\displaystyle PA_{1}P^{-1}=A_{2}.}$

Özel olarak, bir ₁ ve A ₂ olan benzer ve bu nedenle, aynı sahip en az bir polinom , karakteristik polinom , öz , belirleyici ve iz . Bu nedenle bunlar, grafiklerin izomorfizm değişmezleri olarak hizmet edebilir. Bununla birlikte, iki grafik aynı özdeğer kümesine sahip olabilir ancak izomorfik olmayabilir. Bu tür lineer operatörlerin izospektral olduğu söylenir .

matris güçleri

Eğer bir yönlendirilmiş ya da yönlendirilmemiş grafiğin komşuluk matrisi olan G , daha sonra matris bir ^N (yani, bir matris çarpımı arasında N kopya A ) ilginç bir yorumu vardır: elemanı ( i , j ) sayısını (yöneliktir verir ya da yönsüz) yürür uzunluğunun n tepe gelen i tepe için j . Eğer , n bazıları için bu tür küçük pozitif bir tamsayı olduğu i , j , elemanın ( i , j ) bir A ^{, n} , o zaman pozitif bir N tepe arasındaki mesafedir i ve tepe j . Bu, bir yönsüz grafikte üçgenler sayısı, bu, örneğin, anlaşılacağı G, tam olarak iz bir A ³ komşuluk matrisi grafiği olup olmadığını belirlemek için kullanılabilir 6'ya bölünerek bağlı .

Veri yapıları

Bitişik matris , grafikleri işlemek için bilgisayar programlarında grafiklerin temsili için bir veri yapısı olarak kullanılabilir . Bu uygulama için de kullanılan ana alternatif veri yapısı bitişiklik listesidir .

Komşuluk matrisindeki her giriş yalnızca bir bit gerektirdiğinden, yalnızca | V | ² /8 byte yaklaşık (dolu üçgen biçimi kullanarak, sadece matrisin alt üçgen kısmını depolayarak) bir çizge temsil ya da | V | ² /16 bir yönsüz grafiği temsil etmek bayt. Biraz daha özlü temsiller mümkün olsa da, bu yöntem, tüm n- köşe grafiklerini temsil etmek için gereken minimum bit sayısı için bilgi teorik alt sınırına yaklaşır. Grafikleri metin dosyalarında saklamak için, örneğin bir Base64 temsili kullanarak, tüm baytların metin karakterleri olmasını sağlamak için bayt başına daha az bit kullanılabilir . Boş alandan kaçınmanın yanı sıra, bu kompaktlık referans yerini teşvik eder . Bununla birlikte, büyük bir seyrek grafik için , bitişik listeler daha az depolama alanı gerektirir, çünkü mevcut olmayan kenarları temsil etmek için herhangi bir alanı boşa harcamazlar .

Alternatif bir komşuluk matrisi biçimi (ancak daha büyük miktarda alan gerektirir), matrisin her bir öğesindeki sayıları, kenar nesnelerine yönelik işaretçiler (kenarlar mevcut olduğunda) veya boş işaretçiler (kenar olmadığında) ile değiştirir. Kenar ağırlıklarını doğrudan bir bitişiklik matrisinin elemanlarında saklamak da mümkündür .

Alan değiş tokuşunun yanı sıra, farklı veri yapıları da farklı işlemleri kolaylaştırır. Bir komşuluk listesinde belirli bir köşeye bitişik tüm köşeleri bulmak, listeyi okumak kadar basittir ve komşu sayısıyla orantılı olarak zaman alır. Bir bitişiklik matrisi ile, bunun yerine tüm bir satırın taranması gerekir; bu, tüm grafikteki köşe sayısıyla orantılı olarak daha fazla zaman alır. Öte yandan, verilen iki köşe arasında bir kenar olup olmadığının test edilmesi, bir bitişiklik matrisi ile bir kerede belirlenebilirken, bitişiklik listesi ile iki köşenin minimum derecesi ile orantılı bir zaman gerektirir.

Ayrıca bakınız

• Laplace matrisi
• Kendi kendine benzerlik matrisi

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Komşuluk matrisi" . Matematik Dünyası .
• Fluffschack — bitişik matrisler ve grafikler arasındaki ilişkiyi gösteren eğitici bir Java web başlangıç ​​oyunu.
• Açık Veri Yapıları - Bölüm 12.1 - BitişikMatris: Bir Grafiğin Bir Matris Tarafından Temsil Edilmesi , Pat Morin
• Kafe matematiği : Grafiklerin Komşuluk Matrisleri  : Komşuluk matrislerinin hesaplama üreten yürüyüş serilerine uygulanması.