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

آغاز نظریه گراف به اتفاق آرا به سال 1736 نسبت داده می شود، زمانی که L. Euler مشکل پل های Königsberg را که در آن زمان محبوب بود حل کرد. با این حال، این نتیجه تنها نتیجه نظریه گراف برای بیش از صد سال باقی ماند. تنها در اواسط قرن نوزدهم، مهندس برق G. Kirchhoff نظریه درختان را برای مطالعه مدارهای الکتریکی توسعه داد و ریاضیدان A. Cayley در رابطه با توصیف ساختار هیدروکربن ها، مسائل شمارش را برای سه مورد حل کرد. انواع درختان

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

این مقاله به بررسی مسائل مناسب تئوری گراف نمی پردازد، بلکه به بررسی نحوه استفاده از آن در یک درس هندسه مدرسه می پردازد.

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

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

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

موضوع – کار کلاسی و فوق برنامه

اهداف: 1) تعیین ماهیت و محتوای استفاده از نمودارها در یک دوره هندسه مدرسه.

2) یک PMC برای اجرای دروس هندسه در کلاس های 7-9 ایجاد کنید.

موضوع اصلی ساخت یک مدل نمودار برای اثبات قضایای هندسی است.

مبانی نظری:

1. نظریه گراف، که در سال 1736 پدید آمد (لئونارد اویلر (1708-1783)، توسعه سریعی یافت و امروز نیز مرتبط است، زیرا در زندگی روزمرهتصاویر گرافیکی، نمایش های هندسی و سایر تکنیک ها و روش های تجسم به طور فزاینده ای مورد استفاده قرار می گیرند.

1. نظریه گراف در زمینه های مختلف ریاضیات مدرن و کاربردهای متعدد آن استفاده می شود (Lipatov E. P.)

2. نظریه گراف در زمینه هایی از ریاضیات مانند منطق ریاضی، ترکیبات و غیره استفاده می شود.

اهمیت نظری کار در این است که:

شناسایی حوزه های کاربرد نظریه گراف.

استفاده از نظریه گراف برای مطالعه قضایای هندسی و مسائل.

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

در نتیجه این کار موارد زیر ایجاد شد:

نرم افزار و مجموعه روش شناسی برای برگزاری دروس هندسه در پایه های 7-9.

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

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

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

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

بخش تحقیق

بخش 1. مطالعه تاریخچه پیدایش نظریه گراف.

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

"یک بار از من مشکلی در مورد جزیره ای در شهر کونیگزبرگ پرسیده شد که توسط رودخانه ای احاطه شده است که در آن هفت پل پرتاب می شود. سوال این است که آیا کسی می تواند به طور مداوم آنها را دور بزند و فقط یک بار از هر پل عبور کند." اطلاع داد که هنوز هیچ کس نتوانسته است این کار را انجام دهد، اما هیچ کس ثابت نکرده است که غیرممکن است. پس از تفکر بسیار، یک قانون آسان بر اساس یک دلیل کاملاً قانع کننده پیدا کردم که با کمک آن می توان بلافاصله در همه مشکلات از این نوع تعیین کرد که آیا می توان چنین انحرافی را از هر تعداد پل واقع در به هر حال یا نه، به طوری که می توان آنها را در شکل زیر نشان داد که در آن A نشان دهنده جزیره است، و B، C و D قسمت هایی از قاره که توسط شاخه های رودخانه از یکدیگر جدا شده اند. حروف a، b، c، d، e، f، g".

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

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

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

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

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

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

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

مشکل هفت جزیره روی دریاچه وجود دارد که همانطور که در شکل 2 نشان داده شده است به یکدیگر متصل هستند. یک قایق باید مسافران را به کدام جزیره ببرد تا بتوانند از هر پل و فقط یک بار عبور کنند؟ چرا نمی توان مسافران را به جزیره A منتقل کرد؟

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

متعاقباً، کونیگ (1774-1833)، همیلتون (1805-1865)، و ریاضیدانان مدرن C. Berge، O. Ore، A. Zykov روی نمودارها کار کردند.

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

اولین کار در مورد نظریه گراف، متعلق به ریاضیدان معروف سوئیسی ال. اویلر، در سال 1736 ظاهر شد. نظریه گراف در آغاز قرن 19 و 20 انگیزه ای برای توسعه یافت، زمانی که تعداد آثار در زمینه توپولوژی و ترکیب شناسی افزایش یافت. ، که با آن ارتباط تنگاتنگی دارد ، خویشاوندی به شدت افزایش یافت. استفاده از نمودارها در ساخت نمودارهای مدارهای الکتریکی و مدارهای مولکولی آغاز شد. به عنوان یک رشته ریاضی جداگانه، نظریه گراف برای اولین بار در کار ریاضیدان مجارستانی کونیگ در دهه 30 قرن بیستم ارائه شد.

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

بخش 2. انواع اساسی، مفاهیم و ساختار نمودارها.

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

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

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

1 نمودار صفر رئوس نموداری که به آن تعلق ندارند مشکل: Arkady، Boris. ولادیمیر، گریگوری و دمیتری در این جلسه دست دادن را رد و بدل کردند؛ هر کدام یک بار با یکدیگر دست دادند. چند یال وجود دارد را ایزوله می گویند. دست دادن انجام شد؟ وضعیت مربوط به لحظه ای که هنوز دست دادن انجام نشده است، الگوی نقطه نشان داده شده در شکل است.

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

نماد: O" - یک نمودار با رئوس و بدون لبه

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

تعیین: U" - نموداری متشکل از n 10.

رئوس و یال هایی که تمام جفت های ممکن این رئوس را به هم متصل می کنند. چنین نموداری را می توان به صورت یک n-gon نشان داد که در آن تمام قطرها رسم شده اند

3 نمودار ناقص به نمودارهایی که هنوز تمام دست دادن ها کامل نشده اند، دست دادن های A و B، A و D، D و لبه های احتمالی تکان داده شده اند، G، C و D ناقص نامیده می شوند.

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

قله ها

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

ابتدای مسیر، قله در انتهای مسیر -

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

چرخه چرخه ای است که نمی گذرد مثلاً از نقطه A (راس نمودار) به نقطه H از مسیرهای مختلفی می توان رسید: ADGH، AEH، AEFCEH، ABCEH.

از طریق یکی از رئوس نمودار بیش از یک مسیر AEH چه تفاوتی با مسیر AEFCEH دارد؟

بار. زیرا در مسیر دوم دو بار از "چهارراه" در نقطه E بازدید کردیم.

این مسیر طولانی تر از AEH است. مسیر AEH را می توان از مسیر بدست آورد

اگر چرخه شامل تمام لبه‌های AEFCEH باشد، مسیر FCE را از آخرین مسیر «خارج کردن» می‌کند.

یک بار در یک زمان نمودار کنید، پس چنین چرخه ای Route AEH یک مسیر در نمودار است، اما مسیر AEFCEH یک مسیر نیست.

خط اویلر نامیده می شود.

نمودارهای متصل و جدا شده تعیین 1: آیا می توان قاب مکعبی با طول لبه از سیمی به طول 12 dm ساخت؟

آیا دو رأس یک گراف به هم متصل می شوند، 1 dm، بدون اینکه سیم را قطعه قطعه کند؟

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

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

1) وقتی درجه هر راس زوج است (مسیر بسته است)

