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

مؤسسه آموزشی خودگردان شهرداری دبیرستان شماره 2

آماده شده

Legkokonets ولادیسلاو، دانش آموز کلاس 10A

کاربرد عملی تئوری گراف

سرپرست

L.I. نوسکووا، معلم ریاضیات

هنر

2011

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

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

3. تعاریف و قضایای اساسی نظریه گراف………………………………………………….

4. مسائل حل شده با استفاده از نمودار…………………………………………………………………..8

4.1 مشکلات معروف…………………………………………………………………………………………………

4.2 چند مشکل جالب…………………………………………………………..9

5. کاربرد نمودارها در حوزه های مختلف زندگی مردم……………………………………………………

6. حل مسائل………………………………………………………………………………………………………………………………………………………………………………

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

8. فهرست مراجع……………………………………………………………………………………

9. ضمیمه………………………………………………………………………………………………………………………

معرفی

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

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

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

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

اهداف پژوهش:

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

2. بررسی اثربخشی روش نمودار در حل مسائل عملی.

3. نتیجه گیری کنید.

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

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

تاریخچه نظریه گراف

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

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

[پیوست شکل 1]سوال این است که آیا کسی می تواند به طور مداوم آنها را دور بزند و فقط یک بار از روی هر پل عبور کند؟ و سپس به من اطلاع دادند که هنوز کسی نتوانسته این کار را انجام دهد، اما هیچ کس ثابت نکرده است که غیرممکن است. این سوال اگرچه پیش پا افتاده بود اما به نظرم رسید شایسته توجهزیرا نه هندسه، نه جبر و نه هنر ترکیبی برای حل آن کافی نیست. پس از تفکر بسیار، یک قانون آسان بر اساس یک دلیل کاملاً قانع کننده پیدا کردم که با کمک آن می توان در تمام مشکلات از این نوع فوراً تعیین کرد که آیا می توان چنین انحرافی را از طریق هر تعداد و هر تعداد پل واقع انجام داد یا خیر. یا نه. پل های کونیگزبرگ به گونه ای قرار گرفته اند که می توان آنها را در شکل زیر نشان داد [پیوست شکل 2]که در آن A بیانگر یک جزیره است و B، C و D - قسمت هایی از قاره که توسط شاخه های رودخانه از یکدیگر جدا شده اند.

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

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

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

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

تعاریف و قضایای اساسی نظریه گراف

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

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

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

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

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

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

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

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

نامگذاری: U" – نموداری متشکل از n راس و یال که تمام جفت های ممکن از این راس ها را به هم متصل می کند. چنین نموداری را می توان به صورت یک n-gon نشان داد که در آن تمام قطرها رسم شده اند

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

تعریف 6.گرافی که درجات تمام k رأس آن یکسان باشد، گراف درجه همگن نامیده می شود .

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

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

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

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

تعریف 10.مسیر A تا X دنباله ای از یال های منتهی به A به X است به طوری که هر دو یال مجاور یک راس مشترک دارند و هیچ یالی بیش از یک بار رخ نمی دهد.

تعریف 11.چرخه مسیری است که در آن نقطه شروع و پایان منطبق است.

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

تعریف 13.طول مسیر , روی یک حلقه گذاشته شده است , تعداد لبه های این مسیر نامیده می شود.

تعریف 14.اگر مسیری از A به B وجود داشته باشد (وجود نداشته باشد) دو رأس A و B در یک گراف متصل (قطع شده) نامیده می شوند.

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

تعریف 16.درخت یک گراف متصل است که شامل چرخه نیست.

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

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

تعریف 18.درختی که تمام n رأس آن از 1 تا n شماره گذاری شده باشد درختی با رئوس شماره گذاری مجدد نامیده می شود.

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

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

مشکلات معروف

مشکل فروشنده دوره گرد

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

بیان مشکل به شرح زیر است.
یک فروشنده دوره گرد (تاجر سرگردان) باید اولین شهر را ترک کند، یک بار به ترتیب نامعلوم از شهرهای 2،1،3..n بازدید کند و به شهر اول بازگردد. فاصله بین شهرها مشخص است. به چه ترتیبی باید شهرها را دور زد تا مسیر بسته (تور) فروشنده دوره گرد کوتاه ترین باشد؟

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

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

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

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

نمودار مربوط به نمودار پل را در نظر بگیرید [پیوست شکل 2].

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

چند کار جالب

1. "مسیرها".

مشکل 1

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

راه حل:

