نظریه گراف: مفاهیم و وظایف اساسی نمودارها به عنوان یک ساختار داده نمودارها آشنایی نظری (اولین تلاش)

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

نظریه گراف از حل مسئله پل های کونیگزبرگ در سال 1736 توسط ریاضیدان معروف سرچشمه می گیرد. لئونارد اویلر(1707-1783: متولد سوئیس، زندگی و کار در روسیه).

مشکل در مورد پل های Königsberg.

هفت پل در شهر پروس کونیگزبرگ بر روی رودخانه پرگال وجود دارد. آیا می توان مسیر پیاده روی را پیدا کرد که دقیقاً یک بار از هر پل عبور کند و در همان نقطه شروع و به پایان برسد؟

گرافی که در آن مسیری وجود دارد که از یک راس شروع و به پایان می رسد و دقیقاً یک بار از تمام یال های نمودار می گذرد، نامیده می شود.نمودار اویلر

دنباله رئوس (شاید تکرار شونده) که مسیر مورد نظر و همچنین خود مسیر از آن عبور می کند، نامیده می شود.چرخه اویلر .

مشکل سه خانه و سه چاه.

سه خانه و سه چاه وجود دارد که به نوعی در یک هواپیما قرار دارند. از هر خانه به هر چاه مسیری بکشید تا مسیرها با هم تلاقی نکنند. این مشکل توسط کوراتوفسکی (1896 - 1979) در سال 1930 حل شد (نشان داده شد که راه حلی وجود ندارد).

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

ماهیت راه حل منتشر شده این است که یک عدد بزرگ اما محدود (حدود 2000) از انواع متقابل بالقوه را برای قضیه چهار رنگ امتحان کنید و نشان دهید که هیچ موردی نیز یک نمونه متضاد نیست. این جستجو توسط برنامه در حدود هزار ساعت کارکرد ابررایانه کامل شد.

بررسی "دستی" راه حل حاصل غیرممکن است - دامنه شمارش فراتر از محدوده توانایی های انسانی است. بسیاری از ریاضیدانان این سوال را مطرح می کنند: آیا می توان چنین "برهان برنامه ای" را یک اثبات معتبر در نظر گرفت؟ به هر حال، ممکن است خطاهایی در برنامه وجود داشته باشد ...

بنابراین، ما فقط می توانیم به مهارت های برنامه نویسی نویسندگان تکیه کنیم و باور کنیم که آنها همه چیز را درست انجام داده اند.

تعریف 7.1. شمردن جی= جی(V, E) مجموعه ای از دو مجموعه متناهی است: V – نامیده می شود بسیاری از رئوسو مجموعه E از جفت عناصر از V، i.e. EÍV´V، نامیده شد بسیاری از لبه ها، اگر جفت ها نامرتب باشند، یا قوس های زیادی، اگر جفت ها سفارش داده شده باشند.

در حالت اول، نمودار جی(V, E) تماس گرفت بی جهت، در دوم - جهت دار.

مثال. یک نمودار با مجموعه ای از رئوس V = (a,b,c) و مجموعه ای از یال های E =((a, b), (b, c))

مثال. یک نمودار با V = (a،b،c،d،e) و E = ((a، b)، (a، e)، (b، e)، (b،d)، (b، c)، (ج، د))،

اگر e=(v 1 ,v 2)، eОЕ، آنگاه می گویند که یال e است متصل می کندرئوس v 1 و v 2.

دو راس v 1,v 2 نامیده می شوند مجاور، اگر لبه ای وجود داشته باشد که آنها را به هم وصل می کند. در این شرایط هر یک از رئوس فراخوانی می شود حادثه لبه مربوطه .

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

تعداد رئوس نمودار جیبیایید نشان دهیم v، و تعداد لبه ها است ه:

.

نمایش هندسی نمودارها به صورت زیر است:

1) راس نمودار یک نقطه در فضا (روی صفحه) است.

2) لبه یک گراف بدون جهت - یک قطعه.

3) قوس یک گراف جهت دار - یک قطعه جهت دار.

تعریف 7.2.اگر در یال e=(v 1 ,v 2) v 1 =v 2 رخ دهد، یال e فراخوانی می شود. حلقه. اگر یک نمودار اجازه حلقه ها را بدهد، آنگاه فراخوانی می شود نمودار با حلقه ها یا شبه نگار .