2) هنگامی که فقط دو راس با درجه فرد وجود دارد.

تعریف 2:

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

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

6 درخت یک درخت هر گراف متصل است، پیوست شماره 1. شجره نامه ژولمورزاوا تومیریس.

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

7 نمودار ایزومورف. نمودارهای نشان داده شده در شکل نیز همین اطلاعات را ارائه می دهند. به چنین نمودارهایی هم شکل (یکسان) می گویند.

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

راه حل: پس از ترسیم هشت مسیر، می توانید مطمئن شوید که نمی توان مسیر نهم را ترسیم کرد که با هیچ یک از مسیرهای ترسیم شده قبلی تلاقی نداشته باشد.

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

الف، ب، ج، 1، 2، 3

شرایط مسئله با خانه ها و چاه ها مطابقت دارد و ما سعی خواهیم کرد ثابت کنیم که مسیر نهم - لبه ای از نمودار که لبه های دیگر را قطع نمی کند - قابل رسم نیست.

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

A1، A2، A3 و B1، B2، VZ (مربوط به مسیرهای خانه های A و B به تمام چاه ها).

نمودار ساخته شده صفحه را به سه منطقه تقسیم می کند: X، Y، Z. راس B بسته به موقعیت آن در صفحه، در یکی از این سه منطقه قرار می گیرد. اگر هر یک از سه حالت "ضربه زدن" راس را در نظر بگیرید

B به یکی از مناطق X، Y یا Z، سپس مطمئن شوید که هر بار یکی از رئوس نمودار 1، 2 یا 3 باشد.

(یکی از چاه ها) برای راس B "غیرقابل دسترسی" خواهد بود (یعنی نمی توان یکی از یال های B1، B2 یا B3 را ترسیم کرد که لبه های موجود در نمودار را قطع نمی کند).

پاسخ به سوال مشکل این خواهد بود: "نه!"

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

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

بنابراین، مفاهیم اساسی نظریه گراف را مرور کردم که بدون آنها اثبات قضایا و در نتیجه حل مسائل غیرممکن است.

نتیجه گیری در مورد کار انجام شده:

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

ترتیب مطالب نظریکمک به درک بصری انواع نمودارها و کاربرد آنها.

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

پیوست شماره 1.

درخت تبارشناسی

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

روش حل.

روش گرافیکی برای حل مشکل

یک راه گرافیکی برای حل مسئله ترسیم "درخت شرایط منطقی" است. "درخت" در قالب یک نقاشی ساده رابطه منطقی بین خویشاوندان را بیان می کند. هر نسل روی درخت مربوط به یک شاخه است.

من شجره خانواده ام را مثال زدم.

بخش 3. کاربرد نظریه گراف.

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

3. 1. کاربرد نمودارها در مسائل هندسی و قضایا.

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

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

روش های راه حل.

اثبات مسئله با استفاده از استدلال

اجازه دهید ABC یک مثلث متساوی الساقین با

B1 A1 پایه AB و نیمسازهای AA1 و BB1.

بیایید ∆АВВ1 و ∆ВАА1 را در نظر بگیریم. آنها ∟В1АВ= دارند

∟A1BA به عنوان زوایای قاعده مثلث متساوی الساقین ∆ABC. ∟АВВ1= ∟А1АВ

A B زیرا AA1 و BB1 نیمسازهای زوایای قاعده یک مثلث متساوی الساقین هستند. AB طرف مشترک است. به معنای

