سخنرانی 4. نمودارها

4.1. نمودارها. تعریف، انواع نمودارها

4.2. خواص نمودارها

مفاد برنامه

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

به راحتی و امکان استفاده گسترده از نمودارها در مسائل کاربردی توجه کنید

ادبیات

سوالات امنیتی

1. گراف چیست؟
2. راس و یال گراف به چه چیزهایی گفته می شود؟

3. آیا می توان این نمودار را بدون بلند کردن مداد و بدون دو بار عبور از هیچ لبه ای ردیابی کرد؟

1. آیا مجموع درجات رئوس یک نمودار می تواند یک عدد فرد باشد؟
2. آیا می توان یک تورنمنت بین 11 تیم برگزار کرد که هر تیم دقیقاً 5 مسابقه انجام دهد؟

6. معادل بودن تعاریف پاراگراف 4.1.(6) را نشان دهید (که آنها یک شی را توصیف می کنند)

7. نشان دهید که نمودارها هم شکل هستند

8. نشان دهید که ایزومورفیسم یک رابطه هم ارزی در نمودارها است.

9. حداقل تعداد قطعاتی که یک تکه سیم باید به چند قسمت تقسیم شود تا بتوان از آن برای ساخت قاب مکعبی استفاده کرد؟

10. نشان دهید که نمودار مسطح است

نمودارها تعریف، انواع نمودارها

پدر نظریه گراف L. Euler A707-1782 است که در سال 1736 مسئله ای را حل کرد که در آن زمان به طور گسترده ای شناخته شده بود، به نام مشکل پل های کونیگزبرگ.

در شهر کونیگزبرگ دو جزیره وجود داشت که توسط هفت پل به کرانه های رودخانه پرگولیا و به یکدیگر متصل می شدند، همانطور که در شکل نشان داده شده است. 4.1.(1) (A,D – جزایر, B,C – سواحل رودخانه). کار به این صورت بود که از هر چهار قسمت زمین مسیری پیدا کنید که از هر کدام شروع شود، به همان قسمت ختم شود و دقیقاً یک بار از روی هر پل بگذرد. البته، تلاش برای حل تجربی این مشکل، جستجو در همه مسیرها، آسان است، اما همه تلاش ها با شکست به پایان می رسد. ال اویلر با اثبات غیرممکن بودن چنین مسیری توانست راه حلی برای این مشکل بیابد.

اویلر برای اثبات اینکه مشکل راه حلی ندارد، هر قسمت از زمین را با یک نقطه (راس) و هر پل را با یک خط (لبه) که نقاط مربوطه را به هم متصل می کند، تعیین کرد. نتیجه یک "گراف" است. این نمودار در شکل نشان داده شده است. 4.1.(2)، که در آن نقاط

با حروف مشابه چهار تکه سوشی در شکل مشخص شده اند. 4.1 (1). بیانیه در مورد عدم وجود راه حل "مثبت" برای این مشکل معادل عبارت در مورد عدم امکان عبور از نمودار ارائه شده در شکل 1 به روشی خاص است. 4.1 (2).

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

مثال دیگری از مسئله ای که می توان با استفاده از تئوری گراف مدل کرد، مسئله تامین سه خانه با سه نوع تاسیسات است. با توجه به این مشکل، هر یک از این سه خانه باید از طریق خطوط لوله و کابل زیرزمینی به سه نوع تاسیسات مانند آب، گاز و برق متصل شوند. سوال اینجاست که آیا می توان بدون عبور از خطوط تامین آب و برق این سه خانه را تامین کرد؟ نمودار مدل سازی این مشکل در شکل نشان داده شده است. 4.1 (3) (این مسئله مدل معروف گاهی اوقات به عنوان مسئله خانه ها و چاه ها فرموله می شود)

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

تعریف 4.1 (1)

گراف یک مجموعه محدود V است که مجموعه رئوس نامیده می شود و یک مجموعه E از زیر مجموعه های دو عنصری مجموعه V است. مجموعه E را مجموعه یال ها می نامند. عنصری از مجموعه E لبه نامیده می شود. نمودار با G(V, E) نشان داده می شود. عناصر a و b از مجموعه V را متصل می نامند یا با یک یال (a, b) متصل می شوند، اگر .

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

نمونه هایی از نمودارها نقشه مترو، شجره نامه، نقشه راه و غیره هستند.

تعاریف 4.1 (2)

اگر (a، b) یک یال باشد، رئوس a و b انتهای یال (a, b) نامیده می شوند. لبه (a, b) نیز نامیده می شود اتفاقیبه رئوس a و b. برعکس، می گوییم که رئوس a و b به لبه (a, b) برخورد می کنند. دو قله نامیده می شود مجاور (همسایه)، اگر انتهای یک یال باشند، یا اگر به یک یال برخورد کنند، چه هستند. اگر دو یال به یک راس مشترک برخورد کنند، گفته می شود که مجاور یکدیگر هستند.

اگر چندین یال بین دو نقطه مجاز باشد، نمودار فراخوانی می شود چند گراف

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

نموداری با یک راس و بدون یال (متشکل از 1 نقطه - یک راس) نامیده می شود. ناچیز.

تعریف 4.1 (3)

درجه یک راس v با deg(v) نشان داده می شود، که تعداد یال هایی است که به این راس (که از آن نشأت می گیرد) برخورد می کند.

راس درجه 0 (یعنی هیچ لبه ای از راس خارج نمی شود، این یک نقطه "تنها" است) ایزوله نامیده می شود.

راس درجه 1 را رأس آویزان می نامند.

رئوس می توانند زوج یا فرد باشند.

تعاریف 4.1. (4)

مسیر (بین رئوس) - دنباله ای از یال ها و رئوس میانی که آنها را به هم متصل می کند.

طول مسیر - تعداد لبه های موجود در مسیر

مسیر ساده مسیری است که در آن تمام یال ها و رئوس متمایز هستند

