فاصله ها و درخت ها

زندگي با رياضيات
 

درخت ها به عنوان گراف ها داراي کاربردهاي فراواني هستند که از آن جمله در ذخيره داده ها و محاسبه ي فاصله ها در ارتباطات است.گراف همبندي که هيچ دوري نداشته باشد يک درخت ناميده مي شود.
درخت در رشته هاي مختلفي مانند شيمي، مهندسي برق و علم محاسبه کاربرد دارد.گراف مربوط به هيدروکربن cnh2n+2 يك درخت است.
کيلي در سال 1857 درختها را در ارتباط با شمارش ايزومرهاي مختلف هيدروکربن ها کشف کرد.
اگر هزينه ي کشيدن مثلاً راه آهن بين هر دو شهر از n شهر مشخص باشد.ارزانترين شبکه اي که اين n شهر را به هم وصل مي کند با مفهوم يک درخت از مرتبه ي n ارتباط نزديک دارد،زيرا گراف هاي درختي در بين گراف هاي همبند، کمترين يال را دارند.
در سال 1847 کرشهف هنگام حل دستگاه هاي معادلات خطي مربوط به شبکه هاي الکتريکي،درخت ها را کشف و نظريه درختها را بارور کرد.
ديويد گيل يک بازي را تحت عنوان«پل زني»ابداع و به بازار عرضه داشت که اساس اين بازي به کمک خواص گراف هاي درخت بود.در اين بازي(شکل 2)هر يک از بازيکنان يک شبکه مستطيلي از ميله ها دارند.
بازيکنان به طور متناوب حرکت مي کنند.در هر حرکت يک جفت از ميله هاي آماده را با پلي به طول واحد به هم مي پيوندند.
هدف بازيکن 1 ساختن پلي از چپ به راست و هدف بازيکن 2 ساختن پلي از بالا به پايين است.بازيکن 1 مي تواند با يک حرکت دلخواه آغاز کند سپس راهبرد بازيکن 2 را دنبال کند.اگر راهبرد بازيکن 2 همواره پلي را در مکان حرکت نخست ايجاب کند، يک حرکت دلخواه انجام مي دهد.اگر راهبرد بازيکن 2 منجر به يک بُرد شود، بازيکن 1 به جاي او برنده مي شود، زيرا حرکت هاي اضافي ضرري ندارد.پس بازيکن 2 نمي تواند يک راهبرد بُرد داشته باشد.با استفاده از پنداره هاي هامني بودن، مي توان نشان داد که نتيجه تساوي امکان ندارد.بنابراين، مي توان ثابت کرد که بازيکن 1 در اين بازي داراي يک راهبرد،بُرد است.
حل مساله فروشنده ي سيار نيز با خواص درخت امکان پذير است.فرض کنيد فروشنده ي سياري پيش از بازگشت به وطن بايستي به چند شهر سفر کند.طبيعتاً مايل است که اين کار را در کوتاهترين زمان ممکن و کمترين هزينه ي ممکن انجام دهد.اگر او از روش آزمايش و خطا استفاده کند، در صورت زياد بودن تعداد شهرها اين کار عملي نيست.به عنوان مثال اگر تعداد شهرها صد باشد، تعداد مدارهاي ممکن بالغ بر 157 10×9 مي شود که عدد بسيار بزرگي است.
فرض کنيد که مدار براي مساله فروشنده ي سيار در مورد پنج شهر e و dو c و b و a باشد اگر راس a را حذف کنيم، مسيري گذرنده از راس هاي b وc و e به دست مي آوريم.چنين مسيري، درختي با راس هاي مزبور است و کل هزينه ي سفر فروشنده از افزودن هزينه ي يالهاي اين درخت به هزينه ي آن دو يال متصل به a به دست مي آيد.نتيجه آنکه اگر هزينه ي يک درخت اقتصادي با راس هاي b و c و d و e را به هزينه ي آن دو يال متصل به a که در ميان يالهاي متصل به a کمترين هزينه را دارند، بيفزائيم مجموع از جواب مسئله ي فروشنده ي سيار تجاوز نخواهد کرد.
منبع: نشريه اطلاعات علمي -شماره 359