نقشه راه نشان می دهد که چیچیکوف سفر خود را از املاک E آغاز کرد و با املاک O به پایان رسید. توجه می کنیم که فقط دو جاده به املاک B و C منتهی می شود، بنابراین چیچیکوف مجبور شد در امتداد این جاده ها حرکت کند. بیایید آنها را با یک خط پررنگ علامت گذاری کنیم. بخش هایی از مسیر عبور از A مشخص شده است: AC و AB. چیچیکوف در جاده های AE، AK و AM سفر نکرد. بیایید آنها را خط بکشیم. اجازه دهید با خط پررنگ ED علامت گذاری کنیم. بیایید DK را خط بکشیم. بیایید MO و MN را خط بزنیم. بیایید با یک خط پررنگ MF علامت گذاری کنیم. خط FO; بیایید FH، NK و KO را با خط پررنگ علامت گذاری کنیم. بیایید تنها مسیر ممکن را در این شرایط پیدا کنیم. و دریافت می کنیم: املاک E - متعلق به مانیلوف، D - Korobochka، C - Nozdryov، A - Sobakevich، B - Plyushkin، M - Tentetnikov، F - Betrishchev، N - Petukh، K - Konstanzholgo، O - Koshkarev. [پیوست شکل 5].

مشکل 2

شکل، نقشه منطقه را نشان می دهد [پیوست شکل 6].

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

راه حل:

ما مدار را به صورت متوالی به یک درخت "طبقه بندی" می کنیم و از راس 1 شروع می کنیم [پیوست شکل 7]. بیا یک درخت بگیریم عدد راه های ممکنضربات از 1 تا 9 برابر با تعداد رئوس "آویزان" درخت است (14 مورد وجود دارد). واضح است که کوتاه ترین مسیر 1-5-9 است. طولانی ترین 1-2-3-6-5-7-8-9 است.

2 "گروه ها، دوستیابی"

مشکل 1

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

الف) تعداد زوجی از پاکت ها تحویل داده شد.

ب) تعداد شرکت کنندگانی که پاکت ها را به تعداد فرد رد و بدل کرده اند زوج باشد.

راه حل: اجازه دهید شرکت کنندگان جشنواره A 1، A 2، A 3 باشند. . . ، و n رئوس نمودار هستند و یال ها جفت رئوس را به هم متصل می کنند که نشان دهنده افراد در حال مبادله پاکت ها هستند. [پیوست شکل 8]

راه حل:

الف) درجه هر راس A i تعداد پاکت هایی را نشان می دهد که شرکت کننده A به دوستانش داد. تعداد کلاز پاکت های ارسالی N برابر است با مجموع درجات تمام رئوس نمودار N = درجه. یک پله 1 + A 2 + + . . . + قدم A n -1 + درجه. و n، N = 2p، که در آن p تعداد یال های نمودار است، یعنی. N - زوج. در نتیجه تعداد زوجی از پاکت ها تحویل داده شد.

ب) در برابری N = درجه. یک پله 1 + A 2 + + . . . + قدم A n -1 + درجه. و n مجموع جمله های فرد باید زوج باشد و این تنها زمانی می تواند باشد که تعداد جمله های فرد زوج باشد. این به این معنی است که تعداد شرکت کنندگانی که پاکت نامه ها را چند بار رد و بدل کرده اند زوج است.

مشکل 2

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

راه حل:

بیایید پنج نقطه بکشیم و آنها را با حروف A، B، C، D، D برچسب گذاری کنیم. اینها حروف اول نام ها هستند. بیایید نقاطی را به هم وصل کنیم که با نام بچه هایی که تماس گرفتند مطابقت دارد.

[پیوست شکل 9]

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

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

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

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

نمودارهای مولکولیکه در استریوشیمی و توپولوژی ساختاری، شیمی خوشه‌ها، پلیمرها و غیره استفاده می‌شود، نمودارهایی بدون جهت هستند که ساختار مولکول‌ها را نمایش می‌دهند. [پیوست شکل 10]. رئوس و لبه های این نمودارها با اتم های مربوطه مطابقت دارد و پیوندهای شیمیاییبین آنها.

نمودارهای مولکولی و درختان: [پیوست شکل 10] a، b - به ترتیب چند نمودار. اتیلن و فرمالدئید؛ میگویند ایزومرهای پنتان (درختان 4 و 5 نسبت به درخت 2 هم شکل هستند).

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

شبکه های پروتئینی

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

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

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

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

نمونه ای از شجره نامه من [پیوست شکل 12].

یک مثال دیگر تصویر درخت خانوادگی کتاب مقدس را نشان می دهد [پیوست شکل 13].

حل مسئله

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

راه حل:

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