چرخه (حلقه) یک مسیر بسته با طول غیر صفر است که در آن همه رئوس متفاوت هستند به جز ابتدا که با انتها منطبق است.

مثال 4.1 (1).

1. نموداری با مجموعه ای از رئوس V = (a,b,c) و مجموعه ای از یال های E ((a, b, (b, c)) را می توان همانطور که در شکل 4.1(4) نشان داده شده است (ساده) نشان داد. ) مسیر بین رئوس a و c شامل یال های (a,b), (b,c) و راس c می باشد.

توجه: هر دو تصویر وضعیت یکسانی را نشان می دهند. از نظر نمودارها، آنچه در ابتدا اهمیت دارد، وجود ارتباط بین نقاط است و نه هندسه آن.

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

را می توان با نمودار نشان داده شده در شکل نشان داد. 4.1. (5). نمودار شامل دو چرخه (b، e، a)، (b، c، d) است.

3. در شکل. 4.1.(6) رئوس a و c مجاور هستند و e 1، e 2 و e 3 لبه های مجاور هستند، رئوس a و f مجاور نیستند و e 2 و e 5 لبه های مجاور نیستند. رئوس b، c و d دارای درجه 2 هستند، در حالی که رئوس a و f دارای درجه 3 هستند.

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

در حالت اول، همه رئوس باید دارای درجه زوج باشند، در حالت دوم، همه رئوس باید زوج باشند، به جز ورودی و خروجی.

مثال 4.1.(2)

آیا امکان گذر از نمودار در شکل 1 وجود دارد. 4.1 (4)، بدون پرش یا عبور از هیچ لبه دو بار؟

درجات همه رئوس زوج هستند، به جز رئوس c و j با درجه 3. بر این اساس، تنها مسیر پیمایش مسیری است که رئوس c و j به عنوان شروع و پایان (یا برعکس) است.

در بسیاری از موارد، شما به نمودارهایی نیاز دارید که لبه های آنها اساسا یک خیابان یک طرفه باشد. این بدان معناست که اگر یک یال را از راس a به راس b می‌رود، نمی‌توان آن را از راس b به راس a در نظر گرفت. به عنوان مثال، اگر نمودار جریان نفت را در یک خط لوله مدل کند، و اگر نفت از نقطه a به نقطه b جریان یابد، ما نمی خواهیم که در جهت مخالف، از نقطه b به نقطه a جریان یابد.

تعریف 4.1 (5)

گراف جهت دار یا دیگراف Gکه با G(V, E) نشان داده می شود شامل یک مجموعه V از رئوس و یک مجموعه E از جفت های مرتب شده از عناصر از Y است که اگر مشخص باشد که گراف جهت دار است، مجموعه یال های جهت دار یا به سادگی یال نامیده می شود. عنصری از مجموعه E لبه جهت دار نامیده می شود. اگر a را رأس اولیه یال (a, b) می نامند، b را رأس نهایی می نامند.

مثال 4.1 (3)

دیگرافی که برای آن V = (a, b, c, d] و E = ((a, b), (b, c), (c, c), (c,d), (d,b),( ج، د)، (د، الف)) در شکل نشان داده شده است.

تعریف 4.1. (6)

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

1) این یک نمودار متصل است که هیچ چرخه ای ندارد (در مورد ویژگی اتصال، به 4.2 مراجعه کنید.)

2) نموداری که در آن هر 2 رأس با یک مسیر ساده به هم متصل شده اند

3) یک نمودار متصل که با حذف هر لبه، اتصال را از دست می دهد

4) نموداری که در آن 1 یال کمتر از رئوس وجود دارد

نمونه هایی از درختان:

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

خواص نمودارها

قضیه 4.2 (1).

مجموع درجات رئوس یک نمودار همیشه زوج است.

اثبات

از آنجایی که هر یال نمودار دارای دو انتهای است، درجه هر انتهای آن به ازای یک یال 1 افزایش می یابد. بنابراین، هر یال 2 واحد به مجموع درجات همه رئوس کمک می کند، بنابراین مجموع باید دو برابر تعداد یال ها باشد. بنابراین، مجموع یک عدد زوج است.

قضیه 4.2.(2)

در هر نمودار تعداد رئوس درجه فرد زوج است.

اثبات

ما برهان را با تناقض انجام می دهیم: با فرض اینکه قضیه صادق نباشد، تناقضی خواهیم یافت که از آن نتیجه می شود که قضیه صادق است. اگر قضیه درست نباشد، تعداد فرد رئوس وجود دارد که درجات آنها فرد است. اما مجموع درجات رئوس با درجه زوج زوج است. مجموع درجات همه رئوس، مجموع درجات رئوس با درجات فرد به اضافه مجموع درجات رئوس با درجه زوج است. از آنجایی که مجموع یک عدد فرد و یک عدد زوج عددی فرد است، مجموع درجات تمامی رئوس فرد است. اما این با قضیه 4.1(1) در تضاد است، بنابراین ما به یک تناقض رسیدیم. بنابراین نتیجه می گیریم که قضیه درست است.

مثال 4.2.(1)

آیا می توان یک تورنمنت فوتبال بین 7 تیم برگزار کرد تا هر تیم دقیقاً 3 مسابقه برگزار کند؟

خیر، زیرا اگر نموداری با 7 راس بسازیم و سعی کنیم از هر رأس 3 یال استخراج کنیم. طبق قضیه 4.2(2)، ساخت چنین نموداری غیرممکن است.

تعریف 4.2 (1).

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

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

توجه داشته باشید که ایزومورفیسم یک رابطه هم ارزی در نمودارها است.

تعاریف 4.2 (2)

نمودار نامیده می شود منسجم، اگر مسیری بین هر دو راس وجود داشته باشد.

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

اتصال x=x(G) یک گراف G کوچکترین تعداد رئوس است که حذف آنها منجر به یک گراف قطع یا بی اهمیت می شود. از تعریف به دست می آید که اتصال یک گراف قطع شده برابر با 0 است و اتصال یک گراف متصل که دارای نقطه اتصال است برابر با 1 است. یک نمودار کامل را نمی توان قطع کرد، مهم نیست که چند رأس از آن حذف شود. آن را