∆АВВ1 = ∆ВАВ1 در امتداد ضلع و دو زاویه مجاور. از تساوی مثلث ها به دست می آید که اضلاع AA1 و BB1 آنها مساوی است.

اثبات مسئله با استفاده از نمودار

اثبات: AA=BB

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

لبه های نمودار پیامدهای منطقی هستند. انتهای نمودار نمودار یک جمله قابل اثبات است.

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

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

3. 2. مجموعه نرم افزاری و روش شناختی.

الف) کتابچه راهنمای معلم.

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

ب) کتاب کار برای دانش آموزان.

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

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

این راهنما برای دانش آموزان پایه های 7-9 مفید است.

ج) کتابچه راهنمای الکترونیکی.

نتایج کار و بحث آنها. این پروژه نتیجه یک مطالعه دو ساله در مورد استفاده از نمودارها در یک درس ریاضی مدرسه است.

ایجاد به صورت برنامه ای – مجموعه روش شناختیو اجرای آن طی:

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

کاربرد نمودارها در اثبات قضایای هندسی و مسائل

در درس هندسه در پایه های هشتم و نهم.

ارائه با یک پروژه در مدرسه علمی و عملیهمایش ها.

نتیجه.

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

1. مزیت اثبات گراف قضایا و حل مسئله نسبت به سنتی، نشان دادن پویایی اثبات قضایا و مسائل است.

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

3. توسعه نرم افزار و مجموعه روش شناختی برای مطالعه هندسه در پایه های 7-9: الف) کتابچه راهنمای معلم. ب) کتاب کار برای دانش آموزان؛ ج) کتابچه راهنمای الکترونیکی برای دانش آموزان پایه های 7-9 مفید است.

نسخه آموزشی

یووکین نیکولای الکسیویچ

شماره LR برای مهر امضا شد

اوخ اد. ل..،.

دانشگاه فنی دولتی ورونژ

394026 Voronezh, Moskovsky Ave. 14

دایرکتوری دیسک مغناطیسی

گروه ریاضیات عالی و مدل سازی فیزیکی و ریاضی

در. یووکین

ریاضیات گسسته قسمت 1. عناصر نظریه گراف

آموزش

در. یووکین

ریاضیات گسسته قسمت 1. عناصر نظریه گراف

آموزش

ورونژ 2004

معرفی

این راهنما را می توان در درس "ریاضیات گسسته" توسط دانشجویان VSTU که در تخصص های زیر تحصیل می کنند استفاده کرد:

090102 – امنیت کامپیوتر;

090105 - ارائه جامع امنیت اطلاعات سیستم های خودکار.

090106 - امنیت اطلاعات سیستم های مخابراتی.

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

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

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

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

V نمودار مشکل فروشنده دوره گرد؛ شمارش نمودارها و نگاشتها. وظایف شدید؛ مشکلات بهینه سازی؛ وظایف جهانی؛ روش شاخه و کران؛ و همچنین مهارت های عملی را در استفاده از مفاهیم فوق توسعه دهید.

هدف از این دوره توسعه دانش نظری، مهارت‌ها و توانایی‌های عملی دانشجویان در زمینه مدل‌سازی فرآیندها و پدیده‌های علوم و فناوری طبیعی است.

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

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

مطالعه گسترده ترین دامنه ممکن از مفاهیم نظریه گراف.

کسب مهارت در حل مسائل آموزشی و عملی؛

استاد روش های بهینه سازی؛

توسعه مهارت در تنظیم و حل مسائل اطلاعاتی، مدل سازی و تجزیه و تحلیل اطلاعات با استفاده از نمودارها.

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

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

1.1. مسائل تئوری گراف.

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

اولین مسائل تئوری گراف مربوط به حل مسائل سرگرمی و معماها بود.

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

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

وظیفه دوم. مشکل سه خانه و سه چاه. سه خانه و سه چاه دارد.

لازم است از هر خانه تا هر چاه مسیری ترسیم شود تا مسیرها با هم تلاقی نکنند. وظیفه بود

توسط پونتریاگین و مستقل از او توسط کوراتوفسکی حل شد

وظیفه سوم. حدود چهار رنگ هر نقشه ای را در یک هواپیما با چهار رنگ رنگ کنید تا هیچ دو ناحیه مجاور با یک رنگ رنگ آمیزی نشوند.

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

1.2. تعاریف اساسی

یک نمودار G= (V,E) مجموعه ای از دو مجموعه است - یک مجموعه غیر خالی از رئوس V و مجموعه ای از جفت های نامرتب و مرتب از رئوس E. در ادامه، نمودارهای متناهی را در نظر خواهیم گرفت، یعنی. نمودارهایی با مجموعه ای محدود از رئوس و خانواده محدودی از جفت ها. به جفت رئوس نامرتب یال و به جفت مرتب شده قوس می گویند.

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

خواص هندسی دنده ها (طول، انحنا)، و همچنین ترتیب متقابلرئوس در هواپیما

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

آنها می گویند که یک یال (u,v) رئوس u و v را به هم وصل می کند و یک کمان (u,v) از رأس u شروع می شود و به رأس v ختم می شود که u ابتدا و v انتهای این کمان می گویند.

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

نمودار بدون حلقه یا چند یال ساده نامیده می شود. گراف ساده اگر برای هر جفت رئوس آن یک یال (قوس) وجود داشته باشد که آنها را به هم متصل می کند، کامل نامیده می شود. یک نمودار کامل با n راس با K n نشان داده می شود. مثلاً اینها نمودارها هستند

