Köşe (grafik teorisi) - Vertex (graph theory)

En soldaki 6 numaralı tepe noktasının bir yaprak tepe noktası veya bir asılı tepe noktası olduğu 6 köşesi ve 7 kenarı olan bir grafik

Gelen matematik ve daha özel olarak grafik teorisi , bir tepe (çoğul noktalar ) ya da düğüm grafikleri oluşturulduğu temel birimdir: bir yönsüz grafik köşe bir dizi ve bir dizi oluşur kenarları (vertices sırasız çifti), ise bir yönlendirilmiş grafiktir köşe bir dizi ve yayların bir dizi (vertices sıralı çifti) oluşur. Bir grafiğin diyagramında, bir tepe noktası genellikle etiketli bir daire ile temsil edilir ve bir kenar, bir tepe noktasından diğerine uzanan bir çizgi veya ok ile temsil edilir.

Graf teorisi açısından, köşeler özelliksiz ve bölünemez nesneler olarak kabul edilir , ancak grafiğin ortaya çıktığı uygulamaya bağlı olarak ek bir yapıya sahip olabilirler; örneğin, bir anlamsal ağ , köşelerin kavramları veya nesne sınıflarını temsil ettiği bir grafiktir.

Bir kenarı oluşturan iki köşenin bu kenarın uç noktaları olduğu söylenir ve kenarın köşelere denk geldiği söylenir. Bir köşe ağırlık başka bir köşe bitişik olduğu söylenen v grafiği (bir kenar içeriyorsa v , w ). Mahalle bir tepe noktası v bir olduğunu kaynaklı alt grafiğinin bitişik tüm köşe oluşturduğu grafiğinin,  v .

Köşe türleri

8 köşesi ve 10 kenarı olan küçük bir örnek ağ.
8 köşeli (biri izole edilmiş) ve 10 kenarlı örnek ağ.

Derecesi (v) bir grafikte δ gösterilen bir köşe, buna kenarları olay sayısıdır. Bir izole edilmiş bir tepe derecesi sıfır olan bir tepe olduğu; yani, herhangi bir kenarın bitiş noktası olmayan bir tepe noktası (örnek görüntü, izole edilmiş bir tepe noktasını göstermektedir). Bir yaprak tepe noktası (ayrıca sarkıt tepe noktası ), birinci dereceli bir tepe noktasıdır. Yönlendirilmiş bir grafikte, 𝛿 + (v) ile gösterilen dış derece (giden kenarların sayısı), 𝛿 (v) ile gösterilen dereceden (gelen kenarların sayısı) ayırt edilebilir ; bir kaynak tepe noktası, derece sıfır olan bir tepe noktası iken , bir çöküntü tepe noktası, derece sıfır olan bir tepe noktasıdır. Bir simpleksel tepe olan komşu bir formu biridir klik : Her iki komşu bitişiktir. Bir üniversal köşe grafikte her tepe bitişik olan bir tepe noktasıdır.

Bir kesik tepe çıkarılması kalan grafik kesin olan bir tepe olduğu; köşe ayırıcı , kaldırılması durumunda kalan grafiğin bağlantısını küçük parçalara ayıracak olan bir köşe noktaları topluluğudur. Bir K tepe-bağlı grafik daha az ve bundan da bir grafiktir k her zaman bağlı kalan grafik yaprak köşe. Bir bağımsız ayar bitişik olan herhangi iki tanesi köşe bir dizi, bir köşe kapağı grafikteki her kenarının en azından bir son nokta içeren köşelerin bir kümesidir. Tepe alanı , bir grafiğin grafiğin noktalar ile karşılık gelen taban vektörlerinin bir dizi olan bir vektör alanıdır.

Bir grafik, herhangi bir tepe noktasını diğer herhangi bir tepe noktasına eşleyen simetrilere sahipse , tepe noktası geçişlidir . Grafik numaralandırma ve grafik izomorfizmi bağlamında, etiketli köşeler ile etiketsiz köşeler arasında ayrım yapmak önemlidir . Etiketli tepe noktası, diğer etiketli tepe noktalarından ayırt edilmesini sağlayan ekstra bilgilerle ilişkilendirilen bir tepe noktasıdır; iki grafiğin eşbiçimli olduğu kabul edilebilir, ancak köşeleri arasındaki benzerlik, köşeleri eşit etiketlerle eşleştirirse. Etiketlenmemiş bir tepe noktası, herhangi bir ek bilgiye dayanmayan ve yalnızca grafikteki komşuluklarına dayalı olarak başka herhangi bir tepe noktasının yerine kullanılabilen bir tepe noktasıdır .

Grafiklerdeki köşeler, çokyüzlülerin köşeleriyle benzerdir, ancak bunlarla aynı değildir : çokyüzlülerin iskeleti , köşeleri çokyüzlülerin köşeleri olan bir grafik oluşturur, ancak çokyüzlü köşelerin ek yapısı (geometrik konumları) vardır. grafik teorisinde mevcut olduğu varsayılmaz. Tepe şekil çok yüzeyli bir tepe noktası bir grafik bir köşe bölgesinde benzer.

Ayrıca bakınız

Referanslar

  • Gallo, Giorgio; Pallotino, Stefano (1988). "En kısa yol algoritmaları". Yöneylem Araştırması Yıllıkları . 13 (1): 1-79. doi : 10.1007/BF02288320 .
  • Berge, Claude , Théorie des graphes et ses uygulamaları . Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 s. (İngilizce baskı, Wiley 1961; Methuen & Co, New York 1962; Rusça, Moskova 1961; İspanyolca, Meksika 1962; Romanya, Bükreş 1969; Çince, Şanghay 1963 ; 1962 ilk İngilizce baskısının ikinci baskısı. Dover, New York 2001)
  • Chartrand, Gary (1985). Giriş grafik teorisi . New York: Dover. ISBN'si 0-486-24775-9.
  • Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Grafik teorisi, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN'si 0-19-853916-9.
  • Harary, Frank (1969). Grafik teorisi . Okuma, Mass.: Addison-Wesley Publishing. ISBN'si 0-201-41033-8.
  • Harry, Frank; Palmer, Edgar M. (1973). Grafiksel numaralandırma . New York, Akademik Basın. ISBN'si 0-12-324245-2.

Dış bağlantılar