نمودارها

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

شکل 7.1. طرح کونیگزبرگ قدیمی

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

نمودارها و اصطلاحات

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

مدل وظیفه است نمودار،متشکل از بسیاری قله هاو بسیاری دنده هااتصال رئوس رئوس A، B، C و D نماد سواحل رودخانه و جزایر و دنده ها است الف، ج, ج,د,f و gنشان دهنده هفت پل است (شکل 7.2 را ببینید). مسیر مورد نیاز (در صورت وجود) مربوط به پیمودن لبه های نمودار است به گونه ای که هر یک از آنها فقط یک بار پیموده شود. گذر از دنده بدیهی است که مطابق با عبور رودخانه از طریق پل است.

شکل 7.2. مدل مسئله پل کونیگزبرگ

به نموداری که در آن یک مسیر وجود دارد، مسیری وجود دارد که از همان راس شروع و به پایان می رسد و دقیقاً یک بار از تمام لبه های نمودار می گذرد، نامیده می شود. نمودار سیلر.دنباله رئوس (شاید با تکرار) که مسیر مورد نظر مانند خود مسیر از آن می گذرد، نامیده می شود. اویلرین چرخه. اویلر متوجه شد که اگر یک چرخه اویلر در یک نمودار وجود داشته باشد، پس برای هر یال منتهی به یک راس باید یال دیگری وجود داشته باشد که از این راس 1 خارج می شود، و از این مشاهده ساده نتیجه زیر را به دست آورد: اگر یک چرخه اویلر در یک گراف وجود داشته باشد. نمودار داده شده، پس هر راس باید دارای تعداد یال زوج باشد.

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

اکنون کاملاً واضح است که در مدل‌سازی نمودار مسئله پل کونیگزبرگ، یک چرخه اویلر نمی‌تواند پیدا شود. در واقع، درجات تمام رئوس آن فرد هستند: δ(ب) = δ(С)= δ(D) = 3 و δ(الف) = 5. با کمک اویلر، نمودارهایی شبیه به آنچه که ما در هنگام حل مسئله پل ها مطالعه کردیم، در حل بسیاری از مسائل عملی مورد استفاده قرار گرفتند و مطالعه آنها به حوزه قابل توجهی از ریاضیات تبدیل شد.

نمودار سادهبه عنوان جفت G = (V، E)که در آن V مجموعه محدودی از رئوس است، و E- مجموعه ای محدود از لبه ها، و نمی تواند شامل شود حلقه ها(لبه هایی که به یک راس شروع و ختم می شوند) و لبه های متعدد(لبه های متعدد یال های متعددی هستند که یک جفت رئوس را به هم متصل می کنند). نمودار نشان داده شده در شکل. 7.2. ساده نیست، زیرا، برای مثال، رئوس الفو درتوسط دو یال به هم متصل می شوند (این لبه ها هستند که چندتایی نامیده می شوند).

دو قله تو و vدر یک نمودار ساده نامیده می شوند مجاور، اگر با لبه ای به هم وصل شده باشند ه، که درباره آن می گویند که هست اتفاقیراس u (و v ). بنابراین ما می توانیم بسیاری را تصور کنیم Eیال ها به عنوان مجموعه ای از جفت رئوس مجاور، در نتیجه یک رابطه غیر بازتابی و متقارن را در مجموعه تعریف می کنند. V.فقدان انعکاس به این دلیل است که یک نمودار ساده دارای حلقه ها، یعنی لبه هایی است که هر دو انتهای آن در یک راس قرار دارند. تقارن رابطه از این واقعیت ناشی می شود که لبه ه، اتصال رأس وبا vمتصل می کند و vبا و(به عبارت دیگر لبه ها جهت دار نیستند یعنی جهت ندارند). یک یال منفرد در یک نمودار ساده که یک جفت رئوس را به هم متصل می کند تو و vما آن را به عنوان andv(یا vi).

ماتریس منطقی یک رابطه روی مجموعه رئوس یک گراف که با یال های آن تعریف می شود، نامیده می شود. ، ماتریس مجاورت.تقارن یک رابطه بر حسب ماتریس مجاورت M به این معنی است که M متقارن در مورد قطر اصلی. و با توجه به غیر بازتابی بودن این رابطه روی قطر اصلی ماتریس M نماد "L" وجود دارد.

مثال 7.1. رسم نمودار G(V, E) با مجموعه رئوس V = (a، b، c، d، e) و مجموعه ای از لبه های E = (ab, ae, bc, bd, ce, de). ماتریس مجاورت آن را بنویسید.

راه حل. نمودار G در شکل نشان داده شده است. 7.3.

شکل 7.3.

ماتریس مجاورت آن به شکل زیر است:

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

زیرگرافگراف G = (V, E) یک نمودار G’ = (V’, E’) نامیده می شود که در آن E’ C E و V’ C V.

مثال 7.2در میان نمودارهای H، K و L نشان داده شده در شکل. 7.4، زیرگراف های نمودار G.

راه حل.اجازه دهید رئوس نمودارهای G، H و K را همانطور که در شکل نشان داده شده است نشان دهیم. 7.5. همانطور که از علامت گذاری ما پیداست، نمودارهای H و K زیرگراف های G هستند. نمودار L زیرگراف G نیست زیرا دارای راس با شاخص 4 است، در حالی که G ندارد.

مسیرطول ک در نمودار G چنین دنباله ای از رئوس نامیده می شود v 0 , v 1 , …, v ک , که برای هر i = 1، …، k جفت v من – 1 v من یک لبه از نمودار را تشکیل می دهد. ما چنین مسیری را با نشان می دهیم v 0 v 1 … v ک . برای مثال، 1 4 3 2 5 مسیری به طول 4 در نمودار G از مثال 7.2 است.

جی اچ

ک L

