اهمیت کاربردی مقاله پژوهشی نظریه گراف. کار پژوهشی پروژه "نظریه گراف"

آموزش متوسطه شهرداری سازمان تامین مالی دولتی -

دبیرستان شماره 51

اورنبورگ

پروژه در:

معلم ریاضی

اگورچوا ویکتوریا آندریونا

2017

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

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

وظایف:

1) دانش را در مورد روش های ساخت نمودار گسترش دهید.

2) انواع مسائلی را که حل آنها مستلزم استفاده از نظریه گراف است، شناسایی کنید.

3) استفاده از نمودارها را در ریاضیات کاوش کنید.

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

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

من. معرفی. پ.

II . بخش اصلی.

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

2. خواص نمودارها. پ.

3. مسائل با استفاده از نظریه گراف. پ.

ش. نتیجه گیری.

معنی نمودارها پ.

IV. کتابشناسی - فهرست کتب. پ.

من . معرفی

نظریه گراف یک علم نسبتاً جوان است. "Graphs" ریشه کلمه یونانی "grapho" به معنای "من می نویسم" است. همین ریشه در کلمات "گراف"، "بیوگرافی" است.

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

II . بخش اصلی.

1. مفهوم گراف.

اولین کار در مورد نظریه گراف متعلق به لئونارد اویلر است. در سال 1736 در انتشارات آکادمی علوم سن پترزبورگ ظاهر شد و با بررسی مشکل پل های کونیگزبرگ آغاز شد.

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

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

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

2. خواص نمودار.

اویلر در حین حل مشکل پل های کونیگزبرگ، به ویژه ویژگی های نمودار را مشخص کرد:

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

2. نموداری با دو رأس فرد را نیز می توان با یک ضربه رسم کرد. حرکت باید از هر راس فرد شروع شود و به راس فرد دیگری ختم شود.

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

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

5. اگر یک نمودار دارای رئوس فرد باشد، کوچکترین تعداد ضربه ای که می توان برای رسم نمودار استفاده کرد، برابر با نصف تعداد رئوس فرد این نمودار خواهد بود.

به عنوان مثال، اگر یک شکل دارای چهار عدد فرد باشد، می توان آن را حداقل با دو ضربه ترسیم کرد.

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

3. حل مسائل با استفاده از نمودار.

1. وظایف ترسیم فیگورها با یک ضربه.

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

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

اگر یک شکل فقط یک جفت نقطه فرد داشته باشد، می توان چنین شکلی را با یک ضربه ترسیم کرد و از یکی از نقاط فرد شروع به کشیدن کرد (مهم نیست کدام). به راحتی می توان فهمید که نقاشی باید در نقطه فرد دوم به پایان برسد. اینها شکل های 2، 3، 6 هستند. برای مثال در شکل 6، ترسیم باید از نقطه A یا از نقطه B شروع شود.

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

من پیشنهاد می کنم که شکل های زیر را در یک حرکت بکشید.

2. حل مسائل منطقی.

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

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

راه حل:

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

7 بازی انجام شده

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

وظیفه شماره 2

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

راه حل:

راه حل مسئله در شکل نشان داده شده است.

3. حل مسائل کلمه.

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

1. در مورد چه فرآیندی در مسئله صحبت می کنیم؟2. چه مقادیری این فرآیند را مشخص می کند؟3. چه رابطه ای بین این مقادیر وجود دارد؟4.چند فرآیند مختلف در مسئله توضیح داده شده است؟5. آیا ارتباطی بین عناصر وجود دارد؟

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

مثلا . این اتوبوس 2 ساعت با سرعت 45 کیلومتر بر ساعت و 3 ساعت با سرعت 60 کیلومتر در ساعت حرکت کرد. اتوبوس در این 5 ساعت چقدر مسافت را طی کرد؟

اس
¹=90 کیلومتر V ¹=45 کیلومتر در ساعت t¹=2 ساعت

S=VT

S²=180 کیلومتر V²=60 کیلومتر در ساعت t²=3 ساعت

اس ¹ + اس ² = 90 + 180

راه حل:

1) 45 x 2 = 90 (کیلومتر) - اتوبوس در 2 ساعت حرکت کرد.

2) 60 x 3 = 180 (کیلومتر) - اتوبوس در 3 ساعت حرکت کرد.

3) 90 + 180 = 270 (کیلومتر) - اتوبوس در 5 ساعت حرکت کرد.

جواب: 270 کیلومتر.

III . نتیجه.

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

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

V . کتابشناسی - فهرست کتب:

2008

مرور.

پروژه ای با موضوع "نمودارهای اطراف ما" توسط نیکیتا زایتسف، دانش آموز کلاس 7 "A" در موسسه آموزشی شهرداری شماره 3، کراسنی کوت تکمیل شد.

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

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

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

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

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

3. مسائل با استفاده از نظریه گراف.

4. معنای نمودارها.

5. گزینه مسیر اتوبوس مدرسه.

N. Zaitsev هنگام اجرای کار خود از موارد زیر استفاده کرد:

1. Alkhova Z.N., Makeeva A.V. " فعالیت های فوق برنامهریاضیات".

2. مجله "ریاضیات در مدرسه". پیوست «اول شهریور» شماره 13

2008

3. Ya.I.Perelman "کارها و آزمایشات سرگرم کننده." - مسکو: آموزش و پرورش، 2000.

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

کوچین آناتولی نیکولایویچ

مدیر پروژه:

کوکلینا تاتیانا ایوانونا

موسسه، نهاد:

MBOU "دبیرستان پایه" ترویتسکو-پچورسک نماینده. کومی

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

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

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

معرفی
فصل 1. آشنایی با نمودارها
1.1. تاریخچه نمودارها
1.2. انواع نمودارها
فصل 2. امکان به کارگیری نظریه گراف در حوزه های مختلف زندگی روزمره
2.1. کاربرد نمودارها در حوزه های مختلف زندگی مردم
2.2. کاربرد نمودارها در حل مسئله
2.3. شجره نامه یکی از راه های اعمال نظریه گراف است
2.4. شرح تحقیق و تدوین شجره نامه خانواده من
نتیجه
منابع
برنامه های کاربردی

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

