WİENER ENDEKSİ  

Kimyasal grafik teorisinde, Harry Wiener tarafından sunulan Wiener endeksi, moleküldeki hidrojen olmayan atomları temsil eden kimyasal grafikteki tüm köşe çiftleri arasındaki en kısa yolların uzunluklarının toplamı olarak tanımlanan bir molekülün topolojik endeksidir[1]. Harry Wiener de Brooklyn Koleji’nin Amerikalı Kimyacısıydı ve topolojik endekslerin çalışmasına önemli ve temel katkılarda bulundu ve Wiener endeksi ile parafinlerin kaynama noktaları arasında bir ilişki kurdu.

TARİHÇE

Wiener endeksi adını 1947’de tanıtan Harry Wiener’den almıştır. İlk keşfettiğinde Wiener ona “yol numarası” adını verdi. [2] Moleküler dallanma ile ilgili en eski topolojik endekstir. [3] Başarısına dayanarak, Viyana’da çalışmasından sonra grafiğin mesafe matrisindeki bilgilere dayanan kimyasal grafiklerin diğer birçok topolojik indeksi geliştirilmiştir. [4]

Aynı miktar, saf matematikte, brüt durum, [5] bir grafiğin mesafesi, [6] ve iletim de dahil olmak üzere çeşitli isimler altında incelenmiştir . [7] Wiener göstergesi da  yakınlık merkezî bir grafik bir köşe, belirli bir tepe noktası ve sıkça kullanılan tüm diğer köşe arasındaki mesafelerin toplamına ters orantılı bir miktar Sosyometri ve teorinin sosyal ağlar ile yakından ilgilidir . [6]

ÖRNEK 

Bütan (Cı- 4 , H 10 ), iki farklı olan , yapısal izomerleri : n, doğrusal dört karbon atomu içeren bir yapı, ile -bütan, izobütan kollara ayrılmış bir yapıya sahip,. N- bütan için kimyasal grafik dört köşeli bir yol grafiğidir ve izobütan için kimyasal grafik, üç yaprağa bağlı bir merkezi tepe noktası olan bir ağaçtır.

N -bütan molekül mesafede üç mesafeli iki birbirine, iki çift mesafe biri köşe üç çift ve bir çift sahip olan Wiener göstergesi olacak şekilde

İzobütan molekülünün birbirinden uzak mesafelerde üç çift köşe noktası (üç yaprak-merkez çifti) ve iki mesafeden üç çift (yaprak-yaprak çiftleri) vardır. Bu nedenle, Wiener endeksi

Bu sayılar, Wiener endeksinin özel durumları için formüllerin örnekleridir: herhangi -vertex yol grafiği grafiğinin gibi N , -butan [8] ve  herhangi  izobutan grafiği gibi -vertex yıldızı . [9]

Bu nedenle, bu iki molekül aynı kimyasal formüle ve aynı sayıda karbon-karbon ve karbon-hidrojen bağına sahip olsa da, farklı yapıları farklı Wiener indekslerine yol açar.

KİMYASAL ÖZELLİKLERLE İLİŞKİSİ 

Wiener, Wiener indeks numarası ile yakından ilişkili olduğunu göstermiştir kaynama noktası arasında kalan molekülü. [2] üzerinde daha sonraki çalışma kantitatif yapı-aktivite ilişkileri aynı zamanda onun parametrelerinin dahil olmak üzere  kritik nokta, [10] yoğunluğu , yüzey gerilimi ve viskoziteye sıvı fazın, [11] ve Van Der molekülün Waals yüzey alanı gibi diğer miktarları ile ilişkili olduğunu göstermiştir. [12]

KEYFİ GRAFİKLERDE HESAPLAMA  

Wiener endeksi, grafikteki tüm çift mesafeleri hesaplamak için bir algoritma kullanılarak doğrudan hesaplanabilir. Grafik ağırlıksız olduğunda (yani bir yolun uzunluğu sadece kenar sayısıdır), bu mesafeler her başlangıç ​​köşesi için bir kez önce bir arama  algoritması tekrarlanarak hesaplanabilir . [13] Bu yaklaşım için toplam süre O ( nm ) ‘dir, burada n , grafikteki köşe sayısıdır ve m, kenar sayısıdır. 