اگر یک نمودار بیش از یک یال را بین دو راس اجازه دهد، آنگاه فراخوانی می شود چند گراف .

اگر هر رأس یک گراف و/یا یال برچسب گذاری شده باشد، چنین نموداری فراخوانی می شود مشخص شده است (یا لود شده ). معمولاً از حروف یا اعداد صحیح به عنوان علامت استفاده می شود.

تعریف 7.3.نمودار جی (V , E ) تماس گرفت زیرگراف (یا بخش ) نمودار جی(V,E)، اگر V V, E E. اگر V = V، آن جی تماس گرفت زیرگراف فراگیر جی.

مثال 7 . 1 . یک نمودار بدون جهت داده شده است.

تعریف 7.4.نمودار نامیده می شود کامل ، اگر هر دو رأس آن توسط یک لبه به هم متصل شده اند. نمودار کامل با nرئوس با نشان داده می شود ک n .

شمارش K 2 ، به 3, به 4 و ک 5 .

تعریف 7.5.نمودار جی=جی(V, E) نامیده میشود دولپه ای ، اگر Vمثلاً می‌توان آن‌ها را به‌عنوان اتحادیه‌ای از مجموعه‌های مجزا نشان داد V=آب، بنابراین هر لبه دارای فرم ( v من , v j)، جایی که v من آو v j ب.

هر یال یک راس از A را به یک راس از B متصل می کند، اما هیچ دو راس از A یا دو راس از B به هم متصل نیستند.

یک گراف دو بخشی نامیده می شود دو لپه ای کامل شمردن ک متر , n، اگر آشامل مترقله ها، بشامل nرئوس و برای هر کدام v من آ, v j بما داریم ( v من , v j)E.

بنابراین، برای همه v من آ، و v j بلبه ای وجود دارد که آنها را به هم متصل می کند.

K 12 K 23 K 22 K 33

مثال 7 . 2 . یک نمودار دو بخشی کامل بسازید ک 2.4 و نمودار کامل ک 4 .

نمودار واحدn-مکعب بعدیکه در n .

رئوس نمودار مجموعه های باینری n بعدی هستند. لبه ها راس هایی را که در یک مختصات متفاوت هستند به هم متصل می کنند.

مثال:

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

در مورد دوره

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

قالب

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

منابع اطلاعاتی

1. V. A. Emelichev، O. I. Melnikov، V. I. Sarvanov، R. I. Tyshkevich. سخنرانی در مورد نظریه گراف. م.: خانه کتاب "لیبروکم"، 2009.
2. A. A. Zykov. نظریه گراف محدود نووسیبیرسک: ناوکا، 1969.
3. M. Swami، K. Thulasiraman. نمودارها، شبکه ها و الگوریتم ها. م.: میر، 1984.
4. M. Aigner، G. M. Ziegler. شواهد ازکتاب. ویرایش چهارم. اسپرینگر، 2009.
5. B. بولوباس. نظریه گراف مدرن. اسپرینگر، 1998.
6. J. A. Bondy، U. S. R. Murty. نظریه گراف. اسپرینگر، 2008.

الزامات

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

برنامه دوره

1. مفهوم گراف و انواع نمودارها
2. کاربردهای مختلف نمودارها: از پل های کونیگزبرگ تا اینترنت.
3. اتصال نمودار، زیرگراف ها و درجه راس.
4. تعاریف درختی معادل
5. مسطح بودن و معیار کوراتوفسکی
6. فرمول اویلر
7. عدد کروماتیک یک نمودار مسطح.
8. شمارش درختان: کد Prüfer و فرمول Cayley.
9. فرمول تعداد نمودارهای تک حلقه ای
10. چرخه های اویلر و معیار اویلر
11. چرخه های همیلتونی معیار دیراک و معیار چواتال.
12. تطبیق. قضیه هال و کونیگ.
13. نظریه گراف افراطی قضیه توران.
14. قیاسی از قضیه توران برای نمودارها در یک صفحه.
15. نظریه رمزی قرار بین شش نفر.
16. تعیین عدد رمزی
17. مرزهای پایین و بالایی برای اعداد رمزی.