معرفی

شمارش همه جا هست! در مقاله تحقیقاتی خود در مورد ریاضیات با موضوع "در دنیای نمودارها" در مورد نمودارهایی صحبت خواهیم کرد که هیچ ربطی به اشراف گذشته ندارند. "" ریشه کلمه یونانی دارد" گرافی"، یعنی چی" نوشتن" همان ریشه در کلمات " برنامه», « زندگینامه», « هولوگرافی».

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

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

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

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

موضوع مطالعهنمودارهای ریاضی است.

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

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

برای رسیدن به این هدف، مطرح کردم وظایف زیر:

1. با تاریخچه نظریه گراف آشنا شوید.
2. مطالعه مفاهیم اساسی نظریه گراف و انواع نمودارها.
3. روش هایی را برای حل مسائل با استفاده از نمودارها در نظر بگیرید.
4. کاربرد نظریه گراف را در زمینه های مختلف زندگی بشر نشان دهد.
5. یک شجره نامه از خانواده من ایجاد کنید.

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

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

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

برای اطمینان از این موضوع، من و مدیر به دانش آموزان کلاس های 5-9، شرکت کنندگان در تورهای مدرسه و شهرداری پیشنهاد دادیم. المپیاد تمام روسیهدانش آموزان مدرسه، 4 مسئله در حل آنها می توانید تئوری گراف را به کار ببرید ( پیوست 1).

نتایج حل مشکلات به شرح زیر است:
در مجموع 15 دانش آموز (پایه پنجم - 3 دانش آموز، کلاس ششم - 2 دانش آموز، کلاس هفتم - 3 دانش آموز، پایه هشتم - 3 دانش آموز، پایه نهم - 4 دانش آموز) تئوری گراف را در 1 مسئله - 1، در 2 مسئله - 0 استفاده کردند. ، در مسئله 3 – 6، مسئله 4 – 4 دانش آموزان.

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

انجمن علمیدانش آموزان

"جستجو کردن"

40 باز منطقه ای کنفرانس علمیدانش آموزان.

بخش ریاضیات.

کار علمی با موضوع:

در شجره نامه من "شمار می آید".

تکمیل شده توسط: Victoria Loburets

دانش آموز کلاس هفتم

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

سرپرست:

لیسنکو اولگا گریگوریونا

معلم ریاضی

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

اومسک - 2008

ارتباط و تازگی
هدف و وظایف

II. بخش اصلی
1. مفهوم نمودارها

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

3. استفاده از نمودار
III.بخش عملی
IV. نتیجه گیری
V.ادبیات

VI.پیوست

محتوا

مقدمه………………………………………………………………………………………………….3

P.1.1. ارتباط و تازگی……………………………………………………………………………………………………………..4

P.1.2. اهداف و مقاصد……………………………………………………………

فصل اول. بخش نظری………………………………………………….5

ص.2.1 مفهوم نمودارها……………………………………………………………………………

فصل دوم. قسمت عملی………………………………………………………………………………………………………………………………………………………………………

P.2.1. «شمارش» در شجره نامه من…………………………………………………………………………………………

P.2.2. حل مسائل منطقی با استفاده از روش نمودار…………………………………..11

نتیجه گیری……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………….

ادبیات……………………………………………………………………..18

برنامه های کاربردی……………………………………………………………………………..19

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

از نظر تاریخی، نظریه گراف از حل پازل بیش از دویست سال پیش سرچشمه گرفته است. او برای مدت طولانی از مسیرهای اصلی تحقیقات علمی دور بود. نظریه گراف در آغاز قرن نوزدهم و بیستم انگیزه ای برای توسعه یافت، زمانی که تعداد آثار در زمینه توپوگرافی و ترکیب شناسی، که ارتباط نزدیکی با آن دارد، به شدت افزایش یافت. اولین اشاره به نمودارها در کار L. Euler (1736) یافت می شود. در اواسط قرن نوزدهم، مهندس برق G. Kirchhoff تئوری درختان را برای مطالعه مدارهای الکتریکی توسعه داد و ریاضیدان A. Cayley در ارتباط با توصیف ساختار هیدروکربن ها، مسائل شمارش سه نوع درخت را حل کرد. نظریه گراف سرانجام در سال 1936 به عنوان یک رشته ریاضی شکل گرفت. پس از انتشار تک نگاری D. Koenig "Theory of Finite and Infinite Graphs".

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

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

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

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

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

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

بر اساس فرضیه، اهداف و مقاصد زیر از پژوهش مطرح شده است.

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

وظایف:

1) ادبیات علمی رایج در این مورد را مطالعه کنید.

2) اجرای «نمودار» برای روشن شدن روابط خانوادگی را بررسی کنید.

3) نتایج آزمایشات را تجزیه و تحلیل کنید.

4) مطالعه روش "گراف" به عنوان روشی برای حل مسائل منطقی.

فصل اول. بخش نظری

P.2.1. مفهوم نمودارها

واژه گراف در ریاضیات به معنای تصویری است که چندین نقطه کشیده شده است که برخی از آنها با خطوطی به هم متصل شده اند. نمودارهای ریاضی با عنوان نجیب "تعداد" با منشأ مشترک از کلمه لاتین "graphio" به هم متصل می شوند - من می نویسم. نمودارهای معمولی نمودارهای خطوط هوایی هستند که اغلب در فرودگاه ها، نمودارهای مترو و نقشه های جغرافیایی ارسال می شوند - یک تصویر راه آهن(عکس. 1). نقاط انتخاب شده نمودار را رئوس آن و خطوطی که آنها را به هم متصل می کنند یال می نامند.

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

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

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

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

نمودارهای نشان‌داده‌شده در شکل‌های 4 و 5 نقش تعیین‌کننده‌ای در تعیین مسطح بودن هر نمودار ایفا می‌کنند، یعنی اینکه آیا می‌توان آن را روی یک صفحه بدون قطع کردن لبه‌های آن ترسیم کرد. ریاضیدان لهستانی G. Kuratowski و آکادمیک