شکل 7.4.

چرخهدر یک نمودار مرسوم است که دنباله رئوس را صدا می زنند v 0 , v 1 , … , v ک , که هر جفت آن انتهای یک لبه است و v 0 = v 1 ، و رئوس باقیمانده (و لبه ها) تکرار نمی شوند. به عبارت دیگر چرخه یک مسیر بسته است که تنها یک بار از هر رأس و یال خود می گذرد

1 2 1 2 3

شکل 7.5

مثال 7.3.چرخه ها را در نمودار G از مثال 7.2 بیابید.

راه حل.این نمودار دارای دو چرخه متفاوت به طول 5 است:

1 3 2 5 4 1 و 1 2 5 4 3 1

ما می توانیم این چرخه ها را در یک جهت یا جهت دیگر طی کنیم و از بالای دلخواه چرخه شروع کنیم. علاوه بر این، نمودار دارای سه چرخه مختلف به طول 4 است:

1 2 5 4 1، 1 2 3 4 1 و 2 5 4 3 2،

و دو حلقه به طول 3:

1 2 3 1 و 1 3 4 1.

گرافی که چرخه ندارد نامیده می شود غیر چرخه ایساختارهای درختی که در محاسبات به وجود می آیند یک مورد خاص از نمودارهای غیر چرخه ای هستند. در ادامه این فصل به آنها خواهیم پرداخت.

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

الگوریتم اتصال

فرض کنید G = (V, E) یک نمودار باشد. الگوریتم برای محاسبه مقدار طراحی شده است ج = ج(جی), آن ها تعداد اجزای متصل به یک نمودار معین G.

V' :=V;

در حالی کهV’≠ øانجام دهید

y Є را انتخاب کنید V’

رئوس اتصال مسیر به y را پیدا کنید.

راس را ازV' و

لبه های مربوطه از E.

ج:= ج+1;

مثال 7.4.عملکرد الگوریتم اتصال را در نمودار نشان داده شده در شکل مشاهده کنید. 7.6.

شکل 7.6.

راه حل.جدول را ببینید. 7.1.

جدول 7.1.

مقادیر اولیه	{1,2,3,4,5,6,7,8}
انتخاب y = 1
انتخاب y = 2
انتخاب y = 7

بنابراین، ج(جی) = 3. اجزای متصل مربوطه در شکل نشان داده شده است. 7.7.

5

سوالات کلیدی:

اطلاعاتی از تاریخچه نمودارها. بشمار و
عناصر آن
مسیرها و مسیرها در نمودارها
نمودارهای متصل درختان
عملیات روی نمودارها

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

تاریخچه نمودارها

برای اولین بار مبانی نظریه گراف
در آثار لئونارد ظاهر شد
اویلر (1707-1783;
سوئیسی، آلمانی و
ریاضیدان روسی)
که او راه حل را شرح داد
پازل و ریاضی
وظایف سرگرمی
نظریه گراف با شروع شد
راه حل اویلر برای مشکل
هفت پل
کونیگزبرگ

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

تاریخچه نمودارها

اصطلاح "گراف" برای اولین بار در کتاب ظاهر شد
ریاضیدان مجارستانی D. Koenig در سال 1936، اگرچه
مهمترین قضایای اولیه در مورد نمودارها
به L. Euler برگردید.

این تئوری مبتنی بر مفهوم گراف است.

- مجموعه ای از اعداد متناهی
نقاطی به نام رئوس نمودار، و
به صورت جفتی برخی از اینها را به هم وصل می کند
رئوس خطوط به نام یال یا
کمان های نمودار گاهی اوقات نمودار به عنوان یک کل
را می توان با یک حرف بزرگ نشان داد
نامه
G V , X را یک جفت دو می گویند
مجموعه های محدود: مجموعه نقاط V و
مجموعه ای از خطوط X (لبه ها، قوس ها)،
اتصال چند جفت نقطه

ترکیب نمودار

نمودار شامل رئوس هایی است که با خطوطی به هم متصل شده اند. قله ها
ستون با حروف لاتین A، B، C، D یا مشخص شده است
در اعداد
خط جهت دار (با فلش) کمان نامیده می شود.
خط غیر جهت دار (بدون فلش) لبه نامیده می شود.
خطی که از یک راس مشخص خارج شده و وارد a می شود
به آن حلقه می گویند.
قوس
الف
لبه
در
حلقه
با

نمودار جهت دار -

نموداری که رئوس آن با کمان به هم متصل شده اند. با
با استفاده از چنین نمودارهایی می توان نمایش داد
طرح های روابط یک طرفه
یورا
آنیا
ماشا
کولیا
ویتیا

نمودار وزنی

این نموداری است که لبه ها یا قوس های آن اختصاص داده شده اند
با مقادیر عددی مطابقت دارد (آنها می توانند
برای مثال فاصله بین شهرها را نشان می دهد
یا هزینه حمل و نقل).
وزن یک نمودار برابر است با مجموع وزن یال های آن.
4
ب
سی
2
3
2
الف
1
E
D
الف
ب
سی
D
E
A B C D E
3 1
4
2
3 4
2
1
2 2
جدول (به آن وزن می گویند
ماتریس) با نمودار مطابقت دارد.

اگر
یک لبه از نمودار G دو آن را به هم متصل می کند
رئوس V و W، (یعنی V، W X)، سپس می گویند
که این لبه برای آنها اتفاقی است.
دو رأس یک نمودار مجاور نامیده می شوند،
اگر یک حادثه لبه برای آن وجود داشته باشد: روشن
در شکل، رئوس A و B مجاورند،
A و S.
الف
با
در

اگر نمودار G دارای یالی باشد که مبدأ آن
و انتها منطبق می شوند، سپس این لبه نامیده می شود
حلقه در شکل، لبه q(C, C) یک حلقه است.
q
E
با
الف
D
ب