نتایج یادگیری

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

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

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

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

نمودارها به عنوان وسیله ای مناسب برای توصیف روابط بین اشیاء عمل می کنند. ما قبلا از نمودارها به عنوان راهی برای نمایش بصری روابط باینری محدود استفاده کرده‌ایم.

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

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

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

• تعاریف اساسی

  همانطور که قبلاً در مثال ها اشاره شد، نمودارها روشی برای "تجسم" ارتباطات بین اشیاء خاص هستند. این ارتباطات می تواند "جهت دار" باشد، به عنوان مثال، در یک شجره نامه، یا "بدون جهت" (شبکه ای از دو طرفه). جاده ها). مطابق با این، در نظریه گراف دو نوع اصلی گراف وجود دارد: جهت دار (یا جهت دار) و غیر جهت دار.

• روش های ارائه

  تاکنون نمودارهای جهت دار و غیر جهت دار را تعریف کرده ایم و آنها را با استفاده از نقشه ها به تصویر می کشیم. شما می توانید یک نمودار را به عنوان یک جفت مجموعه تعریف کنید، اما این روش کاملاً دست و پا گیر است و بیشتر جنبه نظری دارد. توسعه رویکردهای الگوریتمی برای تجزیه و تحلیل ویژگی‌های نمودارها به روش‌های دیگری برای توصیف نمودارها نیاز دارد که برای محاسبات عملی از جمله استفاده از رایانه مناسب‌تر هستند. بیایید به سه روش رایج برای نمایش نمودارها نگاه کنیم.

• درختان

  تعریف 5.5. درخت بدون جهت یک گراف بدون جهت متصل و غیر چرخه ای است. تعریف 5.6. درخت جهت دار یک گراف جهت دار غیر کانتوری است که در آن نیم درجه هر رأسی بزرگتر از 1 نیست و دقیقاً یک راس وجود دارد که ریشه درخت جهت دار نامیده می شود که نیم درجه آن 0 است.

• درخت پوشا با کمترین وزن

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

• روش‌هایی برای پیمایش سیستماتیک رئوس نمودار

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

• مسئله مسیر در نمودارهای جهت دار وزنی

• ایزومورفیسم نمودار

  برای یک گراف جهت دار (V, E)، مجموعه E کمان ها را می توان به عنوان نموداری از یک رابطه دسترسی مستقیم باینری تعریف شده بر روی مجموعه رئوس در نظر گرفت. در یک گراف بدون جهت (V, E)، مجموعه E یال ها مجموعه ای از جفت های نامرتب است. برای هر جفت نامرتب (u, v) ∈ E می توانیم فرض کنیم که رئوس u و v توسط یک رابطه دودویی متقارن p به هم متصل شده اند. (u، v) ∈ р و (v، u) ∈ р.

• مرتب سازی توپولوژیکی

  تعریف 5.17. یک شبکه جهت دار (یا به سادگی یک شبکه) یک گراف جهت دار بدون کانتور* است. از آنجایی که شبکه یک نمودار بدون کانتور است، می توان نشان داد که رئوس (گره ها) شبکه با درجه خارج از صفر و همچنین رئوس (گره ها) با صفر در درجه وجود دارند. اولی را سینک یا خروجی شبکه و دومی را منابع یا ورودی شبکه می نامند.

• عناصر سیکلوماتیک

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

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

الگوریتمی برای شناسایی مستقیم چرخه اویلری
[فلوری]. اجازه دهید یک مولتی گراف G متصل را در نظر بگیریم، که همه رئوس آن دارای درجه زوج هستند، و سعی می کنیم آن را با یک ضربه ترسیم کنیم، بدون اینکه در طول فرآیند ساخت و ساز به اصلاحات در قسمت از قبل ترسیم شده مسیر متوسل شویم. کافی است قانون زیر را رعایت کنید:
1 از یک راس دلخواه a خارج می شویم. هر لبه رد شده را خط می زنیم.
2 ما هرگز در امتداد چنین لبه ای حرکت نمی کنیم و که در لحظه مورد بررسی یک تنگه است (یعنی وقتی حذف می شود، نموداری که توسط لبه های متقاطع تشکیل شده است به دو جزء متصل که هر کدام حداقل یک یال دارند تقسیم می شود).

