Mahalle (grafik teorisi) - Neighbourhood (graph theory) - Wikipedia

6 köşe ve 7 kenardan oluşan bir grafik
Matematikte mahallelerin diğer anlamları için bkz. Mahalle (matematik). Matematiksel olmayan mahalleler için bkz. Mahalle (belirsizliği giderme).

İçinde grafik teorisi, bir bitişik tepe bir tepe v içinde grafik bağlı bir tepe noktasıdır v tarafından kenar. Semt bir tepe noktası v bir grafikte G alt grafiği G indüklenmiş bitişik tüm köşeler tarafından vyani bitişik köşelerden oluşan grafik v ve bitişik köşeleri birleştiren tüm kenarlar v. Örneğin, sağdaki resimde, köşe 5'in komşusu 1, 2 ve 4 numaralı köşelerden ve 1 ve 2 numaralı köşeleri birleştiren kenarlardan oluşur.

Mahalle sık sık gösterilir NG(v) veya (grafik net olduğunda)N(v). Aynı komşuluk notasyonu, karşılık gelen indüklenmiş alt grafiklerden ziyade bitişik köşelerin setlerine atıfta bulunmak için de kullanılabilir. Yukarıda açıklanan mahalle içermez v kendisi ve daha spesifik olarak açık mahalle nın-nin v; bir mahalle tanımlamak da mümkündür. v kendisi dahil edilir, denir kapalı mahalle ve ile gösterilir NG[v]. Herhangi bir vasıf olmaksızın ifade edildiğinde mahallenin açık olduğu varsayılır.

Mahalleler, bilgisayar algoritmalarındaki grafikleri temsil etmek için kullanılabilir. bitişiklik listesi ve bitişik matris temsiller. Mahalleler de kullanılmaktadır. kümeleme katsayısı ortalamanın bir ölçüsü olan bir grafiğin yoğunluk mahallelerinden. Ek olarak, birçok önemli grafik sınıfı, mahallelerinin özellikleriyle veya mahalleleri birbiriyle ilişkilendiren simetrilerle tanımlanabilir.

Bir izole köşe bitişik köşeleri yoktur. derece Bir köşe noktası, bitişik köşelerin sayısına eşittir. Özel bir durum bir döngü bir tepe noktasını kendisine bağlayan; böyle bir kenar varsa, tepe kendi mahallesine aittir.

Grafiklerdeki yerel özellikler

İçinde oktahedron grafiği, herhangi bir tepe noktasının komşuluğu 4-döngü.

Tüm köşeler G mahalleleri var izomorf aynı grafiğe H, G olduğu söyleniyor yerel olarak Hve eğer tüm köşeler içindeyse G bazı grafik ailesine ait mahalleler var F, G olduğu söyleniyor yerel olarak F (Cehennem 1978, Sedláček 1983 ). Örneğin, oktahedron grafiği Şekilde gösterildiği gibi, her tepe noktasının bir komşuluk izomorfik döngü dört köşe olduğundan, sekiz yüzlü yerel olarakC4.

Örneğin:

Bir setin mahalle

Bir set için Bir köşelerin mahallesi Bir köşelerin mahallelerinin birleşimidir ve bu nedenle, en az bir üyesine bitişik tüm köşelerin kümesidir.Bir.

Bir set Bir bir grafikteki köşe noktalarının her köşe noktasının bir modül olduğu söylenir. Bir dışında aynı komşulara sahip Bir. Herhangi bir grafiğin modüllere benzersiz bir özyinelemeli ayrışması vardır. modüler ayrıştırma, grafikten oluşturulabilir doğrusal zaman; modüler ayrıştırma algoritmalarının tanınması dahil diğer grafik algoritmalarında uygulamaları vardır. karşılaştırılabilirlik grafikleri.

Ayrıca bakınız

Referanslar

  • Fronček, Dalibor (1989), "Yerel doğrusal grafikler", Mathematica Slovaca, 39 (1): 3–6, hdl:10338.dmlcz / 136481, BAY  1016323
  • Hartsfeld, Nora; Ringel, Gerhard (1991), "Temiz nirengi", Kombinatorik, 11 (2): 145–155, doi:10.1007 / BF01206358.
  • Cehennem, Pavol (1978), "Verilen mahalleler I ile grafikler", Problèmes cominatoires ve théorie des graphesColloques internationaux C.N.R.S., 260, s. 219–223.
  • Larrión, F .; Neumann-Lara, V.; Pizaña, M.A. (2002), "Whitney üçgenlemeleri, yerel çevre ve yinelenen klik grafikleri", Ayrık Matematik, 258 (1–3): 123–135, doi:10.1016 / S0012-365X (02) 00266-2.
  • Malnič, Aleksander; Mohar, Bojan (1992), "Yüzeylerin yerel döngüsel üçgenlemelerinin oluşturulması", Kombinatoryal Teori Dergisi, B Serisi, 56 (2): 147–164, doi:10.1016 / 0095-8956 (92) 90015-P.
  • Sedláček, J. (1983), "Sonlu grafiklerin yerel özellikleri üzerine", Çizge Teorisi, Lagów, Matematik Ders Notları, 1018, Springer-Verlag, s. 242–247, doi:10.1007 / BFb0071634, ISBN  978-3-540-12687-4.
  • Seress, Ákos; Szabó, Tibor (1995), "Döngü mahallelerine sahip yoğun grafikler", Kombinatoryal Teori Dergisi, B Serisi, 63 (2): 281–293, doi:10.1006 / jctb.1995.1020, dan arşivlendi orijinal 2005-08-30 tarihinde.
  • Wigderson, Avi (1983), "Yaklaşık grafik renklendirme için performans garantisinin iyileştirilmesi", ACM Dergisi, 30 (4): 729–735, doi:10.1145/2157.2158.