İnsidans matrisi - Incidence matrix

Gelen matematik bir insidans matris a, mantıksal matris gösterir nesneleri iki sınıf arasındaki ilişki, genellikle adlandırılan sıklığı ilişkisi . Birinci sınıf X ve ikincisi Y ise, matrisin her X öğesi için bir satırı ve Y'nin her öğesi için bir sütunu vardır . x ve y ilişkiliyse ( bu bağlamda olay denir ) satır x ve y sütunundaki giriş 1, değilse 0'dır. Varyasyonlar var; aşağıya bakınız.

Grafik teorisi

İnsidans matrisi, çizge teorisinde yaygın bir çizge gösterimidir . Köşe-köşe çiftlerinin ilişkisini kodlayan Bitişiklik matrisinden farklıdır .

Yönlendirilmemiş ve yönlendirilmiş grafikler

Yönsüz bir grafik.

Grafik teorisinde, yönlendirilmemiş bir grafiğin iki tür geliş matrisi vardır: yönlendirilmemiş ve yönlendirilmiş.

Yönlendirilmemiş insidansı matrisi (ya da sadece matris oranı , bir yönsüz grafiğin) a, matris B burada, n, ve m, sayısıdır köşeler ve kenarlar gibi, sırasıyla, o tepe olmadığını ve kenar düşürülür ve 0 olacaktır.

Örneğin, sağda gösterilen yönsüz grafiğin geliş matrisi, 4 satır (dört köşeye, 1–4'e karşılık gelir) ve 4 sütundan (dört kenara karşılık gelir) oluşan bir matristir :

e 1 e 2 e 3 e 4
1 1 1 1 0
2 1 0 0 0
3 0 1 0 1
4 0 0 1 1
=

Geliş matrisine bakarsak, her sütunun toplamının 2'ye eşit olduğunu görürüz. Bunun nedeni, her kenarın her bir uca bağlı bir tepe noktasının olmasıdır.

Sıklığı matris a yöneliktir grafik a, matris B , n ve m, öyle ki köşe ve kenarlar sayısı sırasıyla, kenar ise yaprak köşe , 1 bu köşe girerse , aksi ve 0 (birçok yazar tersi işaret kuralını kullanın).

Yönlendirilmiş sıklığı matrisi bir yönsüz grafik herhangi birine göre, yönlendirilmiş grafikler anlamında, insidans matrisi yönlendirme grafik. Kendisine, kenar sütununda e , orada aralıksız bir 1, bir tepe noktası karşı gelen e ve bir -1 aralıksız diğer tepe karşılık gelen e ve diğer tüm satır 0 yönlendirilmiş sıklığı matris olduğu bilgisi sütunlardan herhangi birinin olumsuzlamasına kadar benzersizdir , çünkü bir sütunun girişlerini olumsuzlamak, bir kenarın yönünü tersine çevirmeye karşılık gelir.

Bir grafik yönlendirilmemiş sıklığı matris G ile ilgilidir bitişiklik matrisi olan bir çizgi grafiğidir L ( G aşağıdaki teoremi):

burada bir ( L ( G )) hattı grafiğin komşuluk matrisi olan G , B ( G ) sıklığı matrisidir ve bir m olan birim matris boyutu arasında m .

Ayrık Laplacian (veya Kirchhoff matrisi), B ( G ) odaklı insidans matrisinden formülle elde edilir.

Bir grafiğin integral döngü uzayı , tamsayılar veya gerçek ya da karmaşık sayılar üzerinde bir matris olarak görülen, yönlendirilmiş geliş matrisinin sıfır uzayına eşittir . İkili döngü alanı, iki elemanlı alan üzerinde bir matris olarak görülen, yönlendirilmiş veya yönlendirilmemiş geliş matrisinin sıfır uzayıdır .

İmzalı ve çift yönlü grafikler

Bir sıklığı matrisi imzalı grafik tabanlı sıklığı matrisinin bir genellemedir. Verilen işaretli grafiği yönlendiren herhangi bir çift ​​yönlü grafiğin görülme sıklığı matrisidir . Pozitif kenarın sütunu, sıradan (işaretsiz) bir grafikteki bir kenar gibi, bir uç noktaya karşılık gelen satırda 1'e ve diğer uç noktaya karşılık gelen satırda -1'e sahiptir. Negatif kenarın sütununda her iki satırda da 1 veya -1 bulunur. Çizgi grafiği ve Kirchhoff matrisi özellikleri, işaretli grafiklere genellenir.

çoklu grafikler

İnsidans matrisinin tanımları, döngüleri ve çoklu kenarları olan grafikler için geçerlidir . Grafik imzalanmadıkça ve döngü negatif olmadıkça, bir döngüye karşılık gelen yönlendirilmiş bir geliş matrisinin sütununun tamamı sıfırdır; o zaman sütun, olay köşesinin satırındaki ±2 dışında tamamen sıfırdır.

Ağırlıklı grafikler

Ağırlıklı yönsüz grafik

Ağırlıklı bir grafik, 1 yerine kenarın ağırlığı kullanılarak temsil edilebilir. Örneğin, sağdaki grafiğin insidans matrisi:

e 1 e 2 e 3 e 4
1 2 1 5 0
2 2 0 0 0
3 0 1 0 6
4 0 0 5 6
=

hipergraflar

Sıradan grafiklerin kenarları yalnızca iki köşeye (her bir uçta bir tane) sahip olabileceğinden, grafikler için bir insidans matrisinin sütununda yalnızca iki sıfır olmayan giriş olabilir. Buna karşılık, bir hipergrafın bir kenara atanmış birden çok köşesi olabilir; bu nedenle, negatif olmayan tamsayılardan oluşan genel bir matris, bir hipergrafı tanımlar.

İnsidans yapıları

Sıklığı matrisi bir bölgesinin sıklığı yapısı C a, p x q matris B (veya devrik), p ve q, sayısıdır noktaları ve çizgileri sırasıyla bu şekilde B i , j = 1 ise nokta s i ve hat L j olaydır ve aksi halde 0'dır. Bu durumda, insidans matris, a, biadjacency matris arasında Levi grafik yapısı. Her Levi grafiği için bir hipergraf olduğu ve bunun tersi olduğu için, bir insidans yapısının insidans matrisi bir hipergrafı tanımlar.

sonlu geometriler

Önemli bir örnek sonlu bir geometridir . Örneğin, sonlu bir düzlemde X noktalar kümesidir ve Y doğrular kümesidir. Daha yüksek boyutlu sonlu bir geometride, X noktalar kümesi olabilir ve Y , tüm uzayın boyutundan (hiper düzlemler) bir küçük boyutlu alt uzaylar kümesi olabilir; veya daha genel olarak, X , bir d boyutunun tüm alt uzaylarının kümesi olabilir ve Y , insidansı kapsama olarak tanımlanan başka bir e boyutunun tüm alt uzaylarının kümesi olabilir .

politoplar

Benzer bir şekilde, boyutları bir politopta farklı olan hücreler arasındaki ilişki, bir insidans matrisi ile temsil edilebilir.

Blok tasarımları

Başka bir örnek, bir blok tasarımıdır . Burada X , sonlu bir "nokta" kümesidir ve Y , tasarımın türüne bağlı kurallara tabi olan "bloklar" olarak adlandırılan X'in alt kümelerinin bir sınıfıdır . İnsidans matrisi, blok tasarımları teorisinde önemli bir araçtır. Örneğin , dengeli eksik 2 tasarımların (BIBD'ler) temel bir teoremi olan Fisher eşitsizliğinin blok sayısının en az nokta sayısı olduğunu kanıtlamak için kullanılabilir . Kümelerinin bir sistem olarak blok göz önüne alındığında, sürekli sıklığı matris sayısı farklı temsilcilerin sistemleri (SDR).

Referanslar

daha fazla okuma

  • Diestel, Reinhard (2005), Grafik Teorisi , Matematikte Lisansüstü Metinler , 173 (3. baskı), Springer-Verlag, ISBN 3-540-26183-4
  • Jonathan L Gross, Jay Yellen, Grafik Teorisi ve uygulamaları , ikinci baskı, 2006 (s 97, Yönsüz grafikler için İnsidans Matrisleri; s 98, digraflar için insidans matrisleri)

Dış bağlantılar