با پیروی از این قانون، ما همیشه در موقعیت مطلوب خواهیم بود، زیرا وقتی در x = a هستیم، نمودار (لبه های غیر متقاطع) دارای دو رأس درجه فرد است: x و a; اگر رئوس جدا شده کنار گذاشته شوند، یک گراف متصل باقی می ماند که به موجب قضیه 1، دارای یک زنجیره اویلر است که از x شروع می شود.

محتوا
معرفی
فصل 1. تعاریف اساسی
مجموعه ها و نگاشت های چند ارزشی
نمودار مسیرها و خطوط
مدارها و چرخه ها
فصل 2. بررسی مقدماتی شبه نظم
شبه ترتیبی که توسط نمودار تعریف شده است
نمودار استقرایی و مبانی
فصل 3. تابع و تابع ترتیبی
گراندی برای یک گراف بی نهایت
ملاحظات کلی در مورد نمودارهای بی نهایت
تابع ترتیبی
توابع گراندی
عملیات روی نمودارها
فصل 4. اعداد پایه نظریه گراف
عدد سیکلوماتیک
عدد کروماتیک
شماره پایداری داخلی
شماره پایداری خارجی
فصل 5. هسته های نمودار
قضایای هستی و یگانگی
کاربرد برای توابع Grundy
فصل 6. بازی های نموداری
بازی نیم
تعریف کلی بازی (با اطلاعات کامل)
استراتژی ها
فصل 7. مسئله کوتاه ترین مسیر
فرآیندها بر اساس مراحل برخی از تعمیم ها
فصل 8. شبکه های حمل و نقل
مشکل حداکثر جریان مشکل کمترین جریان
مشکل جریان سازگار با مقدار مجموعه
شبکه های حمل و نقل بی پایان
فصل 9. قضیه نیم قدرت
نیمه درجه خروجی و ورودی
فصل 10. تطبیق یک نمودار ساده
حداکثر مشکل تطبیق
کمبود نمودار ساده
الگوریتم مجارستانی
تعمیم به حالت بی نهایت
کاربرد در نظریه ماتریس
فصل 11. عوامل
مسیرهای همیلتونی و خطوط همیلتونی
یافتن یک عامل
پیدا کردن یک نمودار جزئی با نیم درجه داده شده
فصل 12. مراکز نمودار
مراکز
شعاع
فصل 13. قطر یک گراف به شدت متصل
ویژگی های کلی نمودارهای به شدت متصل بدون حلقه
قطر
فصل 14. ماتریس مجاورت نمودار
کاربرد عملیات ماتریسی معمولی
شمارش مشکلات
مشکل رهبر
استفاده از عملیات بولی
فصل 15. ماتریس های حادثه
ماتریس های کاملا تک مدولار
سیستم های کاملاً تک مدولار
ماتریس های سیکلوماتیک
فصل 16. درختان و درختان اجدادی
درختان
تحقیق تحلیلی
درختان بزرگ
فصل 17. مسئله اویلر
اویلر خطوط اویلر را دور می‌زند
فصل 18. تطبیق یک نمودار دلخواه
نظریه مدار متناوب
پیدا کردن یک نمودار جزئی با درجات راس داده شده
تطابق کامل
کاربرد برای شماره پایداری داخلی
فصل 19. فاکتوروئیدها
چرخه هامیلتونی و فاکتوروئیدها
شرط لازم و کافی برای وجود فاکتوروئید
فصل 20. اتصال نمودار
نقاط بیان
نمودارها بدون مفصل
نمودارهای متصل به h
فصل 21. نمودارهای مسطح
خواص اساسی
تعمیم
اضافات
I. تئوری عمومی، بازی ها
II. درباره وظایف حمل و نقل
III. در مورد استفاده از مفاهیم بالقوه در شبکه های حمل و نقل
IV. مشکلات حل نشده و فرضیات اثبات نشده
V. در مورد برخی از اصول اولیه شمارش (J. Riguet)
VI. اضافات به ترجمه روسی (A.A. Zykov و G.I. Kozhukhin)
ادبیات
نظریه گراف و کتاب سی برژ (پس‌گفتار ترجمه روسی)
شاخص شخصیت
فهرست نام
نمایه موضوعی