L.S. Pontryagin به طور مستقل ثابت کرد که اگر نمودار مسطح نباشد، حداقل یکی از نمودارهای نشان داده شده در شکل 4 و 5 در آن "نشسته" است، یعنی یک نمودار "پنج رأس کامل" یا یک نمودار "خانه-چاه". .

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

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

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

شکل 7.

اعداد در نزدیکی رئوس نمودار نشان داده می شوند - مدت زمان کار مربوطه در روز. اکنون می‌توانیم کوتاه‌ترین مدت زمان ساخت را پیدا کنیم. برای انجام این کار، از بین تمام مسیرهای نمودار در جهت فلش ها، باید مسیری را انتخاب کنید که مجموع اعداد در رئوس آن بزرگ ترین باشد. به آن مسیر بحرانی می گویند (در شکل 7 با رنگ قهوه ای مشخص شده است). در مورد ما 170 روز می گیریم. و اگر زمان اجرای شبکه برق را از 40 روز به 10 روز کاهش دهید، زمان ساخت نیز 30 روز کاهش می یابد؟ خیر، در این صورت مسیر بحرانی از این راس عبور نمی کند، بلکه از رئوس مربوط به ساخت گودال، پی ریزی و غیره می گذرد. کل زمانساخت 160 روز خواهد بود، یعنی مدت زمان فقط 10 روز کاهش می یابد.

شکل 8 نقشه راه های بین روستاهای M، A، B، C، D را نشان می دهد.

در اینجا هر دو راس با یک یال به هم متصل می شوند. چنین نموداری کامل نامیده می شود. اعداد در شکل نشان دهنده فواصل بین روستاهای این جاده ها هستند. بگذارید یک اداره پست در روستای M وجود داشته باشد و پستچی باید نامه ها را به چهار روستای دیگر برساند. مسیرهای سفر بسیار متنوعی وجود دارد. چگونه کوتاه ترین را انتخاب کنیم؟ ساده ترین راه تجزیه و تحلیل همه گزینه ها است. یک نمودار جدید (در زیر) به شما در انجام این کار کمک می کند، جایی که می توانید مسیرهای احتمالی را به راحتی مشاهده کنید. قله M در بالا ابتدای مسیرها است. شما می توانید حرکت از آن را با چهار شروع کنید راه های مختلف: در A، در B، در C، در D. پس از بازدید از یکی از روستاها، سه امکان برای ادامه مسیر وجود دارد، سپس دو، سپس جاده آخرین روستا و دوباره به M. مجموعاً 4×3 × 2 × 1 = 24 راه.

بیایید اعدادی را در لبه های نمودار قرار دهیم که نشان دهنده فواصل بین روستاها است و در انتهای هر مسیر مجموع این فواصل را در طول مسیر می نویسیم. از 24 عدد به‌دست‌آمده، کوچک‌ترین آنها دو عدد 28 کیلومتری هستند مسیرهای M-V-B-A-G-Mو م-گ-الف-ب-و-م. این همان مسیر است، اما در جهات مختلف طی شده است. توجه داشته باشید که نمودار در شکل. 8 را نیز می توان با نشان دادن جهت از بالا به پایین در هر یک از لبه ها جهت دار کرد که با جهت حرکت پستچی مطابقت دارد. مشکلات مشابه اغلب هنگام یافتن بهترین گزینه ها برای توزیع کالاها در فروشگاه ها و مصالح ساختمانی در سایت های ساختمانی ایجاد می شود.

نمودارها اغلب برای حل مسائل منطقی شامل شمارش گزینه ها استفاده می شوند. برای مثال مشکل زیر را در نظر بگیرید. این سطل دارای 8 لیتر آب است و دارای دو تابه 5 و 3 لیتری می باشد. باید 4 لیتر آب در یک تابه پنج لیتری بریزید و 4 لیتر در سطل بگذارید، یعنی آب را به همان اندازه در سطل و یک تابه بزرگ بریزید. راه حل: وضعیت در هر لحظه را می توان با سه عدد توصیف کرد، که در آن A تعداد لیتر آب در سطل، B در یک تابه بزرگ، C در یک عدد کوچکتر است. در لحظه اولیه، وضعیت با سه عدد (8، 0، 0) توصیف شد، که از آن می توانیم به یکی از این دو وضعیت برویم: (3، 5، 0)، اگر یک ظرف بزرگ را پر از آب کنیم، یا (5، 0، 3)، اگر ظرف کوچکتر را پر کنید. در نتیجه، دو راه حل دریافت می کنیم: یکی در 7 حرکت، دیگری در 8 حرکت.

به روشی مشابه، می توانید نموداری از هر بازی موقعیتی ایجاد کنید: شطرنج، چکرز، تیک تاک، جایی که موقعیت ها به رئوس تبدیل می شوند و بخش های هدایت شده بین آنها به این معنی است که در یک حرکت می توانید از یک موقعیت حرکت کنید. به دیگری، در جهت فلش. با این حال، برای شطرنج و چکرز، چنین نموداری بسیار بزرگ خواهد بود، زیرا موقعیت های مختلف در این بازی ها به میلیون ها نفر می رسد. اما برای بازی "tic-tac-toe" روی تخته 3x3، رسم نمودار مربوطه چندان دشوار نیست، اگرچه حاوی چندین ده (اما نه میلیون ها) رئوس است. از نظر نموداری، مشکل انتصاب به سمت ها به راحتی قابل فرمول بندی و حل است. یعنی: اگر چندین موقعیت خالی وجود داشته باشد و گروهی از افراد مایل به پر کردن آنها باشند و هر یک از متقاضیان واجد شرایط چند موقعیت شغلی باشند، هر یک از متقاضیان تحت چه شرایطی می‌توانند در یکی از تخصص‌های خود مشغول به کار شوند؟

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