نموداری که از یک راس جدا شده (K 1) تشکیل شده باشد، بی اهمیت نامیده می شود.

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

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

1.3. درجات رئوس نمودار.

درجه (ظرفیت) (نشان d (v) یا deg (v)) یک راس v یک نمودار ساده G تعداد یال ها یا کمان هایی است که به یک راس معین v برخورد می کنند. هنگام محاسبه ظرفیت رئوس شبه نگار، هر حلقه باید دو بار شمارش شود.

اگر درجات همه رئوس یک n-گراف برابر با k باشد، گراف فراخوانی می شود منظم (یکنواخت)درجه k اگر درجه یک راس 0 باشد آنگاه جدا می شود. اگر درجه یک راس 1 باشد، آن راس را راس انتهایی (آویز، بن بست) می نامند.

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

متفاوت است نیمه درجه نتیجه				(v) و ورودی - نیمه مرحله ای-

تماس جدید د			(v)، در این مورد رابطه d (v)=

	(v)+	(v).

قضیه اویلر: مجموع درجات رئوس یک نمودار است

دو برابر تعداد دنده ها، یعنی.

d(vi)



			(v)

جایی که n تعداد رئوس است. m - شماره

دنده ها (قوس ها). این بیانیه با این واقعیت ثابت می شود که هنگام محاسبه مجموع درجات رئوس، هر یال دو بار در نظر گرفته می شود - برای یک انتهای لبه و برای دیگری.

1.4. ایزومورفیسم نمودار.

گراف در صورتی برچسب گذاری شده (یا شماره گذاری مجدد) نامیده می شود که رئوس آن به نحوی با یکدیگر متفاوت باشد.

برچسب ها (اعداد). شمارش در نظر گرفته شده است به طور کامل به معنای دقیق داده شده است، اگر شماره رئوس و لبه های آن ثابت باشد. در این مورد، نمودارهای G 1 و G 2 برابر نامیده می شوند (تعریف G 1 = G 2)، اگر مجموعه رئوس و یال آنها منطبق باشند. دو نمودار یا شبه نگار G 1 = (V 1 , E 1 ) و G 2 = ( V 2 , E 2 ) نامیده می شوند.

	هم شکل (نشان G	اگر وجود داشته باشند

	نگاشت یک به یک: 1)	: V 1 V 2
: E 1 E 2 به طوری که برای هر دو راس u، v در نمودار
	رابطه ((u، v)) ((u)، (v)) معتبر است.

	دو نمودار ساده (بدون حلقه و لبه های متعدد) G 1		و G 2

اگر متقابلاً یکسان باشد، هم شکل است

نقشه برداری ارزش

: V 1 V 2

پس چی؟

(u , v ) ((u ), (v )) .

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

انعکاس پذیری -

G1،

و bijection

یک تابع یکسان است.

تقارن.

با دوجکشن

گذرا.

G 1 G 2

دوجکشن

1، a

با دوجکشن

سپس G G

با دوجکشن

2 (1 ) .

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

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

زمینه های اصلی کاربرد نظریه گراف:

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

در علوم کامپیوتر و برنامه نویسی (نمودار نمودار الگوریتم)؛

در سیستم های ارتباطی و حمل و نقل. به ویژه، برای مسیریابی داده ها در اینترنت؛

در اقتصاد؛

در تدارکات؛

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

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

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

نمایش ماتریسی نمودارها ماتریس حادثه

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

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

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

ماتریسی از نوع تعریف شده به این صورت نامیده می شود ماتریس حادثه

نمونه ای از بدست آوردن ماتریس حادثه. برای نمودار نشان داده شده در زیر ( برنج. 2.1 الفشکل 2.1 ب).

شکل 2.1 a شکل. 2.1 ب

ماتریس مجاورت

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

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

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

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

ساختار ماتریسی کارآمدتر نشان دهنده یک نمودار است ماتریس مجاورت راس، یا ماتریس بولینمودار این یک ماتریس مربع از مرتبه B است nکه عناصر آن به شرح زیر تعریف می شود:

برای یک نمودار بدون جهت:

برای یک نمودار جهت دار:

برای نمودار نشان داده شده در زیر ( برنج. 2.2 الف) ماتریس بروز ماتریس ارائه شده در ( شکل 2.2 ب).

متن اثر بدون تصویر و فرمول درج شده است.
نسخه کاملکار در برگه "فایل های کاری" در قالب PDF موجود است

معرفی

"در ریاضیات این فرمول ها نیستند که باید به خاطر بسپارند، بلکه فرآیند تفکر هستند..."

E. I. Ignatiev

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

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

هدف موارد زیر را مشخص کرد وظایف:

با تاریخچه نظریه گراف آشنا شوید.

مطالعه مفاهیم اساسی تئوری گراف و ویژگی های اصلی نمودارها.

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

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

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

موردتحقیق: بخش ریاضیات نظریه گراف.

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

مواد و روش هاکار تحقیقاتی:

در طول تحقیق ما از روش های زیر استفاده شد:

1) کار با منابع مختلف اطلاعات.

2) توصیف، جمع آوری، سیستم سازی مطالب.

3) مشاهده، تجزیه و تحلیل و مقایسه.

4) آماده سازی وظایف.

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

فصل اول. مرور نظری مواد در موضوع تحقیق