دانلود رایگان کتاب الکترونیکیدر قالبی مناسب، تماشا کنید و بخوانید:
دانلود کتاب نظریه گراف و کاربردهای آن Berge K. - fileskachat.com دانلود سریع و رایگان.

دانشگاه علوم تربیتی دولتی ولادیمیر

خلاصه

"نظریه گراف"

انجام:

Zudina T.V.

ولادیمیر 2001

1. معرفی

2. تاریخچه پیدایش نظریه گراف

3. تعاریف اساسی نظریه گراف

4. قضایای اساسی نظریه گراف

5. مسائل مربوط به کاربرد نظریه گراف

6. کاربرد نظریه گراف در درس ریاضی مدرسه

7. کاربرد نظریه گراف در زمینه های مختلف علم و فناوری

8. پیشرفت های اخیر در نظریه گراف

§1. تاریخچه ظهور نظریه گراف.

بنیانگذار نظریه گراف را ریاضیدان لئونارد اویلر (1707-1783) می دانند. تاریخچه این نظریه را می توان از طریق مکاتبات این دانشمند بزرگ ردیابی کرد. در اینجا ترجمه ای از متن لاتین است که از نامه اویلر به ریاضیدان و مهندس ایتالیایی مارینونی، که از سنت پترزبورگ در 13 مارس 1736 ارسال شده است، گرفته شده است [نگاه کنید به. ص 41-42]:

"یک بار از من مشکلی در مورد جزیره ای در شهر کونیگزبرگ پرسیده شد که توسط رودخانه ای احاطه شده است که در آن هفت پل پرتاب می شود. سوال این است که آیا کسی می تواند به طور مداوم آنها را دور بزند و فقط یک بار از هر پل عبور کند." اطلاع داد که هنوز کسی نتوانسته این کار را انجام دهد، اما هیچ کس ثابت نکرده است که غیرممکن است. برای حل آن کافی است... پس از فکر کردن، قاعده آسانی را بر اساس یک دلیل کاملاً قانع کننده یافتم که با کمک آن می توان بلافاصله در همه مشکلات از این دست تعیین کرد که آیا می توان چنین انحرافی را از طریق هر یک انجام داد. تعداد پل هایی که به هر شکلی قرار گرفته اند یا نه به طوری که در شکل زیر می توان آنها را نشان داد[عکس. 1] ، که در آن آ دلالت بر جزیره دارد و ب , سی و د - قسمت هایی از قاره که توسط شاخه های رودخانه از یکدیگر جدا شده اند. هفت پل با حروف مشخص شده اند آ , ب , ج , د , ه , f , g ".

(شکل 1.1)

اویلر در مورد روشی که برای حل مسائل از این دست کشف کرد، نوشت [نگاه کنید به. ص 102-104]:

این راه‌حل، از نظر ماهیت، ظاهراً ربطی به ریاضیات ندارد، و من نمی‌دانم چرا باید این راه‌حل را از یک ریاضیدان انتظار داشت تا از هر شخص دیگری، زیرا این تصمیم تنها با استدلال پشتیبانی می‌شود و هیچ وجود ندارد. برای یافتن این راه حل، هر قانون ذاتی در ریاضیات باید مداخله کرد. بنابراین، من نمی دانم چگونه معلوم می شود که سؤالاتی که ارتباط بسیار کمی با ریاضیات دارند، توسط ریاضیدانان بیشتر از دیگران حل می شوند."

بنابراین آیا می توان تنها با یک بار عبور از روی هر یک از این پل ها، پل های کونیگزبرگ را دور زد؟ برای یافتن پاسخ، نامه اویلر به مارینونی را ادامه می دهیم:

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

دلیل قاعده فوق را می توان در نامه ای از L. Euler به دوستش Ehler در تاریخ 3 آوریل همان سال یافت. در ادامه گزیده ای از این نامه را بازگو می کنیم.

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

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

مسئله شماره 569. هفت جزیره روی دریاچه وجود دارد که همانطور که در شکل 1.2 نشان داده شده است به یکدیگر متصل هستند. یک قایق باید مسافران را به کدام جزیره ببرد تا از هر پل فقط یک بار عبور کنند؟ چرا نمی توان مسافران را به جزیره منتقل کرد؟ آ ?