فصل دوم. بخش عملی
P.2.1. در شجره نامه من "شمار می آید".
روش های کار:

مقایسه و تجزیه و تحلیل نتایج تجربی.

روش کار:

موارد زیر برای تحقیق انتخاب شدند:

الف) شجره نامه خانواده من، آرشیو داده ها، شناسنامه.

ب) شجره شاهزادگان گولیتسین، آرشیو داده ها.

من تحقیقاتی انجام دادم، نتایج تحقیق را در نمودارها قرار دادم و آنها را تجزیه و تحلیل کردم.

روش 1.
هدف: اجرای "شمارش" را در شجره نامه خود بررسی کنید.

نتایج: طرح 1 (به پیوست 1 مراجعه کنید).

روش 2.
هدف: اجرای "شمار" را در شجره نامه شاهزادگان گلیتسین بررسی کنید.

نتیجه: طرح 2 (به پیوست 2 مراجعه کنید).

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

مثال 1.1. مدادهای قرمز، آبی، زرد و سبز در چهار جعبه، یک به یک قرار دارند. رنگ مداد با رنگ جعبه متفاوت است. معلوم است که مداد سبز در جعبه آبی است، اما مداد قرمز در یک زرد نیست. هر مداد در کدام جعبه قرار می گیرد؟

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

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

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

راه حل.بیایید یک نمودار از رابطه مشخص شده در بیان مسئله بسازیم. برای این کار ابتدا مجموعه نام خانوادگی M و مجموعه رنگ مو K را انتخاب می کنیم که عناصر آن با نقطه مشخص می شوند. اجازه دهید نقاط مجموعه را حروف M بنامیم B، H، R(بلوکوروف، چرنوف و ریژوف)؛ امتیازات ست دوم – b، br، r(بلند، سبزه، قرمز). اگر نقطه ای از یک مجموعه با نقطه ای از مجموعه دیگر مطابقت داشته باشد آنها را با یک خط ثابت و اگر مطابقت نداشت آنها را با یک خط چین وصل می کنیم. شرط مسئله فقط ناهماهنگی ها را نشان می دهد، بنابراین، ابتدا نمودار نشان داده شده در شکل 2 باید ظاهر شود.

شکل 2

از شرایط مسئله چنین استنباط می شود که برای هر نقطه از مجموعه M، یک و تنها یک نقطه از مجموعه های K وجود دارد که با نقطه اول مطابقت دارد و برعکس، برای هر نقطه از مجموعه K یک و فقط یک نقطه از مجموعه M. مشکل به این خلاصه می‌شود: یافتن این تناظر ممکن بین عناصر مجموعه‌های M و K، یعنی یافتن سه خط ثابت که نقاط متناظر مجموعه‌ها را به هم متصل می‌کنند.

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

شکل 3
بعد، باقی مانده است که نقطه را با یک خط ثابت وصل کنید اچو دوره ب، از آنجا که نقطه اچمتصل به یک نقطه brخط چین و نقطه آردر حال حاضر "مشغول" است (شکل 4).

برنج. 4

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

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

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

1. دختری که گیتار می نوازد اسپانیایی صحبت می کند.

2. لیدا ویولن یا ویولن سل نمی نوازد و انگلیسی نمی داند.

3. ماشا ویولن یا ویولن سل نمی نوازد و انگلیسی نمی داند.

4. دختری که آلمانی صحبت می کند ویولن سل نمی نوازد.

5. ژنیا می داند فرانسوی، اما ویولن نمی نوازد.

چه کسی کدام ساز و کدام ساز را می نوازد؟ زبان خارجیمی داند؟

راه حل.شرایط مشکل با نمودار نشان داده شده در شکل 5 مطابقت دارد.

برنج. 5

اجازه دهید قطعات جامد زیر را به ترتیب ترسیم کنیم: KS، VZH، VF، AK (شکل 6).

برنج. 6

بنابراین، دو مثلث "جامد" ZHVF و KSA تشکیل می شوند. ما یک بخش پیوسته دیگر از وسیله نقلیه پرتاب را انجام می دهیم. اکنون متقاعد شده‌ایم که شرایط مشکل، انتخاب بدون ابهام نقطه سوم را برای هر یک از جفت‌های RN و GI تضمین نمی‌کند. گزینه های زیر برای مثلث های "جامد" امکان پذیر است: MGI و OSR یا LGI و MRN. بنابراین، مشکل دو راه حل دارد.

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

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

مثلاً این را در نظر بگیرید وظیفه:

دو کشتی با ظرفیت 3 و 5 لیتر وجود دارد. چگونه می توان از این ظروف برای ریختن 4 لیتر آب از شیر استفاده کرد؟

بیایید از آخر شروع کنیم. نتیجه چگونه می تواند 4 لیتر باشد؟ – از ظرف 5 لیتری 1 لیتر بریزید. چگونه انجامش بدهیم؟ - در ظرف 3 لیتری باید دقیقا 2 لیتر داشته باشید. چگونه آنها را بدست آوریم؟ – از ظرف 5 لیتری 3 لیتر بریزید. حالا بیایید ابتدا راه حل مسئله را در قالب جدول بنویسیم.

جستجوی راه حل را می توان با عمل 3+1 شروع کرد که به حلی که در جدول زیر نوشته می شود منجر می شود.

از اعداد 3 و 5 می توانید عباراتی ایجاد کنید که دارای مقدار 4 هستند:

5-3+5-3=4 و 3+3-5+3=4

به راحتی می توان تأیید کرد که عبارات حاصل با راه حل های موجود در بالا مطابقت دارند.

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

من مثالی از راه حل با استفاده از درخت گراف برای حل یک مسئله ترکیبی می زنم.

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

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

بعد وظیفه:

"با استفاده از اعداد 1،2،3،4 چند عدد دو رقمی می توانید بسازید؟"

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

پاسخ: 16 عدد

بگذارید چند مثال بزنم:

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

ن