برای راحتی راه حل، شهرها را با اعداد مشخص می کنیم: کراسنودار - 1، کریمسک - 2، تمریوک - 3، اسلاویانسک - 4، تیماشفسک - 5.

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

به همین ترتیب، محاسبه حمل و نقل واقعی از یک محل به محل دیگر ممکن است و به نظر من ضروری است.

مشکل منطقی مربوط به انتقال خوناین سطل دارای 8 لیتر آب است و دارای دو تابه 5 و 3 لیتری می باشد. باید 4 لیتر آب در یک تابه پنج لیتری بریزید و 4 لیتر در سطل بگذارید، یعنی آب را به همان اندازه در سطل و یک تابه بزرگ بریزید.

راه حل:

وضعیت در هر لحظه را می توان با سه عدد توصیف کرد [پیوست شکل 16].

در نتیجه، دو راه حل دریافت می کنیم: یکی در 7 حرکت، دیگری در 8 حرکت.

نتیجه

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

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

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

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

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

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

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

ادبیات

برگ ک.نظریه گراف و کاربردهای آن -M.: IIL، 1962.

کیمنی جی، اسنل جی.، تامپسون جی.مقدمه ای بر ریاضیات متناهی -M.: IIL، 1963.

سنگ معدن O.نمودارها و کاربرد آنها -م.: میر، 1965.

هراری اف.نظریه گراف. -م.: میر، 1973.

زیکوف A.A.نظریه گراف محدود -نووسیبیرسک: علم، 1969.

Berezina L.Yu.نمودارها و کاربرد آنها -م.: آموزش و پرورش، 1979. -144 ص.

"مجله آموزشی سوروس" شماره 11 1996 (مقاله "نمودارهای مسطح");

گاردنر M. "فرغت ریاضی"، M. "World"، 1972 (فصل 35);

Olehnik S. N.، Nesterenko Yu. V.، Potapov M. K. "مشکلات سرگرم کننده قدیمی"، M. "علم"، 1988 (بخش 2، بخش 8؛ پیوست 4).

کاربرد

برنج. 6

برنج. 7

برنج. 8

کاربرد

برنج. 14

کاربرد

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

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

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

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

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

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

در اقتصاد؛

در تدارکات؛

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

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

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

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

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

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

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

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

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

شکل 2.1 a شکل. 2.1 ب

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

مبانی نظری:

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

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

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

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

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

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

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

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

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

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

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

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

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

بخش تحقیق

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

"یک بار از من مشکلی در مورد جزیره ای در شهر کونیگزبرگ پرسیده شد که توسط رودخانه ای احاطه شده است که در آن هفت پل پرتاب می شود. سوال این است که آیا کسی می تواند به طور مداوم آنها را دور بزند و فقط یک بار از هر پل عبور کند." اطلاع داد که هنوز هیچ کس نتوانسته است این کار را انجام دهد، اما هیچ کس ثابت نکرده است که غیرممکن است. پس از تفکر بسیار، یک قانون آسان بر اساس یک دلیل کاملاً قانع کننده پیدا کردم که با کمک آن می توان بلافاصله در همه مشکلات از این نوع تعیین کرد که آیا می توان چنین انحرافی را از هر تعداد پل واقع در به هر حال یا نه، به طوری که می توان آنها را در شکل زیر نشان داد که در آن 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 مفید است.

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

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

اسناد مشابه

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

کار آزمایشگاهی، اضافه شده 01/09/2009

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

چکیده، اضافه شده در 1390/06/13

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

ارائه، اضافه شده در 11/19/2013

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

کار دوره، اضافه شده در 2014/09/30

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

پایان نامه، اضافه شده در 2011/07/19

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

کار دوره، اضافه شده در 2009/02/21

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

کارهای آزمایشگاهی، اضافه شده در 2012/03/11

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

معرفی

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

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

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

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

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

فرضیه ها:

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

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

وظایف:

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

یک وب سایت برای آزمایش ایجاد کنید مشکلات المپیاد

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

موضوعات مورد مطالعه:وظایف المپیاد، سیستم های هشدار

موضوع مطالعه:تئوری گراف، برنامه نویسی وب

روش های پژوهش:

روش های نظریه گراف

روش های برنامه نویسی وب

طرح تحقیق:

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

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

دوره برنامه نویسی وب مدرسه را بگذرانید فناوری اطلاعات"واقعی"

یک وب سایت برای تست مسائل المپیاد در تئوری گراف ایجاد کنید و آن را روی دوستان تست کنید

طراحی یک سیستم هشدار کلاس فوری (UCA)

آزمایشی را برای آزمایش سیستم RNS انجام دهید

فصل 1. نظریه گراف در زندگی ما