اگر دو لبه مجاور هم باشند گفته می شود
دارای یک راس مشترک
در شکل، مجاور، به عنوان مثال،
لبه های x1 و x2 با راس مشترک C.
D
x5
x1
اف
با
x4
x2
جی
x7
x3
E
x6
ب
اچ
الف

دنده هایی که در یک و
همان اوج، به همین ترتیب تمام شود
در همان راس نامیده می شوند
چندتایی یا موازی
تعداد جفت های یکسان از نوع
(V , W) کثرت یال (V , W) نامیده می شود.
تعداد یال هایی که به راس A برخورد می کنند است
درجه این راس و
با درجه (A) نشان داده می شود (از درجه انگلیسی -
درجه).

در شکل، مضرب ها به عنوان مثال،
لبه های x1 (A، B)، x2 (A، B). رئوس A و C
لبه های x3، x4، x5 تصادفی هستند. از این رو،
لبه AC دارای تعدد 3 و یال است
AB - تعدد برابر با 2.
الف
x4
x1
x3
با
x2
x5
در

در شکل، راس A دارای درجه است
برابر 1، راس C – 4، راس D – 2.
این به شکل نوشته شده است: deg(A)=1، deg(C)=4،
درجه (D) = 2.
D
x5
x1
اف
با
x4
x2
جی
x7
x3
E
x6
ب
اچ
الف

راس نموداری که دارای درجه صفر است
ایزوله نامیده می شود.
نموداری متشکل از رئوس مجزا
گراف تهی نامیده می شود.
راس نموداری که درجه 1 دارد
به نام حلق آویز کردن
گرافی که لبه ندارد (قوس) نامیده می شود
خالی
E
سی
الف
D
ب
در تصویر بالا
E - جدا شده:
درجه (E) = 0.

در شکل، رئوس A، B، E، G، H آویز هستند.
D
x5
x1
اف
با
x4
x2
جی
x7
x3
E
x6
ب
اچ
الف

قضیه 1. در نمودار G V , X مجموع
درجات تمام رئوس آن یک عدد زوج است،
برابر با دو برابر تعداد یال های نمودار:
n
درجه (V) 2 متر
من 1
من
تعداد یال ها در هر نمودار برابر است
نصف مجموع درجات رئوس آن.
جایی که n V
- تعداد رئوس؛
m X تعداد یال های نمودار است.

راس زوج (فرد) نامیده می شود.
اگر درجه آن یک عدد زوج (فرد) باشد.
در شکل، deg(D)=2، deg(F)=3، یعنی
راس نمودار D زوج است و F است
عجیب و غریب
x5
D
x1
اف
با
x4
x2
جی
x7
x3
E
x6
ب
اچ
الف

وظیفه 15 تلفن در شهر Malenky وجود دارد. آیا می توان آنها را با سیم وصل کرد تا هر گوشی دقیقاً به پنج تا متصل شود

دیگران؟

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

وظیفه 30 نفر در کلاس هستند. آیا ممکن است 9 نفر 3 دوست، 11 نفر 4 دوست و 10 نفر 5 دوست داشته باشند؟

متمم یک گراف G V , X نامیده می شود
نمودار G V , X با همان رئوس V مانند
نمودار G، و داشتن آن و فقط آن یال های X،
که باید به نمودار G اضافه شود تا آن
پر شد در شکل با اضافه کردن نمودار G1 به
نمودار G یک نمودار است
G1
جی
G1
G1

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

الگوی 3.
الگوی 4.
تعداد فرد
غیر ممکن
رئوس هر کدام
ستون یکنواخت است
رسم نمودار با
عدد فرد
رئوس عجیب و غریب

الگوی 5.
الگوی 6.
اگر همه رئوس
نمودار با همه چیز
پس ستون یکنواخت است
بدون پاره کردن آن ممکن است
مداد کاغذی
("با یک ضربه")
کشیدن انگشت روی هر کدام
دنده فقط یکبار
این نمودار را رسم کنید
حرکت امکان پذیر است
با هر کدام شروع کنید
بالا و پایان
او در همان اوج
دو عجیب و غریب
اوج، شما می توانید
قرعه کشی، نه
پاره کردن یک مداد
از کاغذ، در حالی که
حرکت مورد نیاز است
با یکی از
این عجیب و غریب
بالا و پایان
در دومی آنها

الگوی 7.
نموداری که بیشتر دارد
دو عجیب و غریب
قله ها، غیر ممکن
رسم "یک
با شکوفایی." شکل
(گراف)، که می تواند باشد
بدون بلند کردن بکشید
مداد کاغذی،
تماس گرفت
یکنواخت

مسیرها و مسیرها در نمودارها

یک مسیر در یک گراف جهت دار نامیده می شود
دنباله ای از کمان که در آن نهایی
راس هر کمانی غیر از قوس آخر،
راس شروع قوس بعدی است.
قله ای که مسیر از آن کشیده شده است،
به نام ابتدای مسیر، بالا در پایان است
مسیر - انتهای مسیر.
مسیری که در آن از هر رأس استفاده شده است
بیش از یک بار، ساده نامیده می شود
راه
طول یک مسیر در نمودار تعداد کمان ها است
(لبه ها) که این مسیر را تشکیل می دهند.

به عنوان مثال، نمودار را در نظر بگیرید
در شکل ارائه شده است. یکی از موجود
مسیرهای اتصال رئوس 1 و 3 است
دنباله رئوس 1، 2، 1، 4، 3. تنها یکی
یک مسیر ساده برای یک جفت رئوس است
دنباله 1، 4، 3. مسیرها از راس 1 تا
راس 5 برای یک گراف وجود ندارد.

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

یک مسیر اگر بسته نامیده می شود
رئوس شروع و پایان یکسان است.
یک مسیر بسته را یک چرخه می گویند اگر همه
رئوس آن (به جز رئوس اولیه و پایانی)
متفاوت هستند.
نمودار را در نظر بگیرید. برای او مسیر 2، 1، 6، 5، 4، 1 است،
2 بسته است؛ و مسیر 1، 6، 5، 4، 1 است
یک چرخه است

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