در فینال، 4x6 = 24 بازی انجام می شود.
2. در گلدان چهار نوع شیرینی بود. هر بچه دو آب نبات گرفت. و همه ست های مختلف آب نبات داشتند. چند تا بچه ممکنه باشه؟ (نمودار در شکل 4).

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

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

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

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

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

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

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

ادبیات.

Berezina L.Yu. نمودارها و کاربرد آنها - م.، 1979.
ویلنکین N.Ya. ریاضیات. - م.: کلمه روسی, 1997.
گاردنر M. "فرغت ریاضی" M.: میر، 1972
Gnedenko B.V. درس تئوری احتمال. - M.: URSS، 2005.
Konnova L.P. با شمارش ملاقات کنید. - سامارا، 2001.
لیکووا I.A. معماهای منطقی – م.: کاراپوز، 2000.
ساوین A.V. فرهنگ لغت دایره المعارفیریاضیدان جوان ویرایش دوم، - م.: آموزش، 1989
شادرینوا V.D. فرآیندها و توانایی های شناختی در یادگیری - م.: آموزش، 1980
دوره چیستیاکوف V.P. در نظریه احتمال. م.، آموزش و پرورش، 1361.

برنامه های کاربردی.
پیوست 1.
لوبورتس ویکتوریا ولادیمیرونا، متولد 1994.

Loburets V. N

1962
.

Orlovskaya L.V.

صفحه 1

انجمن علمی دانشجویان

"جستجو کردن"

بخش علوم کامپیوتر

کار علمی با موضوع:

"اعلیحضرت کنت"

انجام: ساپوژنیکوا سوتلانا،

دانش آموز کلاس هفتم

موسسه آموزشی شهری "مدرسه متوسطه سرگیفسکایا"

اوکونشنیکوفسکی آقای

سرپرست: گرمس النا آناتولیونا،

معلم فناوری اطلاعات

موسسه آموزشی شهری "مدرسه متوسطه سرگیفسکایا"

اومسک - 2010
محتوا

انجمن علمی دانشجویی 1

"جستجو" 1

کار علمی با موضوع: 1

مقدمه 3

نظریه گراف 4

1.2. نمودارهای اویلری 7

1.3. مسئله پل، لئونارد اویلر و نظریه گراف 8

2.1. حل مسائل با استفاده از نمودارهای "یک روز از زندگی تعداد" 11

کتابشناسی 16

معرفی

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

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

موضوع مطالعه: مفهوم گراف
موضوع مطالعه: میزان شیوع استفاده از گراف
هدف از مطالعه: نقش نمودارها را در زندگی ما کشف کنید.
اهداف پژوهش:

1. با تاریخچه پیدایش نمودارها آشنا شوید.

2. با مفاهیم اساسی گراف، انواع، عناصر آشنا شوید.

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

4. شجره نامه خود را ایجاد کنید.
روش های پژوهش: جزئی - جستجو، تحلیلی.

فصل 1

تئوری گراف

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

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

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

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

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

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

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

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

اگرچه اصطلاح "گراف" برای اولین بار در سال 1936 توسط ریاضیدان مجارستانی Dénes König ابداع شد.

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

طرح گراف متشکل از رئوس "ایزوله" گراف تهی نامیده می شود. (شکل 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 +...) یک عدد زوج است.
توجه داشته باشید که اگر یک نمودار کامل n رأس داشته باشد، تعداد یال ها برابر خواهد بود

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

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

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

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

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

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

الگوی 5.

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

الگوی 6.

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

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

شکل 6 (نمودارهای اویلری)

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

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

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

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

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

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

1.3. مسئله پل، لئونارد اویلر و نظریه گراف

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

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

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

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

شکل 9

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

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

اگر همه رئوس نمودار زوج باشند، می توانید بدون اینکه مداد خود را از روی کاغذ بردارید، نموداری بکشید و می توانید از هر رأس نمودار شروع کنید و آن را در همان راس خاتمه دهید.

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

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

اویلر در حین حل مشکل پل های کونیگزبرگ، به ویژه ویژگی های نمودار را مشخص کرد:

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

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

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

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

اگر همه رئوس یک چرخه متفاوت باشند، به چنین چرخه ای چرخه ابتدایی (یا ساده) می گویند. اگر یک چرخه تمام لبه های نمودار را یک بار شامل شود، چنین چرخه ای خط اویلر نامیده می شود (شکل 10a). نمودار در شکل 10b دارای دو چرخه است: 1-2-3-4-1 و 5-6-7-5.

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

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

شکل 10 a;b
ملک 1.

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

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

ملک 2.

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

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

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

اثبات:

واضح است که این نمودار متصل است. بیایید فرض کنیم که یک حلقه دارد. سپس هر دو راس این چرخه حداقل با دو مسیر ساده به هم متصل می شوند. ما یک تناقض دریافت کردیم، به این معنی که فرض ما نادرست است.

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

LEMMA (درباره راس آویزان)

هر درختی یک بالای آویزان دارد.

اثبات:

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

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

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

مثلا:

نقشه خطوط مترو را می توان به عنوان یک نمودار در نظر گرفت.

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

در پزشکی - سوال از گروه خون.

یک شجره نامه را می توان به عنوان یک نمودار نشان داد.

سیستم های طبقه بندی در علم

ساختار سلسله مراتبی مدیریت اداری یک شرکت، دانشگاه و غیره

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

فصل 2

2.1. حل مسائل با استفاده از نمودارهای "یک روز در زندگی یک تعداد"

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

وظیفه 1.صبح دانش آموزان مدرسه ما را از روستاهای اطراف ولچینو، اولخوفکا، کوچکواتو و پاولوفکا به کلاس ها آوردند. شکل نموداری را نشان می دهد که اطلاعات جاده های بین چهار روستا را نشان می دهد: Volchino، Olkhovka، Kochkovatoe، Pavlovka. وزن رئوس نام روستاها، وزن خطوط طول راه ها به کیلومتر است.

مسیر اتوبوس یک نمودار است.