1.1. کاربرد نظریه گراف در مناطق مختلف

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

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

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

امروزه، به لطف اینترنت، «شبکه‌ای از شبکه‌ها» که رایانه‌ها را در سراسر جهان به هم متصل می‌کند، انقلاب دیجیتال امکان‌پذیر شده است. قدرت رایانه ها به طور پیوسته افزایش یافته است، اما به لطف شبکه ها بود که جهش عظیم به دنیای دیجیتال ممکن شد. نمودارها و مخابرات همیشه دست به دست هم داده اند.

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

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

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

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

a - اتوبوس مشترک، b - ستاره، c - حلقه

بازی‌های زیادی وجود دارند که در آن‌ها باید یک نمودار خاص (بازی‌های پیچ و خم) بسازید یا از نمودار برای تعیین وجود استراتژی برنده استفاده کنید.

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

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

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

1.2. نتیجه گیری در مورد فصل.

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

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

فصل 2. تئوری نمودار برای کمک به دانش آموزان

2.1. نظریه گراف در مسائل المپیاد

المپیادهای مختلف ریاضی مانند "Kangaroo"، "Dino-Olympiad Uchi.ru"، المپیاد بین المللی اکتشافی "Owlet" نیز اغلب شامل مسائل مربوط به نظریه گراف در فرمول های مختلف می شوند.

همانطور که می دانید، بچه ها به هر چیزی که مربوط به کامپیوتر و اینترنت است علاقه زیادی دارند و نمی توان آنها را با کتاب ریاضی پشت میز نشست. به منظور برانگیختن علاقه دانش آموزان به نظریه گراف، نویسندگان مقاله، بر اساس دوره های تکمیل شده در برنامه نویسی وب در دانشکده فناوری اطلاعات REAL-IT، یک شبیه ساز آنلاین، از جمله آزمایش در نظریه گراف، که در صفحه قرار دارد، توسعه دادند. مدرسه خصوصی تیومن "Evolventa" ": evolventa-tmn.github.io. از دانش‌آموزان خواسته می‌شود که شش مشکل با سطوح دشواری مختلف را حل کنند، او پاسخ‌ها را در کادرها وارد می‌کند و سپس با کلیک کردن روی دکمه «انجام شد»، نتیجه داده می‌شود: تعداد مشکلاتی که او به درستی حل کرده است (شکل 2.1).

شکل 2.1. قطعه ای از صفحه سایت با گزینه های تست

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

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

2.2. نظریه گراف در طراحی سیستم هشدار کلاس درس

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

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

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

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

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

شکل 2.2. کلاس ما در سفر به مؤسسه خودمختار دولتی "مرکز منطقه ای آموزش پیش از خدمت اجباری و آموزش میهنی "Avanpost"

در این کار سعی شده است با استفاده از مثال یک کلاس یک سیستم اطلاع رسانی جمعی ایجاد شود موسسه تحصیلی: دبیرستان MAOU شماره 89.

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

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

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

در 19 نوامبر 2017، سیستم SOC طراحی شده مورد آزمایش قرار گرفت. در ابتدا برنامه ریزی کردیم که این اعلام در سه دور انجام شود. برای حلقه اول (شروع اعلان)، ما دو کودک را انتخاب کردیم که هیچ کس نمی خواهد با آنها تماس بگیرد، اما آنها آماده تماس هستند، و همچنین خود نویسندگان پروژه (شکل 2.3، بلوک های صورتی). سپس اطلاعات به دایره هشدار دوم منتقل می شود (شکل 2.4، بلوک های زرد). و در دایره اعلان سوم (شکل 2.4 بلوک های سبز) به کل کلاس اطلاع داده می شود. اما در حین آزمایش دیدیم که برخی از کودکان 1.5-2 ساعت تمرین می کنند و به تلفن نگاه نمی کنند، برخی دیگر تعادل منفی دارند، بنابراین نمی توانند تماس بگیرند.

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

شکل 2.4. حلقه های هشدار سیستم SOK

بنابراین، در واقع، کلاس ما فقط 490 دقیقه قبل اطلاع رسانی شد - این 8 ساعت و 10 دقیقه است. اما همه چیز 100٪ بود. نکته مهم در اینجا این است که سیستم ما ساختار یک درخت نیست، بلکه یک نمودار است. و در آن مسیرهای متعددی از یک قله به قله دیگر منتهی می شود که در هر صورت به همه اطلاع داده می شود!

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

شکل 2.6. برنامه اطلاع رسانی کلاس

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