Ağırlıklı grafikler, bir yerine kullanabilir Floyd-Warshall algoritması [13] [14] [15] ya da Johnson algoritması , [16] süresi O (çalışan 3 ) ya da O ( mil + 2 günlük  n , sırasıyla). Kimyasal bilişim literatüründe tekrarlanan matris çarpımına dayanan alternatif ancak daha az verimli algoritmalar da geliştirilmiştir. [17] [18]

ÖZEL GRAFİK TÜRLERİNDE HESAPLAMA  

Temel grafik bir ağaç olduğunda (örneğin, Wiener tarafından çalışılan alkanlar için geçerli olduğu gibi), Wiener endeksi daha verimli bir şekilde hesaplanabilir. Grafik, tek bir kenar kaldırarak iki alt ağaçlar bölünür Eğer e , daha sonra Wiener endeksi birbirine geçmesine yolları temsil eden üçüncü bir terim ile, iki alt ağaçlar Wiener indislerinin toplamı olan e . Bu üçüncü terim tüm noktaların mesafelerin toplamı hesaplayarak lineer zamanda hesaplanabilir e her bir alt ağacı içinde ve iki toplamları çarpılması. [19] Bu bölme ve fethetme algoritması ağaçlardan sınırlı üçlü genişliklere kadar genelleştirilebilir ve bu grafikler için doğrusal zamana yakın algoritmalara yol açar. [20]

Bojan Mohar ve Tomaž Pisanski tarafından bir ağacın Wiener indeksini hesaplamak için alternatif bir yöntem , problemi, bir yolun ağırlığının, uzunluğunun iki uç noktasının ağırlıklarıyla uzunluğu olduğu ağırlıklı köşeli grafiklere genelleştirerek çalışır. Eğer v ağaçtan Wiener indeksi birleştirme ile hesaplanabilir ağacın yaprak verteksidir v yolları için basit bir düzeltme ifadesi, (birlikte ağırlıkları ekleme) ile üst elde edilen daha küçük ağaç indeksini hesaplamak ve ekleme kenardan v’den ebeveyne geçen Yaprakları bu şekilde tekrar tekrar kaldırarak, Wiener indeksi doğrusal zamanda hesaplanabilir. [13]

Daha basit grafiklerin ürünleri olarak oluşturulan grafikler için, ürün grafiğinin Wiener indeksi genellikle faktörlerinin indekslerini birleştiren basit bir formülle hesaplanabilir. [21] Benzoidler (düzenli altıgenlerin kenardan kenara yapıştırılmasıyla oluşturulan grafikler) izometrik olarak üç ağacın Kartezyen ürününe gömülebilir , bu da Wiener indekslerinin doğrusal zaman ağacı ile birlikte ürün formülü kullanılarak lineer zamanda hesaplanmasına izin verir algoritması. [22]

Kaynakça 1

  1. Rouvray, Dennis H. (2002), “Wiener endeksinin yarım yüzyıllık zengin mirası”, Rouvray, Dennis H .; King, Robert Bruce (ed.), Kimyada Topoloji: Moleküllerin Ayrık Matematiği , Horwood Yayınları, s. 16–37.
  2. Wiener, H. (1947), “Parafin kaynama noktalarının yapısal olarak belirlenmesi”,Amerikan Kimya Derneği Dergisi,1(69): 17-20,doi:10.1021 / ja01193a005.
  3. Todeschini, Roberto; Consonni, Viviana (2000), Moleküler Tanımlayıcıların El Kitabı , Wiley, ISBN 3-527-29913-0.
  4. Rouvray (2002) . Bkz. Özellikle Tablo 2, s. 32.
  5. Harary, Frank (1959), “Durum ve çelişkiler”, Sosyometri , 22 : 23–43, doi : 10.2307 / 2785610 , MR 0134798
  6. Entringer, RC; Jackson, DE; Snyder, DA (1976), “Grafiklerdeki uzaklık”,Çekoslovak Matematiksel Dergisi,26(101): 283-296,MR 0543771.
  7. Šoltés, Ľubomír (1991), “Grafiklerde iletim: bir bağ ve tepe noktasını kaldırma”, Mathematica Slovaca , 41 (1): 11–16, MR 1094978.
  8. Zamanda Rouvray (2002) , bu formül önceden tarafından verilen tarif , Wiener (1947) .
  9. Bonchev, D .; Trinajstić, N. (1977), “Bilgi teorisi, uzaklık matrisi ve moleküler dallanma”, Journal of Chemical Physics , 67 (10): 4517-4533, Bibcode : 1977JChPh..67.4517B , doi : 10.1063 / 1.434593 , hdl : 10338.dmlcz / 104.047.
  10. Stiel, Leonard I .; Thodos, George (1962), “Doymuş alifatik hidrokarbonların normal kaynama noktaları ve kritik sabitleri”, AIChE Journal , 8 (4): 527-529, doi : 10.1002 / aic.690080421.
  11. Rouvray, DH; Crafford, BC (1976), “Fiziksel-kimyasal özelliklerin topolojik faktörlere bağımlılığı”, Güney Afrika Bilim Dergisi , 72 : 47.
  12. Gutman, Ivan; Körtvélyesi, T. (1995), “Wiener indeksleri ve moleküler yüzeyleri”, Zeitschrift für Naturforschung , 50a : 669-671.
  13. Mohar, Bojan; Pisanski, Tomaž(1988), “Bir grafiğin Wiener indeksi nasıl hesaplanır”,Matematiksel Kimya Dergisi,2(3): 267–277,doi:10.1007 / BF01167206,MR 0966088.
  14. Floyd, Robert W. (Haziran 1962), “Algoritma 97: En Kısa Yol”, ACM’nin İletişimi , 5 (6): 345, doi : 10.1145 / 367766.368168.
  15. Warshall, Stephen (Ocak 1962), “Boole matrisleri üzerine bir teorem”, ACM Dergisi , 9 (1): 11–12, doi : 10.1145 / 321105.321107.

Kaynakça 2

  1. Johnson, Donald B. (1977), “Seyrek ağlarda en kısa yollar için etkili algoritmalar”, ACM Dergisi , 24 (1): 1–13, doi : 10.1145 / 321992.321993.
  2. Bersohn, Malcom (1983), “Bir molekülün mesafe matrisinin hesaplanması için hızlı bir algoritma”, Hesaplamalı Kimya Dergisi , 4 (1): 110–113, doi : 10.1002 / jcc.540040115.
  3. Müller, WR; Szymanski, K .; Knop, JV; Trinajstić, N. (1987), “Moleküler mesafe matrisinin inşası için bir algoritma”, Hesaplamalı Kimya Dergisi , 8 (2): 170–173, doi : 10.1002 / jcc.540080209.
  4. Canfield, ER; Robinson, RW; Rouvray, DH (1985), “Genel ağaç için Wiener moleküler dallanma indeksinin belirlenmesi”, Hesaplamalı Kimya Dergisi , 6 (6): 598-609, doi : 10.1002 / jcc.540060613 , MR 0824918.
  5. Cabello, Sergio; Knauer, Christian (2009), “Dik aralıklı arama yoluyla sınırlı treididite grafikleri için algoritmalar”, Hesaplamalı Geometri , 42 (9): 815–824, doi : 10.1016 / j.comgeo.2009.02.001 , MR 2543804.
  6. Yeh, Yeong Nan; Gutman, Ivan (1994), “Bileşik grafiklerdeki tüm mesafelerin toplamı”, Ayrık Matematik , 135 (1-3): 359-365 , doi : 10.1016 / 0012-365X (93) E0092-I , MR 1310892.
  7. Chepoi, Victor; Klavžar, Sandi (1997), “Benzinli sistemlerin lineer zamanda Wiener indeksi ve Szeged indeksi”, Kimyasal Bilgi ve Bilgisayar Bilimleri Dergisi , 37 (4): 752-755, doi : 10.1021 / ci9700079. Kısmi küp yapılarına dayanan benzenoidler için önceki algoritmalar için , bkz. Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), “Tepe-mesafe ilişkilerini yansıtan benzenoid sistemlerin etiketlenmesi” (PDF) , Kimyasal Bilgi ve Bilgisayar Bilimleri Dergisi , 35 (3): 590-593, doi : 10.1021 / ci00025a030.
Reklam (#YSR)