وظیفه 2.وقتی همدیگر را دیدیم، هر یک از همکلاسی هایم با یکدیگر دست دادند (هر کدام همدیگر را تکان دادند). در صورت وجود: 1) سه دوست، چند دست دادن انجام شد. 2) چهار؛ 3) پنج؟

راه حل.

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

1) سه نفر ملاقات کردند:

تعداد دست دادن ها برابر است با تعداد لبه ها، یعنی 3.

2) چهار نفر ملاقات کردند:

تعداد دنده 6; امکان 6 دست دادن

3) پنج نفر ملاقات کردند:

10 یال در نمودار وجود دارد. شاید 10 دست دادن

جواب: 1)3; 2) 6; 3) 10.
طبق برنامه شش درس هندسه، تاریخ، کامپیوتر، جغرافیا، زبان روسی و فیزیک داریم.
وظیفه 3.در یک درس هندسه، ساخت نمودار طبقه بندی اجسام هندسی پیشنهاد شد. با استفاده از مفهوم گراف انجام این کار آسان بود.

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

همه می دانند که کلمه "count" به معنای یک عنوان نجیب است، به عنوان مثال، کنت لو نیکولاویچ تولستوی. نمودار دیگری در شکل وجود دارد - بخشی از شجره نامه Count L.N. تولستوی. در اینجا رئوس اجداد نویسنده هستند و لبه ها پیوندهای خانوادگی بین آنها را نشان می دهد.

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

وظیفه 6.در درس جغرافیا به یک پاراگراف نگاه کردیم. و برای یافتن سریعتر مطالب را در انتهای کتاب درسی باز کردم. و در کمال تعجب متوجه شدم که ساختار بخش های کتاب درسی به شکل درخت منعکس شده است.

مسئله 7. در طول درس زبان روسی، موضوع "اعداد" بود و معلم به ما پیشنهاد داد که یک خلاصه پشتیبان تهیه کنیم.

اعداد در زبان روسی بر اساس ترکیب و معنی طبقه بندی می شوند. بر اساس ترکیب آنها به ساده، پیچیده و مرکب تقسیم می شوند. مثال اعداد ساده: چهار، پنج. مثال اعداد مختلط: شصت، پانصد. نمونه ای از اعداد مرکب: 35، 154. اعداد بر اساس معنی به ترتیبی و اصلی تقسیم می شوند. نمونه اعداد ترتیبی: دوم، نهم. نمونه ای از اعداد اصلی: شش، دو.

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

مسئله 8. اتاق غذاخوری دو غذای اول را ارائه می دهد: بورشت، راسولنیک، و همچنین چهار غذای دوم: گولش، کتلت، سوسیس، کوفته. تمام وعده‌های غذایی دو وعده‌ای را که یک غذاخوری ممکن است سفارش دهد فهرست کنید. پاسخ خود را با ساختن درختی از گزینه های ممکن نشان دهید.

راه حل.

برای نشان دادن همه وعده های غذایی دو وعده، به این صورت استدلال می کنیم.

بیایید یک غذای اول (بورشت) را انتخاب کنیم و دوره های مختلف دوم را یکی یکی به آن اضافه کنیم

پاسخ: 8 وعده غذای مختلف دو وعده.

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

پاسخ: 6 ترکیب.

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

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

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

بنابراین شمارش بهترین دوستان من شدند. همکلاسی ها و معلمان متوجه شدند که عملکرد من در دروس بهبود یافته است. اما می دانم که این به لطف «اعلیحضرت کنت» است!

نتیجه

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

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

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

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

کتابشناسی - فهرست کتب

1. Genkin, S. A, Itenberg I. V. محافل ریاضی لنینگراد: کتابچه راهنمای برای

فعالیت های فوق برنامه.-Kirov، 1994.

2. گورباچف، وی.جی. مجموعه مسائل المپیاد در ریاضیات - م.، 1383.

3. ایگناتیف E.I. دانش ریاضی. - مسکو، 1994

4. سنگ معدن، O. نمودارها و کاربرد آنها - مسکو، 1979.

5. پرلمن، یا.آی. وظایف سرگرم کننده - مسکو، 2003

6. مجله فیزیک و ریاضی کوانت، ا. ساوین، شماره 6، 1373.

صفحه 1

شهر سوم علمی

کنفرانس دانشجویی

علوم کامپیوتر و ریاضیات

پژوهش

دایره های اویلر و نظریه گراف در حل مسئله

ریاضیات مدرسه و علوم کامپیوتر

ولیف ایرات

موسسه آموزشی شهرداری

«دبیرستان شماره 10 با مطالعه عمیق

موضوعات فردی»، کلاس 10 B، Nizhnekamsk

ناظران علمی:

خلیلوا نفیسه زینیاتولونا، معلم ریاضیات

معلم فناوری اطلاعات

نابرژنیه چلنی

معرفی. 3

فصل 1. دایره های اویلر. 4

1.1. مبانی نظری در مورد دایره های اویلر 4

1.2. حل مسائل با استفاده از دایره های اویلر 9

فصل 2. درباره ستون 13

2.1.نظریه گراف. 13

2.2. حل مسائل با استفاده از نمودار 19

نتیجه. 22

کتابشناسی - فهرست کتب. 22

معرفی

تمام شأن ما در اندیشه نهفته است.

این فضا نیست، زمان آن نیست که نتوانیم آن را پر کنیم،

ما را بالا می برد، یعنی آن، فکر ما.

یاد بگیریم خوب فکر کنیم.»

ب. پاسکال،

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

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

اهداف پژوهش:

1. مطالعه مبانی نظری مفاهیم: "دایره های اویلری"، "نمودار".

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

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

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

موضوع مطالعه:مفاهیم: "دایره های اویلر"، "نمودارها"، مسائل یک دوره مدرسه در ریاضیات و علوم کامپیوتر.

فصل 1. دایره های اویلر.

1.1. مبانی نظری در مورد دایره های اویلر