یک نتیجه آزمایش دیگر - بررسی موضوعات مورد علاقه (شکل 2.7) نشان داد که کودکان کلاس ما بیشتر از همه به ریاضیات، علوم کامپیوتر و بازی های فضای باز علاقه دارند! این بدان معناست که آنها ممکن است به اندازه ما عاشق نظریه گراف باشند.

شکل 2.7. نمودار دایره ای اقلام کلاس مورد علاقه

2.3. نتیجه گیری در مورد فصل.

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

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

نتیجه.

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

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

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

Beloborodova A.A. توسعه تفکر فضایی با استفاده از بازی های هزارتویی / A.A. Beloborodova // "تالار علمی دانشجویی": مواد هشتم الکترونیک دانشجویی بین المللی کنفرانس علمی.- 2017. https://www.site/2017/7/26746

بلوبورودوا، A.A. توسعه یک شبیه ساز وب برای مطالعه نظریه گراف / A.A. بلوبورودوا، S.V. پاخوتین، ع.الف. فرولوف // فناوری های جدید اطلاعات در صنعت نفت و گاز و آموزش: مواد هفتم کنفرانس بین المللی علمی و فنی؛ پاسخ ویرایش او کوزیاکوف - تیومن: TIU، 2017. - صص 156-159.

Beloborodova A.A. با ریاضی نمی توان گم شد! / ع.الف. Beloborodova // XVIII مسابقه تحقیقات علمی کودکان همه روسیه. و کارهای خلاقانه"گام های اولیه در علم": مجموعه ای از چکیده ها - M.: انسجام NS، دومای ایالتی مجلس فدرال فدراسیون روسیه، وزارت آموزش و پرورش و علوم روسیه - 2016. - P. 110-111.

Gendenstein، L.E. آلیس در سرزمین ریاضیات. داستان پریان / برای کودکان کوچکتر. و چهارشنبه سن مدرسه.- خارکف: انتشارات - تجارت. شرکت "Paritet" LTD, 1994.-288 p., ill.

دولتشین، م.ی. بررسی اثربخشی روش های حذف نویز تصویر / M. I. Davletshin, K. V. Syzrantseva // صرفه جویی در انرژی و فن آوری های نوآورانهدر مجتمع سوخت و انرژی: مواد بین المللی. علمی-عملی conf. دانشجویان، دانشجویان تحصیلات تکمیلی، دانشمندان جوان و متخصصان. T.1 / پاسخ سردبیر A.N. خلین. - تیومن: TIU، 2016. - صص 25-29.

کارناوخوا، A.A. استفاده از نظریه گراف در حل مسائل اقتصاد / A.A. کارناوخوا، A.F. Dolgopolova // مواد هفتم کنفرانس علمی الکترونیکی دانشجویی بین المللی "تالار علمی دانشجویی". http://www.scienceforum.ru/2015/991.

کرن، جی. هزارتوهای جهان. سن پترزبورگ: انتشارات «آزبوکا-کلاسیک»، 2007، 448 ص.

کراوس، ام.و. کاربرد فناوری اطلاعات برای طراحی سیستم هشدار تیمی / M.V. کراوز، A.A. بلوبورودوا، E.I. آربوزووا // فناوری های جدید اطلاعات در صنعت نفت و گاز و آموزش: مواد هفتم کنفرانس بین المللی علمی و فنی؛ پاسخ ویرایش او کوزیاکوف - تیومن: TIU، 2017. - صص 153-156.

دوره آموزشی "ساخت وب سایت" دانشکده فناوری اطلاعات "REAL-IT" http://it-schools.org/faculties/web/

دنیای ریاضیات: در 40 جلد T.11: Claudi Alsina. نقشه های مترو و شبکه های ترون. نظریه گراف./Trans. از اسپانیایی - M.: De Agostini, 2014. - 144 p.

المپیاد آموزشی Moskevich L.V. - یکی از اشکال کلاس های ریاضیات فوق برنامه / L.V. Moskevich // مجله الکترونیکی علمی و روش شناختی "مفهوم". - 2015. - T. 6. - P. 166-170. - آدرس اینترنتی: http://e-koncept.ru/2015/65234.htm.

یادداشت به مردم "اطلاع رسانی به مردم در صورت تهدید و اضطرار" http://47.mchs.gov.ru/document/1306125

رومیانتسف، V.O. مدل سازی ریاضی سیستم حمل و نقل گاز با استفاده از نظریه گراف / V. O. Rumyantsev // مشکلات زمین شناسی و توسعه زیر خاک: مجموعه. علمی tr. / TPU. - تومسک، 2017. - ص 340 - 342.

وب سایت وزارت شرایط اضطراری فدراسیون روسیه http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves