Kenar alanı - Edge space

Olarak matematiksel bir disiplin grafik teorisi , kenar alanı ve tepe alanı , bir ait yönsüz grafik olan vektör uzayı açısından tanımlanan kenar ve köşe sırasıyla kümeleri. Bu vektör uzayı mümkün tekniklerini kullanmak için yapmak lineer cebir grafik okuyan.

Tanım

Let sonlu yönsüz çizge. Tepe alanı arasında G üzerinden vektör alanıdır sonlu alan iki eleman arasında tüm fonksiyonları . Her eleman , doğal alt-kümesini karşılık gelen V kendi noktaların bir 1 atar. Ayrıca, her bir alt kümesi V benzersiz temsil edilmektedir karakteristik fonksiyonu ile. Kenar alanı olan serbest kenar kümesi tarafından oluşturulan -vector alanı E . Kenar alanı boyutu kenarlarının sayısı ise tepe alanı boyutu, böylece grafik köşe sayısıdır. ${\ Displaystyle G: = (V, E)}$ ${\ Displaystyle {\ mathcal {V}} (G)}$${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z} = \ 0,1 \ rbrace lbrace}$${\ Displaystyle V \ rightarrow \ mathbb {Z} / 2 \ mathbb {Z}}$${\ Displaystyle {\ mathcal {V}} (G)}$${\ Displaystyle {\ mathcal {V}} (G)}$ ${\ Displaystyle {\ mathcal {E}} (G)}$${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z}}$

Bu tanımlar daha açık hale getirilebilir. Örneğin aşağıdaki gibi sağlamak için, kenar alanı tanımlayabiliriz:

• Vektör alan elemanları alt kümeleridir bir dizi olarak, yani, bir güç grubu ve E${\ Displaystyle E}$${\ Displaystyle {\ mathcal {E}} (G)}$
• Vektör ek olarak tanımlanır simetrik fark :${\ Displaystyle P + Q: P = \ üçgen Q \ qquad P, Q \ içinde {\ mathcal {E}} (G)}$
• skaler çarpım ile tanımlanır:
  • ${\ Displaystyle 0 \ cdot P: = \ emptyset içinde qquad p \ \ {\ mathcal {E}} (G)}$
  • ${\ Displaystyle 1 \ cdot P: = p \ qquad P \ içinde {\ mathcal {E}} (G)}$

Singleton alt grupları E için bir temel oluşturur . ${\ Displaystyle {\ mathcal {E}} (G)}$

Bir de aklınıza gelebilecek gücü seti olarak V benzer vektör ek ve için tanımlandığı gibi skaler çarpma ile bir vektör uzaya yapılan . ${\ Displaystyle {\ mathcal {V}} (G)}$${\ Displaystyle {\ mathcal {E}} (G)}$

Özellikleri

Sıklığı matrisi , bir grafik için olası bir tanımlayan lineer transformasyon${\ Displaystyle H}$${\ Displaystyle G}$

${\ Displaystyle H: {\ mathcal için {E}} (G) \ {\ mathcal {V}} (G)}$

Kenar alanı arasındaki tepe alanı arasında . Sıklığı matrisi , lineer transformasyon olarak, iki, her kenar eşleştirir olay köşe. Let arasındaki kenar olabilir ve daha sonra ${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle vu}$${\ Displaystyle v}$${\ Displaystyle u}$

${\ Displaystyle H (VII), u + v =}$

Döngüsü alan ve kesme alanı olan lineer alt uzayları kenar alanı.

Referanslar

• Diestel Reinhard (2005), Grafik Teorisi (3 ed.), Springer , ISBN  3-540-26182-6 (Elektronik 3rd edition yazarın sitesinde serbestçe kullanılabilir).

Ayrıca bakınız

• döngüsü uzay
• kesim alanı