در ریاضیات، یک "گراف" را می توان به عنوان یک تصویر ترسیم کرد که نشان دهنده تعدادی از نقاط متصل شده توسط خطوط است. "Count" از کلمه لاتین "graphio" آمده است - من می نویسم، مانند یک عنوان نجیب شناخته شده.

در ریاضیات، تعریف گراف به شرح زیر است:

اصطلاح "گراف" در ریاضیات به صورت زیر تعریف می شود:

نمودار - این مجموعه محدودی از نقاط است - قله ها, که می تواند توسط خطوط متصل شود - دنده .

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

برنج. 1نمونه های نمودار

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

برنج. 2راس نمودار

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

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

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

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

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

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

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

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

حداکثر فاصله ممکن بین هر دو رأس یک نمودار نامیده می شود قطر نمودار

رنگ آمیزی و کاربرد نمودار

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

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

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

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

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

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

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

در سال 1859، ریاضیدان انگلیسی، ویلیام همیلتون، پازلی را منتشر کرد - دوازده وجهی چوبی (دوده وجهی)، که بیست راس آن با گل میخ مشخص شده بود. هر قله نام یکی از بزرگترین شهرهای جهان - کانتون، دهلی، بروکسل و غیره را داشت. وظیفه یافتن یک مسیر بسته بود که در امتداد لبه‌های چند وجهی می‌رود و تنها یک بار از هر رأس بازدید می‌کرد. برای علامت گذاری مسیر از بند ناف استفاده می شد که روی میخ ها قلاب می شد.

چرخه همیلتون گرافی است که مسیر آن یک چرخه ساده است که یک بار از تمام رئوس نمودار می گذرد.

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

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

اویلر در حین حل مسئله پل کونیگزبرگ، توانست خصوصیات نمودارها را فرموله کند.

می توان با شروع از یک راس و پایان دادن به همان راس با یک ضربه (بدون کشیدن دو بار در امتداد یک خط و بدون برداشتن مداد از روی کاغذ) نمودار را در صورتی که همه رئوس نمودار زوج باشند رسم کرد.

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

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

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

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

فصل دوم. شرح مطالعه و نتایج آن

2.1. مراحل مطالعه

برای آزمون فرضیه، پژوهش شامل سه مرحله بود (جدول 1):

مراحل تحقیق

میز 1.

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

2.2. زمینه های کاربرد عملی نمودارها

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

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

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

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

A. Cayley همچنین مشکل ساختارهای احتمالی هیدروکربن های اشباع (یا اشباع) را در نظر گرفت که مولکول های آن با فرمول ارائه شده است:

CnH 2n+2

تمام اتم های هیدروکربن 4 ظرفیتی و همه اتم های هیدروژن 1 ظرفیتی هستند. فرمول های ساختاریساده ترین هیدروکربن ها در شکل نشان داده شده اند.

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

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

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

نمودار و فیزیک

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

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

ریاضیات اینترنتی

اینترنت یک سیستم جهانی از شبکه های کامپیوتری متصل به هم برای ذخیره و انتقال اطلاعات است.

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

نمودار وب (اینترنت) که دارای میلیاردها رأس و لبه است، دائماً در حال تغییر است - سایت ها به طور خود به خود اضافه و ناپدید می شوند، پیوندها ناپدید می شوند و اضافه می شوند. با این حال، اینترنت ساختاری ریاضی دارد، از نظریه گراف پیروی می کند و چندین ویژگی «پایدار» دارد.

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

با وجود پراکندگی اینترنت، اینترنت بسیار شلوغ است. می توانید با استفاده از پیوندها با 5 تا 6 کلیک از یک سایت به سایت دیگر بروید (تئوری معروف "شش دست دادن").

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

جایی که نسبت رئوس درجه معینی است، درجه یک راس است، ثابت مستقل از تعداد رئوس در نمودار وب است، یعنی. در طول فرآیند افزودن یا حذف سایت ها (راس) تغییر نمی کند.

این قانون قدرت برای شبکه های پیچیده - از بیولوژیکی گرفته تا بین بانکی - جهانی است.

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

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

برای مطالعه اینترنت باید یک مدل نمودار تصادفی ساخت. این مدل باید ویژگی های اینترنت واقعی را داشته باشد و خیلی پیچیده نباشد.

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

ساخت مدل های بیولوژیکی و اقتصادی خیلی زودتر از زمانی که کار ساخت یک مدل ریاضی از اینترنت مطرح شد آغاز شد. با این حال، پیشرفت در توسعه و مطالعه اینترنت، پاسخ به بسیاری از سؤالات در مورد همه این مدل ها را ممکن ساخته است.

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

مورمانسک با استفاده از نمودار

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

به عنوان مثال، یک مورد معمولی از ورود به مورمانسک از فرودگاه برای اولین بار را در نظر بگیرید. قصد داریم از جاذبه های زیر دیدن کنیم:

1. کلیسای ارتدکس دریایی نجات دهنده روی آب.

2. کلیسای جامع سنت نیکلاس;

3. Oceanarium;

4. بنای یادبود گربه سمیون;

5. یخ شکن هسته ای لنین;

6. چراغ های پارک مورمانسک;

7. پارک دره آسایش;

8. پل کلا;

9. موزه تاریخ شرکت کشتیرانی مورمانسک.

10. میدان پنج گوشه;

11. بندر تجارت دریایی

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

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

با استفاده از نمودار، می توانید طرح انجام نظرسنجی را نیز تجسم کنید. نمونه هایی در پیوست شماره 2 ارائه شده است. بسته به پاسخ های داده شده، از پاسخ دهنده سوالات مختلفی پرسیده می شود. به عنوان مثال، اگر در نظرسنجی شماره 1 جامعه‌شناختی، پاسخ‌دهنده ریاضیات را مهم‌ترین علوم بداند، از او سؤال می‌شود که آیا در درس فیزیک احساس اطمینان می‌کند؟ اگر او غیر از این فکر کند، سوال دوم مربوط به تقاضا خواهد بود علوم انسانی. رئوس چنین نموداری سؤال است و یال ها گزینه های پاسخ هستند.

2.3. کاربرد نظریه گراف در حل مسئله

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

وظیفه شماره 1.

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

راه حل: بیایید همکلاسی ها را با رئوس نمودار نشان دهیم. بیایید هر راس را با خطوط به چهار راس دیگر متصل کنیم. ما 10 خط دریافت می کنیم، اینها دست دادن هستند.

پاسخ: 10 دست دادن (هر خط به معنای یک دست دادن است).

وظیفه شماره 2.

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

راه حل:

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

جواب: افرا، سیب، کاج اروپایی، روون، کاج، بلوط، توس و صنوبر.

وظیفه شماره 3.

مامان 2 پاکت دارد: معمولی و هوا، و 3 مهر: مربع، مستطیل و مثلث. مامان از چند طریق میتونه یک پاکت و مهر برای ارسال نامه به بابا انتخاب کنه؟

پاسخ: 6 راه

وظیفه شماره 4.

بین شهرک هاجاده های A، B، C، D، E ساخته شده است. نیاز به تعیین طول کوتاه ترین مسیربین نقاط A و E. شما فقط می توانید در جاده هایی که طول آنها در شکل مشخص شده است سفر کنید.

وظیفه شماره 5.

سه همکلاسی - ماکسیم، کریل و ووا تصمیم گرفتند به ورزش بروند و انتخاب بخش های ورزشی را پشت سر گذاشتند. مشخص است که 1 پسر برای بخش بسکتبال درخواست داد و سه نفر می خواستند هاکی بازی کنند. ماکسیم فقط برای بخش 1 تست داد، کریل برای هر سه بخش، و ووا برای بخش 2 انتخاب شد. کدام یک از پسران برای کدام بخش ورزشی انتخاب شدند؟

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

بسکتبال ماکسیم

فوتبال کریل

هاکی ووا

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

وظیفه شماره 6.

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

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

2. معلم جغرافی می تواند درس دوم یا سوم را بدهد.

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

4. معلم فیزیک می تواند درس اول، دوم یا سوم را فقط در یک کلاس ارائه دهد.

مدیر مدرسه چه برنامه ای می تواند ایجاد کند که رضایت همه معلمان را جلب کند؟

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

1. 1) فیزیک 2. 1) ریاضیات 3. 1) ریاضیات

2) ریاضیات 2) فیزیک 2) جغرافیا

3) جغرافیا 3) جغرافیا 3) فیزیک

4) OBZH 4) OBZH 4) OBZH

نتیجه

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

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

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

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

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

فهرست منابع استفاده شده

Berezina L. Yu. "نمودارها و کاربرد آنها" - M.: "روشنگری"، 1979

گاردنر M. "فرارت ریاضی"، M. "میر"، 1972

گاردنر ام. پازل های ریاضیو سرگرمی، م. «میر»، 1350

گورباچف A. "مجموعه مسائل المپیاد" - M. MTsNMO، 2005

Zykov A. A. مبانی نظریه گراف. - م.: کتاب دانشگاهی، 1383. - ص 664

Kasatkin V. N. "مسائل غیرمعمول ریاضیات"، کیف، "مدرسه رادیانسکا"، 1987

جزء ریاضی / ویرایشگرها و کامپایلرها N.N. آندریف، S.P. کونوالوف، ن.ام. پانیوشکین. - م.: بنیاد "اتودهای ریاضی" 2015 - 151 ص.

Melnikov O. I. "مسائل سرگرم کننده در نظریه گراف"، Mn. "TetraSystems"، 2001

ملنیکوف O.I. Dunno in the land of counts: کتابچه راهنمای دانش آموزان. اد. سوم، کلیشه ای. M.: KomKniga، 2007. - 160 ص.

Olehnik S. N.، Nesterenko Yu. V.، Potapov M. K. "مشکلات سرگرم کننده قدیمی"، M. "علم"، 1988

Ore O. "نمودارها و کاربردهای آنها"، M. "Mir"، 1965

Harari F. Graph Theory / ترجمه از انگلیسی. و مقدمه V. P. Kozyreva. اد. G. P. Gavrilova. اد. 2. - M.: Editorial URSS, 2003. - 296 p.

ضمیمه شماره 1

ترسیم مسیر بهینه برای بازدید از جاذبه های اصلی

مورمانسک با استفاده از نمودار

مسیر بهینه این خواهد بود:

8. پل کلا6. چراغ های پارک مورمانسک7. پارک دره راحتی 2. کلیسای جامع سنت نیکلاس 10. پنج گوشه مربع5. یخ شکن هسته ای لنین 9. موزه تاریخ شرکت کشتیرانی مورمانسک 11. بندر تجاری دریایی 1. کلیسای ارتدکس دریایی نجات دهنده در آب 4. بنای یادبود گربه Semyon3. اوشناریوم.

راهنمای جاذبه های مورمانسک

ضمیمه شماره 2

بررسی های جامعه شناختی شماره 1، 2

روش گراف چیست؟

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

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

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

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

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

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

توجه داشته باشید که اگر یک نمودار کامل n رأس داشته باشد، تعداد یال ها برابر خواهد بود

n(n-1)/2

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

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

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

تعداد یال هایی که از یک راس نمودار خارج می شوند نامیده می شود درجه راس. راس نموداری که درجه فرد دارد نامیده می شود فردو حتی مدرک - زوج.

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

شکل 5

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

در شکل: St.A = 1، St.B = 2، St.B = 3، St.G = 2، St.D = 0.

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

الگوی 1.

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

اثبات:

این الگو پس از در نظر گرفتن هر نمودار کامل آشکار است. هر راس با یک یال به هر راس به جز خودش متصل است، یعنی از هر رأس نموداری که n رأس دارد، n-1 یال بیرون می‌آید که باید ثابت شود.

الگوی 2.

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

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

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

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

یک نمودار دلخواه G را در نظر بگیرید. بگذارید تعداد رئوس این نمودار که درجه آنها 1 است برابر با K1 باشد. تعداد رئوس که درجه آنها 2 است برابر با K2 است. ...; تعداد رئوسی که درجه آنها n است برابر با Kn است. سپس مجموع درجات رئوس این نمودار را می توان به صورت نوشتاری نوشت
K1 + 2K2 + ZK3 + ...+ nKn.
از طرف دیگر: اگر تعداد یال های نمودار R باشد، از قانون 2 مشخص می شود که مجموع درجات تمام رئوس نمودار برابر با 2R است. سپس می توانیم برابری را بنویسیم
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
اجازه دهید در سمت چپ تساوی مجموعی برابر با تعداد رئوس فرد نمودار (K1 + K3 + ...) انتخاب کنیم:
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R،
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
براکت دوم یک عدد زوج به عنوان مجموع اعداد زوج است. حاصل جمع (2R) یک عدد زوج است. از این رو (K1 + K3 + K5 +...) یک عدد زوج است.

اکنون مشکلات حل شده با نمودارها را در نظر می گیریم:

وظیفه. قهرمانی کلاس . در مسابقات قهرمانی کلاس تنیس روی میز 6 شرکت کننده حضور دارند: آندری، بوریس، ویکتور، گالینا، دیمیتری و النا. مسابقات قهرمانی به صورت رفت و برگشت برگزار می شود - هر شرکت کننده یک بار با یکدیگر بازی می کند. تا به امروز، برخی از بازی ها قبلاً انجام شده است: آندری با بوریس، گالینا و النا بازی کرد. بوریس، همانطور که قبلا ذکر شد، با آندری و همچنین با گالینا است. ویکتور - با گالینا، دیمیتری و النا؛ گالینا با آندری و بوریس؛ دیمیتری - با ویکتور و النا - با آندری و ویکتور. تا الان چند بازی انجام شده و چند بازی باقی مانده است؟

بحث. بیایید این وظایف را در قالب یک نمودار به تصویر بکشیم. ما شرکت کنندگان را به صورت نقطه به تصویر می کشیم: آندری - نقطه A، بوریس - نقطه B و غیره. اگر دو شرکت‌کننده قبلاً با یکدیگر بازی کرده‌اند، نقاط نشان‌دهنده آنها را با بخش‌هایی به هم متصل می‌کنیم. نتیجه نمودار نشان داده شده در شکل 1 است.

نقاط A، B، C، D، D، E رئوس نمودار و قسمت های متصل کننده آنها لبه های نمودار هستند.

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

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

برای جلوگیری از سردرگمی، رئوس یک نمودار اغلب نه به صورت نقطه، بلکه به صورت دایره های کوچک نشان داده می شود.

برای یافتن تعداد بازی‌هایی که باید انجام شوند، نمودار دیگری با همان رئوس می‌سازیم، اما با یال‌ها، شرکت‌کنندگانی را که هنوز با یکدیگر بازی نکرده‌اند به هم وصل می‌کنیم (شکل 2). این نمودار مشخص شد که دارای 8 لبه، یعنی 8 بازی باقی مانده است: آندری - با ویکتور و دیمیتری. بوریس - با ویکتور، دیمیتری و النا و غیره.

بیایید سعی کنیم یک نمودار برای وضعیت توضیح داده شده در مشکل زیر بسازیم:

وظیفه . چه کسی لیاپکین - تیاپکین را بازی می کند؟ باشگاه نمایش مدرسه تصمیم گرفت نمایش بازرس کل گوگول را روی صحنه ببرد. و سپس بحث شدیدی در گرفت. همه چیز با Lyapkin - Tyapkin شروع شد.

لیاپکین - من تایاپکین خواهم بود! - گنا قاطعانه گفت.

نه، من لیاپکین خواهم بود - تیاپکین، دیما مخالفت کرد - از اوایل کودکی آرزو داشتم این تصویر را روی صحنه زنده کنم.

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

"...و برای من - اوسیپا" دیما با سخاوت به او تسلیم نشد.

ووا گفت: "من می خواهم توت فرنگی یا شهردار شوم."

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

آیا می توان نقش ها را طوری توزیع کرد که مجری ها راضی باشند؟

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

