تاریخچه پیدایش درخت «گراف»


img/daneshnameh_up/5/5c/Cayley.jpg
آرتور کایلی


ساختاری که امروزه درخت نام دارد نخستین بار در سال 1847 در کارهای گوستاو کیرشهف (1824 ـ 1877) درباره شبکه های الکتریکی به کار رفت. در همین زمان این مفهوم در کتاب هندسه مکانها اثر کارل فون اشتاوت (1798 ـ 1867) نیز به کار برده شد. در 1857 آرتور کایلی (1841ـ 1895)، که از این تحولات قبلی بی اطلاع بود. مجدداً درختها را کشف کرد.

کایلی نخستین کسی است که این ساختار را «درخت» نامید. او درختها را در کاربردهایی در ارتباط با ایزومرهای شیمیایی مورد استفاده قرار داد. او همچنین شمارش رده هایی از درختها را مورد تحقیق قرار داد. کیلی در نخستین اثر خود درباره درختها، درختهای ریشه دار نشانگداری نشده را شمارش کرد. پس از آن شمارش درختهای مرتب نشانگذاری نشده را به انجام رساند. کارل بورچاردت (1817 ـ 1880) و ماری آنموند جوردان (1838 ـ 1932) دو نفر از معاصران کیلی بودند که آنها نیز مطالعاتی درباره درختها انجام دادند.

فرمول که تعداد درختهای نشاندار n راسی را به دست می دهد .در سال 1860 توسط کارل بورچاردت کشف شد. کایلی بعداً، در 1889، برهان مستقلی برای این فرمول عرضه کرد. از آن زمان تا کنون فرمولهای دیگری نیز از آن اشتقاق شده است.
مقالات جی، پولیا اثری پیشاهنگ درباره شمارش درختها و ساختارهای ترکیباتی دیگر است.همچنین نظریه شمارش پولیا، در این اثر ابداع شد.

عملاً ثابت شده است که کامپیوترهای رقمی ای که سرعتهای بالا دارند محرکی دائمی برای کشف کاربردهای جدیدی از درختها هستند. نخستین کاربرد این ساختارها هنگام استفاده از فرمولهای جبری بروز کرد. این مربوط می شود به کارگریس هوپر در سال 1951 از آن زمان تا کنون کاربردهای درختها، در کامپیوتر به طور وسیعی مورد تحقیق و تفحص قرار گرفته است. ابتدا تنها در مستندات برخی الگوریتمها نتایج خاصی ظاهر شد. نخستین بررسی کلی کاربردهای درختها در سال 1961 توسط کنت ایورسن به صورت بخشی از بررسی وسیعتری در مورد ساختارهای داده ها انجام گرفت. برای ردگیری ایده هایی چون جستجوی پیش ترتیب و جستجوی پس ترتیب باید تا اوایل دهه 1960 به عقب برگردیم. در اینه دهه شواهدی از این ایده ها را در کارهای زدزیسلا پاولاک، لیل جانسون و کنت ایورسن می بینیم.


تعداد بازدید ها: 23374