Kolay endeks seti - Friendly-index set

İçinde grafik teorisi, bir dost endeks kümesi bir Sınırlı set nın-nin tamsayılar verilen ile ilişkili yönsüz grafik ve bir tür tarafından oluşturulmuştur grafik etiketleme deniliyor kolay etiketleme.

Dostça bir etiketleme n-vertex yönsüz grafik G = (V,E) 0 ve 1 değerlerinin köşelerine atanması olarak tanımlanır G 0 etiketli köşe sayısının 1 etiketli köşe sayısına olabildiğince yakın olması özelliği ile: ya eşit olmalı (çift sayıda köşeli grafikler için) ya da bir ile farklı olmalıdır (tek sayıda köşeler).

Köşelerinin dostça etiketlenmesi göz önüne alındığında Gayrıca kenarlar da etiketlenebilir: belirli bir kenar uv uç noktaları 0 ile etiketlenir sen ve v eşit etiketlere sahiptir ve uç noktaları farklı etiketlere sahipse 1 ile etiketlenir. dost endeks etiketlemenin mutlak değer 0 olarak etiketlenen kenarların sayısı ile 1 olarak etiketlenen kenarların sayısı arasındaki fark.

uygun dizin seti nın-nin G, belirtilen FI(G), dostça etiketlemelerin kolay indeksleri olarak ortaya çıkabilecek sayılar kümesidir. G.[1]

Grafik Etiketlemenin Dinamik Araştırması, çeşitli grafiklerin anlaşılır indekslerini inceleyen bir makale listesi içerir.[2]

Referanslar

  1. ^ Kwong, Harris; Lee, Sin-Min; Ng, Ho (2008). "2 düzenli grafiklerin uygun dizin kümelerinde". Ayrık Matematik. 308 (23): 5522–5532. doi:10.1016 / j.disc.2007.10.018. BAY  2459372.
  2. ^ Gallian, Joseph A (2009). "Grafik etiketlemenin dinamik bir incelemesi" (PDF). El. J. Combinat. 16 (# DS6). Arşivlenen orijinal (PDF) 2004-11-20.

Dış bağlantılar