دایره‌های اویلر (دایره‌های اویلر) روشی برای مدل‌سازی پذیرفته‌شده در منطق، نمایشی بصری از روابط بین حجم‌های مفاهیم با استفاده از دایره‌ها است که توسط ریاضیدان معروف L. Euler (1707-1783) پیشنهاد شده است.

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

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

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

https://pandia.ru/text/78/128/images/image003_74.gif" alt="Overlapping classes" width="200" height="100 id=">!}

این دقیقاً رابطه ای است که بین دامنه مفاهیم "دانشجو" و "عضو کومسومول" وجود دارد. برخی (اما نه همه) دانش آموزان عضو Komsomol هستند. برخی (و نه همه) اعضای کومسومول دانشجو هستند. بخش بدون سایه دایره A آن بخشی از دامنه مفهوم "دانشجو" را منعکس می کند که با دامنه مفهوم "عضو کومسومول" منطبق نیست. قسمت بدون سایه دایره B آن بخشی از دامنه مفهوم "عضو کومسومول" را منعکس می کند که با دامنه مفهوم "دانشجو" همخوانی ندارد. قسمت سایه دار، که در هر دو دایره مشترک است، دانش آموزانی را که عضو کامسومول هستند و اعضای کومسومول را که دانشجو هستند نشان می دهد.

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

https://pandia.ru/text/78/128/images/image005_53.gif" alt=" مفاهیم با حجم های یکسان - دایره های همزمان" width="200" height="100 id=">!}

برای مثال، چنین رابطه ای بین مفاهیم «بنیانگذار ماتریالیسم انگلیسی» و «نویسنده ارگانون جدید» وجود دارد. دامنه این مفاهیم یکسان است؛ آنها منعکس کننده همان شخصیت تاریخی هستند - فیلسوف انگلیسی F. Bacon.

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

https://pandia.ru/text/78/128/images/image007_46.gif" alt="مفاهیم مخالف" width="200" height="100 id=">!}

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

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

https://pandia.ru/text/78/128/images/image009_38.gif" alt="موضوع و محمول تعریف" width="200" height="100 id=">!}

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

کتابخانه های مدرسه" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">کتابخانه مدرسه، 20 - در منطقه. چند نفر از دانش آموزان کلاس پنجم:

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

ب) خوانندگان کتابخانه منطقه نباشند.

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

د) فقط خوانندگان کتابخانه منطقه ای هستند.

ه) آیا خوانندگان هر دو کتابخانه هستند؟

3. هر دانش آموز در کلاس یا انگلیسی یا فرانسوی یا هر دو را یاد می گیرد. زبان انگلیسی 25 نفر زبان فرانسه، 27 نفر فرانسه و 18 نفر هر دو را مطالعه می کنند. چند دانش آموز در کلاس هستند؟

4. روی یک ورق کاغذ، دایره ای به مساحت 78 سانتی متر مربع و مربعی به مساحت 55 سانتی متر مربع بکشید. مساحت تقاطع دایره و مربع 30 سانتی متر مربع است. قسمتی از ورق که دایره و مربع آن را اشغال نمی کند 150 سانتی متر مربع مساحت دارد. مساحت ورق را پیدا کنید.

5. ب مهد کودک 52 فرزند. هر کدام از آنها عاشق کیک یا بستنی یا هر دو هستند. نیمی از بچه ها کیک و 20 نفر کیک و بستنی دوست دارند. چند کودک بستنی دوست دارند؟

6. 86 دانش آموز دبیرستانی در تیم تولید دانش آموزی حضور دارند. 8 نفر از آنها کارکردن با تراکتور و کمباین را بلد نیستند. 54 دانش آموز به خوبی بر تراکتور تسلط داشتند، 62 دانش آموز - کمباین. چند نفر از این تیم می توانند هم در تراکتور و هم در کمباین کار کنند؟

7. 36 دانش آموز در کلاس هستند. بسیاری از آنها در باشگاه ها شرکت می کنند: فیزیک (14 نفر)، ریاضی (18 نفر)، شیمی (10 نفر). علاوه بر این، مشخص است که 2 نفر در هر سه حلقه شرکت می کنند. از کسانی که در دو حلقه شرکت می کنند، 8 نفر در حلقه های ریاضی و فیزیکی، 5 نفر در حلقه های ریاضی و شیمی، 3 نفر در حلقه های فیزیکی و شیمیایی هستند. چند نفر در هیچ باشگاهی شرکت نمی کنند؟

8. 100 دانش آموز کلاس ششم مدرسه ما در یک نظرسنجی شرکت کردند تا بفهمند کدام بازی های رایانه ای را بیشتر دوست دارند: شبیه سازها، ماموریت ها یا استراتژی ها. در نتیجه، 20 پاسخ دهنده شبیه سازها، 28 - کوئست، 12 - استراتژی را نام بردند. مشخص شد که 13 دانش آموز به شبیه سازها و کوئست ها، 6 دانش آموز - شبیه سازها و استراتژی ها، 4 دانش آموز - به ماموریت ها و استراتژی ها ترجیح می دهند و 9 دانش آموز نسبت به موارد ذکر شده کاملاً بی تفاوت هستند. بازی های کامپیوتری. برخی از دانش آموزان پاسخ دادند که آنها به همان اندازه به شبیه سازها، ماموریت ها و استراتژی ها علاقه مند هستند. چند نفر از این افراد وجود دارند؟

پاسخ ها

https://pandia.ru/text/78/128/images/image012_31.gif" alt="Oval: A" width="105" height="105">1.!}

الف – شطرنج 25-5=20 – نفر. بلد باشه بازی کنه

ب – چکرز 20+18-20=18 – مردم هم شطرنج بازی می کنند و هم چکرز

2. Ш – تعداد زیادی بازدیدکننده از کتابخانه مدرسه

P - بازدیدکنندگان زیادی از کتابخانه منطقه

https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">

5. 46. پ – کیک، م – بستنی

6- کودکان عاشق کیک هستند

6. 38. T – تراکتور، K – کمباین

54+62-(86-8)=38 – قادر به کار در تراکتور و کمباین

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