برای حل مشکل باید از ده یال که رئوس مشترک ندارند پنج یال را انتخاب کنید. انجام آن آسان است. توجه به این نکته کافی است که یک یال به ترتیب از رئوس D و B به رئوس 3 و 4 منتهی می شود. این بدان معناست که اوسیپ (راس 3) باید توسط دیما (چه کسی دیگر؟) و Zemlyanichka توسط Vova بازی شود. راس 1 - لیاپکین - تیاپکین - توسط لبه هایی به G و D متصل می شود. لبه 1 - D تسلیم می شود، زیرا دیما از قبل مشغول است، 1 - G باقی می ماند، Lyapkina - Tyapkina باید توسط Gena بازی شود. باقی مانده است که رئوس A و B را با رئوس 2 و 5 مرتبط کنیم که مربوط به نقش های خلستاکوف و گورودنیچی است. این را می توان به دو روش انجام داد: یا لبه A -5 و B - 2 را انتخاب کنید یا لبه A -2 و B -5 را انتخاب کنید. در حالت اول آلیک نقش گورودنیچی و بوریا نقش خلستاکوف را بازی خواهد کرد و در حالت دوم برعکس. همانطور که نمودار نشان می دهد، مشکل راه حل دیگری ندارد.

هنگام حل مسئله زیر همان نمودار به دست می آید:

وظیفه. همسایه های بداخلاق اهالی پنج خانه با یکدیگر نزاع کردند و برای اینکه کنار چاه ها به هم نرسند تصمیم گرفتند آن ها (چاه ها) را تقسیم کنند تا صاحب هر خانه در مسیر «خود» به سمت چاه «خود» برود. آیا آنها قادر به انجام این کار خواهند بود؟

این سوال پیش می آید:آیا واقعاً در مسائل مورد بحث به نمودارها نیاز بود؟آیا نمی توان از راه های کاملا منطقی به راه حل رسید؟ بله، تو میتونی. اما نمودارها شرایط را واضح تر کردند، راه حل را ساده کردند و شباهت مسائل را آشکار کردند و دو مسئله را به یکی تبدیل کردند و این خیلی کم نیست. حال مشکلاتی را تصور کنید که نمودارهای آن ها 100 رأس یا بیشتر دارند. اما دقیقاً چنین مشکلاتی است که مهندسان و اقتصاددانان مدرن باید حل کنند. اینجا نمی توانید بدون نمودار کار کنید.

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

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

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

بیایید سعی کنیم نمودار نشان داده شده در شکل 4 را دایره کنیم با یک ضربهیعنی بدون اینکه مداد را از روی ورق کاغذ بردارید و بیش از یک بار از همان قسمت خط عبور نکنید.

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

در شکل شکل 5 نموداری را نشان می دهد که احتمالاً می دانید چگونه با یک حرکت آن را ترسیم کنید. این یک ستاره است. به نظر می رسد که اگرچه بسیار پیچیده تر از نمودار قبلی به نظر می رسد، اما می توانید آن را با شروع از هر رأسی ردیابی کنید.

نمودارهای ترسیم شده در شکل 6 را نیز می توان با یک ضربه قلم رسم کرد.

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

شما موفق به انجام این کار نشدید! چرا؟ نمی توانید راس مورد نظر خود را پیدا کنید؟ نه! مساله این نیست. این نمودار معمولاً با یک ضربه قلم رسم نمی شود.

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

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

بنابراین، راس A باید گره شروع یا پایان ترسیم باشد.

اما همین را می توان در مورد سه رأس دیگر نمودار ما نیز گفت. اما راس شروع ترسیم فقط می تواند یک راس باشد و راس نهایی نیز می تواند فقط یک راس باشد! یعنی رسم این نمودار با یک ضربه غیرممکن است.

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

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

الگوی 1. (از قضیه ای که در نظر گرفتیم نتیجه می گیرد).

رسم نمودار با تعداد فرد رئوس فرد غیرممکن است.
الگوی 2.

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

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

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

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

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

شکل 7 شکل 8

شکل 7 به وضوح یک نمودار قطع شده را نشان می دهد. اگر مثلاً در شکل یک یال بین رئوس D و E رسم کنید، نمودار به هم متصل می شود. (شکل 8)

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

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

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

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

اثبات:

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

اجازه دهید اکنون به مشکل پل های کونیگزبرگ برگردیم.

بحث در مورد مشکل . قسمت های مختلف شهر را با حروف A، B، C، D و پل ها را با حروف a، b، c، d، e، f، g نشان می دهیم - پل هایی که قسمت های مربوطه شهر را به هم متصل می کنند. در این مشکل فقط عبور از روی پل ها وجود دارد: با عبور از هر پلی، همیشه از یک نقطه شهر به نقطه دیگر می رسیم و برعکس با عبور از یک نقطه شهر به نقطه دیگر، مطمئناً از یک پل عبور خواهیم کرد. بنابراین، اجازه دهید پلان شهر را به صورت نموداری به تصویر بکشیم که رئوس آن A، B، C، D (شکل 8) قسمت های جداگانه شهر و یال های a، b، c، d، e را نشان می دهد. , f, g پل هایی هستند که قسمت های مربوطه شهر را به هم متصل می کنند. اغلب راحت تر است که لبه ها را نه به عنوان بخش های مستقیم، بلکه به صورت منحنی - "قوس" به تصویر بکشیم.

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