در شکل HCDFD مسیری به طول 4 است.
نامگذاری: |HCDFD|=4. مسیر پذیرفته شد
بپرسید
چگونه
دنباله
دنده ها،
از آنجایی که وقتی چندتایی وجود دارد این راحت است
دنده ها
X
D
x1
5
اف
با
x4
x2
جی
x7
x3
E
x6
ب
اچ
الف

در نمودار شکل (t، s، p، r)، (u، s، t، r) چرخه ها هستند
طول 4، (r، t، q، s، u) - طول چرخه 5، (t، s، u، r، t، s، p، r)
– 8 چرخه، (p، u) – 2 چرخه، حلقه (q) – 1 چرخه.
E
q
سی
س
الف
ص
تی
D
r
ب
تو

عملیات روی نمودارها

عملیات تک
1. حذف یک لبه از نمودار - در این مورد، تمام رئوس نمودار
ذخیره می شوند
2. اضافه کردن یک یال نمودار بین دو
قله های موجود
3. حذف یک راس (همراه با حادثه
دنده ها).
4. اضافه کردن یک راس (که می توان به
برخی از رئوس نمودار).
5. انقباض یک یال - شناسایی یک جفت رئوس، i.e.
حذف یک جفت رئوس مجاور و اضافه کردن یک راس جدید
رئوس مجاور آن رئوس که بودند
در مجاورت حداقل یکی از رئوس از راه دور)
6. تقسیم یک یال با - حذف یک یال و اضافه کردن
یک راس جدید که توسط یک یال به هر یک از آنها متصل است
رئوس یک لبه راه دور

عملیات روی نمودارها

عملیات دوگانه
با ترکیب نمودارهای G1 (V1, X 1) و G2 (V2, X 2)
به نام نمودار G G1 G2، مجموعه ای از رئوس
که V V1 V2 و مجموعه لبه ها X X 1 X 2 است.
تقاطع نمودارهای G1 و G2 نامیده می شود
نمودار G G1 G2 که برای آن X X 1 X 2 مجموعه یال ها است و V V1 V2 مجموعه رئوس است.
به مجموع حلقه دو نمودار، گراف می گویند
G G1 G2 توسط مجموعه ای از رئوس ایجاد می شود
آن ها
V V1 V2 و مجموعه ای از لبه ها (X1 X 2) \ (X1 X 2)
مجموعه ای از لبه های موجود در G1 یا در
G2، اما نه در G1 G2.

V4
V2
x3
x2
V3
x4
V1
x1
V5
x2
x7
x3
x4
x4
V1
x7
V1
G=G1UG2
V3
x4
V5
x2
V1
x3
G=G1∩G2
V2
x1
G2
V4
V2
x5 x6
x6
V3
V1
V4
V3
V4
x5
x3
x1
G1
V2
V5
V2
V4
x5 x6 ولت
3
x7
G=G1 G2

کاربرد نمودارها

با
با کمک
نمودارها
ساده شده
مسائل ریاضی، پازل،
نبوغ
راه حل
وظایف برای
بیشتر

کاربرد نمودارها

هزارتو یک نمودار است. و کاوش در آن یافتن آن است
مسیر در این نمودار
بیشتر

از نمودارها و
اشراف
شکل نشان می دهد
بخشی از شجره نامه
درخت
معروف
خانواده نجیب L.N.
تولستوی. اینجاست
رئوس اعضای این هستند
مهربان، و کسانی که آنها را به هم متصل می کنند
بخش ها - روابط
خویشاوندی،
منجر از والدین به
کودکان
بیشتر

کاربرد نمودارها

نمودارها بلوک دیاگرام های برنامه ها هستند
کامپیوتر.
بیشتر

کاربرد نمودارها

نمودارهای معمولی در
نقشه های جغرافیایی هستند
تصاویر راه آهن
بیشتر

کاربرد نمودارها

نمودارهای معمولی در نقشه شهر
الگوهای ترافیک شهری هستند
حمل و نقل
بیشتر

نتیجه گیری

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

نمودارهای کاملاً قطع شده . گرافی که بسیاری از یال های آن خالی باشد نامیده می شود کاملا نامنسجم(یا خالی) نمودار.یک نمودار کاملاً جدا شده با n راس را با N n نشان خواهیم داد. N 4 در شکل نشان داده شده است. 1. توجه داشته باشید که دردر یک گراف کاملاً جدا شده، همه رئوس جدا شده اند. نمودارهای کاملاً جدا شده از اهمیت خاصی برخوردار نیستند.

نمودارهای کامل . گراف ساده ای که در آن هر دو رأس مجاور هم باشند نامیده می شود نمودار کاملیک نمودار کامل با n راس معمولا با نشان داده می شود. نمودارها و در شکل نشان داده شده است. 2 و 3. دقیقاً n (n - 1)/2 یال دارد.

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

نمودارهای افلاطونی . در میان نمودارهای منظم، نمودارهای به اصطلاح افلاطونی بسیار جالب هستند - نمودارهایی که از رئوس و لبه های پنج چند وجهی منظم تشکیل می شوند - جامدات افلاطونی: چهار وجهی، مکعب، هشت وجهی، دوازده وجهی و ایکو وجهی. نمودار مربوط به چهار وجهی است (شکل 2). نمودارهای مربوط به مکعب و هشت وجهی در شکل نشان داده شده است. 5 و 6;

نمودارهای دوبخشی . فرض کنید مجموعه رئوس نمودار را می توان به دو زیرمجموعه مجزا V 1 و V 2 تقسیم کرد، به طوری که هر یال در G مقداری راس از V 1 را به راس V 2 متصل می کند (شکل 7).

