نظریه گراف

نظریه گراف - آن را یکی از بخش های فرعی از ریاضیات است، از ویژگی های اصلی آن از روش های هندسی در این مطالعه از اشیاء است. این نظر گرفته می شود بنیانگذار ریاضی دان معروف اویلر.

استفاده از نظریه گراف به اواخر قرن 19، به راه حل مشکلات جالب کاهش یافت و توجه عمومی قابل توجهی جلب کرد. از اواخر سده 20، هنگامی که نظریه گراف به عنوان یک رشته مستقل ریاضی تشکیل شد، از آن شده است به طور گسترده ای در زمینه هایی مانند سایبرنتیک، فیزیک، تدارکات، برنامه نویسی، زیست شناسی، الکترونیک، حمل و نقل و سیستم های ارتباطی استفاده می شود.

مفاهیم اساسی نظریه گراف

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

در اصطلاحات از تئوری به عنوان مفاهیم زیر می باشد:

گراف گراف است، همه لبه ها و رئوس میان راس و لبه می باشد.

گراف همبند - یک است که دارای دو قله های مختلف وجود داشته زنجیره اتصال آنها.

نمودار متصل وزن - که مجموعه ای از تابع وزن.

درخت - نمودار متصل شده، بدون چرخه.

اسکلت - یک زیرگراف است که یک درخت.

در تصویر نمودار در هواپیما نماد تعریف استفاده می شود: انتخاب راس نقطه مطابق با سطح ابتدایی و اگر لبه است بین رئوس، امتیاز مربوطه بخش ترکیب شده است. اگر نمودار گرا، این بخشها در با فلش جایگزین شده است.

اما تصویر نمودار با او مقایسه نیست، به عنوان مثال با یک ساختار مجرد، چرا که یک نمودار را می توان با توجه به بیش از یک نمایندگی های گرافیکی. نقاشی بر روی هواپیما به منظور ببینید که دو رأس لبه متحد داده می شود، و که نیست.

در میان برخی از وظایف نظریه گراف متمایز:

1. مشکل از کوتاه ترین مدار (جایگزینی سخت افزار، قرار دادن، آمبولانس و مبادلات تلفنی).
2. مشکل حداکثر جریان (جنبش سفارش در یک شبکه پویا، توزیع کار، این سازمان از ظرفیت).
3. مشکل از پوشش و بسته (مراکز اقامت اعزام).
4. رنگ آمیزی در ستون (قرار دادن حافظه در کامپیوتر های الکترونیکی).
5. شبکه های ارتباطی و نمودار (ایجاد یک شبکه ارتباطات، تجزیه و تحلیل شبکه های ارتباطی).

در حال حاضر غیر ممکن است به برنامه اکثر وظایف بدون آگاهی از نظریه گراف. این باعث می شود آن را آسان تر و آسان تر برای کار با رایانه است.

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

ویژگی مهمی از سیستم کنترل یا مدل مجموعه ای از است رابطه دوتایی با مجموعه ای از اقدامات و واحد داده ها. این ساختارها تنها بخشی از برنامه و اطلاعات توسط آنها تبدیل شده است. بنابراین، نمودار در طراحی برای برنامه نویس است.