(شکل 1.2)

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

در خاتمه، متذکر می شویم که مسئله پل های کونیگزبرگ و مسائل مشابه، همراه با مجموعه ای از روش ها برای مطالعه آنها، شاخه بسیار مهمی از ریاضیات را از نظر عملی تشکیل می دهند که نظریه گراف نامیده می شود. اولین کار بر روی نمودارها متعلق به L. Euler بود و در سال 1736 ظاهر شد. متعاقباً، کونیگ (1774-1833)، همیلتون (1805-1865)، و ریاضیدانان مدرن C. Berge، O. Ore، A. Zykov روی نمودارها کار کردند.

§2. قضایای اساسی نظریه گراف

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

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

این تعریف را می توان به صورت متفاوتی بیان کرد: شمردنمجموعه ای از نقاط غیر خالی نامیده می شود ( قله ها) و بخش ها ( دنده، که هر دو انتهای آن متعلق به یک مجموعه معین از نقاط است (شکل 2.1 را ببینید).

(شکل 2.1)

در ادامه، رئوس نمودار را مشخص می کنیم با حروف لاتین آ , ب ,سی ,D. گاهی اوقات نمودار به عنوان یک کل با یک حرف بزرگ نشان داده می شود.

تعریف 2.02.رئوس نمودارهایی که به هیچ یالی تعلق ندارند نامیده می شوند جدا شده .

تعریف 2.03.نموداری که فقط از رئوس جدا شده تشکیل شده باشد نامیده می شود صفر - شمردن .

تعیین: O " - نموداری با رئوس که لبه ندارد (شکل 2.2).

(شکل 2.2)

تعریف 2.04.نموداری که در آن هر جفت رئوس با یک یال به هم متصل شده باشد نامیده می شود کامل .

تعیین: U " – نمودار متشکل از nرئوس و یال هایی که تمام جفت های ممکن این رئوس را به هم متصل می کنند. چنین نموداری را می توان به صورت نمایش داد n- مثلثی که تمام قطرها در آن رسم شده اند (شکل 2.3).

(شکل 2.3)

تعریف 2.05. درجه قله هاتعداد یال هایی است که یک راس به آن تعلق دارد.

تعیین: پ (آ) – درجه راس آ . به عنوان مثال، در شکل 2.1: پ (آ)=2, پ (ب)=2, پ (سی)=2, پ (D)=1, پ (E)=1.

تعریف 2.06.تعداد، درجات از همه ککه رئوس آن یکسان باشد نامیده می شود همگن شمردن درجه ک .

شکل 2.4 و 2.5 نمودارهای همگن درجه دوم و سوم را نشان می دهد.

(شکل 2.4 و 2.5)

تعریف 2.07. مکمل داده شده نمودارنموداری است متشکل از تمام یال ها و انتهای آنها که باید به گراف اصلی اضافه شود تا یک نمودار کامل به دست آید.

شکل 2.6 نمودار اصلی را نشان می دهد جی , متشکل از چهار راس و سه بخش و در شکل 2.7 - مکمل این نمودار - نمودار جی " .

(شکل 2.6 و 2.7)

می بینیم که در شکل 2.5 دنده هایی وجود دارد A.C.و BDدر نقطه ای قطع می شوند که راس نمودار نیست. اما مواردی وجود دارد که یک گراف معین باید در یک صفحه نمایش داده شود به گونه ای که لبه های آن فقط در رئوس متقاطع شوند (این موضوع به طور مفصل در پاراگراف 5 مورد بحث قرار خواهد گرفت).

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

به عنوان مثال، شکل 2.8 یک نمودار مسطح را نشان می دهد که هم شکل (برابر) با نمودار در شکل 2.5 است. با این حال، توجه داشته باشید که هر نمودار مسطح نیست، اگرچه برعکس آن صادق است، یعنی هر نمودار مسطحی را می توان به شکل معمول نشان داد.

(شکل 2.8)

تعریف 2.09.چند ضلعی از یک گراف مسطح که شامل هیچ رئوس یا لبه ای از گراف نباشد نامیده می شود حاشیه، غیرمتمرکز .