سپس G یک گراف دو بخشی نامیده می شود. اگر کسی بخواهد دو زیرمجموعه مشخص شده را از هم متمایز کند، گاهی اوقات به چنین نمودارهایی G(V 1, V 2) نشان داده می شود. یک نمودار دوبخشی را می توان به روش دیگری نیز تعریف کرد - از نظر رنگ آمیزی رئوس آن با دو رنگ، مثلاً قرمز و آبی. یک گراف دو قسمتی نامیده می شود که هر یک از رئوس آن را بتوان قرمز یا آبی رنگ کرد به طوری که هر یال یک انتهای آن قرمز و دیگری آبی باشد. باید تاکید کرد که در یک گراف دوبخشی لازم نیست که هر رأس در V 1 به هر رأس در V 2 متصل باشد. اگر اینطور است و اگر نمودار G ساده باشد، آن را فراخوانی می کنند نمودار دو بخشی کاملو معمولا با جایی که m، n تعداد رئوس در V 1 و V 2 است نشان داده می شود. به عنوان مثال، در شکل. 8 نمودار K 4، 3 را نشان می دهد. توجه داشته باشید که نمودار دقیقاً دارای m + n راس و mn یال است. یک گراف دو بخشی کامل از فرم، گراف ستاره ای نامیده می شود. در شکل 9 نمودار ستاره ای را نشان می دهد.

نمودارهای متصل . نمودار متصل،اگر نتوان آن را به صورت اتحاد دو نمودار نشان داد، و نامنسجمدر غیر این صورت. بدیهی است که هر گراف قطع شده G را می توان به صورت اتحادیه ای از تعداد محدودی از نمودارهای متصل نشان داد - هر یک از این نمودارهای متصل نامیده می شود. جزء (اتصال)نمودار G. (شکل 10 نموداری با سه مؤلفه را نشان می دهد.) اغلب ساده است که عبارات خاصی را برای نمودارهای دلخواه ابتدا برای نمودارهای متصل اثبات کنیم و سپس آنها را برای هر مؤلفه جداگانه اعمال کنیم.

یک نمودار گراف متشکل از رئوس "ایزوله" نامیده می شود نمودار صفر. (شکل 2)

گراف هایی که تمام یال های ممکن در آنها ساخته نشده اند نامیده می شوند نمودارهای ناقص. (شکل 3)

گراف هایی که تمام یال های ممکن در آنها ساخته شده اند نامیده می شوند نمودارهای کامل. (شکل 4)


اگر فلش هایی در لبه های نمودار وجود داشته باشد که جهت یال ها را نشان می دهد، چنین نموداری نامیده می شود. کارگردانی کرد.

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

شما نمی توانید نصب دیوارها را بدون اتمام ساخت فونداسیون شروع کنید، برای شروع به پایان رساندن، باید روی کف ها آب داشته باشید و غیره.

درجات رئوس و شمارش تعداد یال ها.

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

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

شکل 5 نموداری با پنج رأس را نشان می دهد.

درجه راس A با St.A نشان داده می شود.

در تصویر:
St.A = 1، St.B = 2، St.B = 3، St.G = 2، St.D = 0.

اجازه دهید برخی از نظم های ذاتی در نمودارهای خاص را فرموله کنیم.

الگوی 1.درجات رئوس یک نمودار کامل یکسان است و هر کدام از آنها 1 کمتر از تعداد رئوس این نمودار است.

الگوی 2.مجموع درجات رئوس یک نمودار عددی زوج برابر با دو برابر تعداد یال های نمودار است.

این الگو نه تنها برای یک نمودار کامل، بلکه برای هر نموداری نیز صادق است.

تعداد رئوس فرد در هر نمودار زوج است.

توجه داشته باشید که اگر یک نمودار کامل n رأس داشته باشد، تعداد یال ها برابر با n(n-1)/2 خواهد بود.

نموداری که کامل نیست را می توان با اضافه کردن یال های از دست رفته با همان رئوس کامل کرد. به عنوان مثال، شکل 3 یک نمودار ناقص با پنج رأس را نشان می دهد. در شکل 4، یال هایی که گراف را به یک گراف کامل تبدیل می کنند، با رنگی متفاوت به مجموعه رئوس نمودار با این یال ها، مکمل گراف می گویند.

نمودارهای اویلر

نموداری را که بتوان بدون برداشتن مداد از روی کاغذ رسم کرد نامیده می شود اویلرین. (شکل 6)

این نمودارها به نام دانشمند نامگذاری شده اند لئونارد اویلر.


الگوی 3.(از قضیه ای که در نظر گرفتیم نتیجه می گیرد).
رسم نمودار با تعداد فرد رئوس غیرممکن است.

الگوی 4.اگر تمام رئوس نمودار زوج باشند، می توانید این نمودار را بدون برداشتن مداد از روی کاغذ ("با یک ضربه") بکشید و فقط یک بار در امتداد هر لبه حرکت کنید. حرکت می تواند از هر راس شروع شود و به همان راس ختم شود.

الگوی 5.نموداری با تنها دو رأس فرد را می توان بدون برداشتن مداد از روی کاغذ رسم کرد و حرکت باید از یکی از این رأس های فرد شروع شود و در رأس دوم آنها به پایان برسد.

الگوی 6.نموداری با بیش از دو رأس فرد را نمی توان رسم کرد. با یک ضربه».

شکل (گراف) که بدون برداشتن مداد از روی کاغذ قابل رسم است نامیده می شود یکنواخت.

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

شکل 7 به وضوح یک نمودار قطع شده را نشان می دهد.

نمودار نامیده می شود نامنسجم، در صورت عدم رعایت این شرط.

اگر مثلاً در شکل یک یال بین رئوس D و E رسم کنید، نمودار به هم متصل می شود. شکل 8)

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

نمونه هایی از پل های روی شکل 7لبه‌های DE، A3، VZh و غیره می‌توانند خدمت کنند، که هر کدام رئوس بخش‌های «ایزوله» نمودار را به هم متصل می‌کنند. ( شکل 8)

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

یک گراف اویلری است اگر و فقط اگر متصل باشد و حداکثر دو راس فرد داشته باشد.

درختان

درختهر گراف متصلی که چرخه نداشته باشد نامیده می شود.