مفاهیم اساسی.

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

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

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

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

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

به عنوان یک قاعده، نمودار یا بلافاصله به گونه ای ساخته می شود که همه کمان ها دارای یک ویژگی جهت باشند (مثلاً همه یک طرفه هستند)، یا از طریق تبدیل ها به این شکل می رسند. اگر قوس AB جهت دار باشد، به این معنی است که از دو انتهای آن، یکی (A) آغاز و دومی (B) پایان در نظر گرفته می شود. در این صورت می گویند که شروع کمان AB راس A است و انتهای آن راس B است، اگر کمان از A به B هدایت شود یا اینکه قوس AB از راس A آمده و وارد B می شود (شکل 5). ).

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

یک مفهوم مهم در مطالعه نمودارها مفهوم مسیر است. یک مسیر A1,A2,...An به عنوان یک دنباله محدود (تعدادی) از رئوس A1,A2,...An و کمان های A1, 2,A2,3,...,An-1,n تعریف می شود که به صورت متوالی به هم متصل می شوند. این رئوس

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

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

اتصال می تواند نه تنها یک مشخصه کیفی یک نمودار (متصل/قطع)، بلکه یک ویژگی کمی باشد.

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

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

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

مثلا، نقاشی کودکانشخص (شکل 6) نموداری با حداکثر قابلیت اتصال برابر با 4 است.

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

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

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

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

انواع نمودارها

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

در قلب این همه تنوع چندین ایده نسبتا ساده وجود دارد که در اینجا درباره آنها صحبت خواهیم کرد.

رنگ آمیزی

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

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

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

طول

گاهی اوقات عناصر شی مدل‌سازی شده توسط رئوس دارای کاراکترهای متفاوتی هستند. یا در طی فرآیند رسمی سازی، افزودن برخی عناصر ساختگی به عناصری که در واقع در شیء وجود دارند، مفید است. در این مورد و برخی موارد دیگر، طبیعی است که رئوس نمودار را به کلاس ها (اشتراک) تقسیم کنیم. گراف حاوی دو نوع رئوس را دو قسمتی و غیره می نامند. در این حالت قوانین مربوط به روابط بین رئوس در محدودیت های گراف گنجانده شده است. انواع متفاوت. به عنوان مثال: "هیچ کمانی وجود ندارد که رئوس هم نوع را به هم متصل کند." یکی از انواع گراف ها از این نوع، «شبکه پتری» نام دارد (شکل 9) و بسیار گسترده است. شبکه های پتری در مقاله بعدی این مجموعه با جزئیات بیشتری مورد بحث قرار خواهند گرفت.

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

2.2. حل مسائل با استفاده از نمودار

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

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

3. مشکل چهار رنگبه تقسیم یک هواپیما به مناطق غیر همپوشانی، نقشه می گویند. مناطق روی نقشه اگر دارای مرز مشترک باشند مجاور نامیده می شوند. وظیفه رنگ آمیزی نقشه به گونه ای است که هیچ دو ناحیه مجاور با یک رنگ رنگ آمیزی نشده باشند (شکل 12). از اواخر قرن گذشته، این فرضیه شناخته شده است که چهار رنگ برای این کار کافی است. در سال 1976، اپل و هایکن راه حلی برای مشکل چهار رنگ منتشر کردند که بر اساس جستجوی کامپیوتری بود. راه‌حل این مشکل «به‌صورت برنامه‌ای» سابقه‌ای بود که منجر به بحث‌های داغ شد، که به هیچ وجه تمام نشده است. ماهیت راه حل منتشر شده این است که یک عدد بزرگ اما محدود (حدود 2000) از انواع متقابل بالقوه را برای قضیه چهار رنگ امتحان کنید و نشان دهید که هیچ موردی نیز یک نمونه متضاد نیست. این جستجو توسط برنامه در حدود هزار ساعت کارکرد ابررایانه کامل شد. بررسی "دستی" راه حل حاصل غیرممکن است - دامنه شمارش بسیار فراتر از توانایی های انسانی است. بسیاری از ریاضیدانان این سوال را مطرح می کنند: آیا می توان چنین "برهان برنامه ای" را یک اثبات معتبر در نظر گرفت؟ از این گذشته، ممکن است خطاهایی در برنامه وجود داشته باشد... روش‌هایی برای اثبات صحت برنامه‌ها برای برنامه‌هایی با پیچیدگی‌هایی که مورد بحث قرار می‌گیرد، قابل اجرا نیستند. آزمایش نمی تواند عدم وجود خطا را تضمین کند و در این مورد به طور کلی غیرممکن است. بنابراین، ما فقط می توانیم به مهارت های برنامه نویسی نویسندگان تکیه کنیم و باور کنیم که آنها همه چیز را درست انجام داده اند.

وظایف دودنی

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

2. آقای رابینسون در لس آنجلس زندگی می کند.

3. رهبر ارکستر در اوماها زندگی می کند.

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

5. مسافر، همنام رهبر، در شیکاگو زندگی می کند.

6. هادی و یکی از مسافران، کارشناس معروف فیزیک ریاضی، اگرچه به یک کلیسا می روند.

7. اسمیت همیشه وقتی آتش نشان را در یک بازی بیلیارد ملاقات می کنند، بر او پیروز می شود.

نام خانوادگی راننده چیست؟ (شکل 13)

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

نتیجه

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

کتابشناسی - فهرست کتب

1. "کارهای سرگرم کننده در علوم کامپیوتر"، مسکو، 2005

2. "سناریوهایی برای تعطیلات مدرسه" توسط E. Vladimirova، Rostov-on-Don، 2001

3. وظایف برای کنجکاوها. ، م.، آموزش و پرورش، 1992،

4. کارهای فوق برنامه در ریاضیات، ساراتوف، لیسیوم، 2002.

5. دنیای شگفت انگیز اعداد. ، .، م.، آموزش و پرورش، 1986،

6. جبر: کتاب درسی پایه نهم. ، و دیگران، ویرایش. ، - م.: روشنگری، 2008