Boşluk (grafik teorisi) - Nullity (graph theory)

İptal a grafik olarak matematiksel konusu grafik teorisi ya iki ilgisiz sayılar anlamına gelebilir. Grafiğin n köşesi ve m kenarı varsa, o zaman:

Olarak matris teori grafikler, grafik iptal ve iptal olan komşuluk matrisi A grafiği. Ve iptal A ile verilmektedir n - r r olan seviye bitişiklik matrisi. Bu sıfırlık , bitişik matris spektrumundaki özdeğer 0'ın çokluğuna eşittir . Bkz. Cvetkovič ve Gutman (1972), Cheng ve Liu (2007) ve Gutman ve Borovićanin (2011).
Gelen matroid teorinin grafiğinin iptal yönlendirilmiş iptal olan sıklığı matris M grafiği ile ilişkili. Ve iptal M ile verilmektedir m - n + c , c grafik ve bileşenlerinin sayısı , n - C olan seviye yönlendirilmiş sıklığı matris. Bu isim nadiren kullanılır; sayı daha yaygın olarak grafiğin döngü sırası , döngüsel sayısı veya devre sırası olarak bilinir . Grafiğin ortak grafik matroidinin rankına eşittir . Ayrıca , grafiğin Laplacian matrisinin boşluğuna eşittir, L = D - A olarak tanımlanır; burada D , köşe derecelerinin köşegen matrisidir; Laplacian boşluğu döngü derecesine eşittir çünkü L = M M ^T ( M çarpı kendi devriği).

Ayrıca bakınız

Bo Cheng ve Bolian Liu (2007), Grafiklerin boşluğu üzerine. Elektronik Doğrusal Cebir Dergisi , cilt. 16, 5. madde, sayfa 60–67.
Dragoš M. Cvetkovič ve Ivan M. Gutman (1972), İki parçalı bir grafiğin spektrumunda sıfır sayısının cebirsel çokluğu. Matematički Vesnik (Beograd) , cilt. 9, sayfa 141–150.
Ivan Gutman ve Bojana Borovićanin (2011), Grafiklerin Hükümsüzlüğü: güncellenmiş bir anket. Zbornik Radova (Beograd) , cilt. 14, hayır. 22 (Grafik Spektrumlarının Uygulamaları Üzerine Seçilmiş Konular), s. 137–154.