چرخهمسیری است که در آن ابتدا و انتهای آن بر هم منطبق است.

اگر همه رئوس یک چرخه متفاوت باشند، چنین چرخه ای نامیده می شود ابتداییچرخه (یا ساده).

اگر یک چرخه یک بار تمام یال های نمودار را شامل شود، چنین چرخه ای نامیده می شود خط اویلر (شکل 9a).

در ستون در شکل 9bدو چرخه: 1-2-3-4-1 و 5-6-7-5.

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

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

بالا آویزانیک راس است که دقیقا یک یال از آن بیرون می آید ( شکل 10).
(قله های آویزان دایره ای هستند).


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

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

هر لبه درخت یک پل است.

در واقع، پس از حذف هر لبه درخت، آن را " متلاشی می شود"روی دو درخت

نموداری که در آن هر دو رأس دقیقاً توسط یک مسیر ساده به هم متصل شده باشند درخت.

(در مورد قسمت بالای آویزان). هر درختی یک بالای آویزان دارد.

. در یک درخت، تعداد رئوس یک بیشتر از تعداد یال ها است.

ایزومورفیسم. نمودارهای مسطح و قضیه اویلر.

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

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


رئوس نمودار اول و دوم را از 1 تا 4 شماره گذاری می کنیم ( شکل 12).


نمودار اول رئوس 1 و 2، 2 و 3، 3 و 4، 1 و 4، 1 و 3، 2 و 4 را به هم متصل می کند. توجه داشته باشید که در نمودار دوم رئوس 1 و 2، 2 و 3، 3 و 4، 1 و 4، 1 و 3، 2 و 4 نیز به هم متصل هستند، بنابراین این نمودارها هم شکل هستند.

برای اینکه بفهمید دو نمودار هم شکل هستند، باید مطمئن شوید که دارای:

• همان تعداد رئوس
• اگر رئوس یک گراف با یک یال به هم متصل شوند، رئوس مربوط به گراف دیگر نیز توسط یک یال به هم متصل می شوند.

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

اویلر. برای یک نمودار مسطح متصل به درستی، برابری دارد: V-E+F=2، که در آن V تعداد رئوس است، E تعداد یال ها، F تعداد قطعات است (برابری V -E+ F=2 معمولاً فرمول اویلر نامیده می شود).

نموداری که در آن هر رأس به یک یال هر راس دیگر متصل است، نامیده می شود کامل.

پونتریاگین - کوراتوفسکی. یک گراف صاف است اگر و تنها در صورتی که شامل (به معنای توپولوژیکی) یک گراف با شش رأس از نوع «خانه چاه» و یک نمودار کامل با پنج رأس نباشد.

(عمدتاً در مسائل باستانی در مورد خانه ها و چاه ها استفاده می شود که ماهیت آن به روشن شدن این سؤال خلاصه می شود - آیا نمودار مورد نظر صاف است یا خیر. شکل 13)

نمودارهای جهت دار

کلاس های قابل توجهی از مسائل عملی وجود دارد که نمی توان با استفاده از انواع نمودارهایی که قبلاً بحث شد حل کرد.

به عنوان مثال، نقشه راه ها و میادین یک شهر با استفاده از یک نمودار مسطح به تصویر کشیده شده است. اما اگر نیاز به استفاده از این طرح برای تردد در سطح شهر با ماشین داشته باشید و ترافیک در برخی (یا همه) خیابان ها یک طرفه باشد، چه؟

سپس فلش‌هایی که به‌عنوان مثال مستقیماً در لبه‌ها - خیابان‌های نمودار شهر (نمودار) مورد نظر قرار دارند، می‌توانند به هدایت این وضعیت کمک کنند.

به نموداری که در لبه های آن فلش ها وجود دارد، گفته می شود جهت گیری.

نرخ بازدهرأس یک گراف جهت دار، تعداد یال هایی است که این راس برای آنها آغاز است (تعداد یال ها، " بیرون آمدن"از بالا).

درجه ورودیک راس در یک گراف جهت دار تعداد یال هایی است که این راس انتهای آن هاست (تعداد یال ها، " ورودی"به بالا).

بله، روشن است شکل 15یک گراف جهت دار ABCD را نشان می دهد. درجات ورود و خروج برخی از رئوس آن به شرح زیر است:
St.in.A=2، St.out.A=1 St.in.B=2، St.out.B=0 St.in.D=1، St.out.D=3.

یک مسیر در یک گراف جهت دار از راس A1 به راس An، دنباله ای از یال های جهت دار A1A2، A2A3، ...، Аn-1Аn است که در آن انتهای هر یال قبلی با ابتدای یال بعدی منطبق است و هر یال در آن قرار می گیرد. این سکانس فقط یکبار

روشن شکل.15نمونه هایی از مسیرها در یک نمودار جهت دار نشان داده شده است. علاوه بر این، دو مسیر اول ساده هستند - هیچ یک از رئوس بیش از یک بار در آن وجود ندارد. راه سوم ساده نیست، یعنی. از طریق راس G مسیر ". گذشت"دوبار

چرخه هدایت شدهیک مسیر بسته در یک گراف جهت دار نامیده می شود.

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

بنابراین، در شکل 16، مسیرهای A تا D می توانند متفاوت بوده و طول های متفاوتی داشته باشند.
مسیر اول دارای طول 2 است، مسیر دوم - 3،
و سومی 4 است.

طول "کوتاه ترین مسیر" بین دو راس، فاصله بین آنها نامیده می شود. بنابراین فاصله بین رئوس A و D در نمودار شکل 16 2 است. به این صورت نوشته شده است: S(BP)=2.

اگر در یک گراف جهت دار عبور از یک راس به راس دیگر غیرممکن باشد، فاصله بین آنها نامحدود نامیده می شود (که با نماد بی نهایت نشان داده می شود). بنابراین، فاصله بین رئوس B و D نمودار ارائه شده در شکل 17 بی نهایت است: S(DB) = ∞

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