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

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

نمودارها ساخته می شوندبه منظور نمایش روابط در مجموعه ها. مثلاً یک مجموعه باشد آ = {آ1 , آ 2 , ... آن)- تعداد زیادی از افراد، و هر عنصر به عنوان یک نقطه نمایش داده می شود. یک دسته از ب = {ب1 , ب 2 , ... بم)- بسیاری از اتصالات (خطوط مستقیم، قوس ها، بخش ها - هنوز مهم نیست). سر صحنه آرابطه آشنایی بین افراد از این مجموعه آورده شده است. ساختن نموداراز نقاط و اتصالات. پیوندها جفت افرادی را که یکدیگر را می شناسند به هم متصل می کند. طبیعتاً ممکن است تعداد آشنایان برخی از افراد با تعداد آشنایان افراد دیگر متفاوت باشد و برخی ممکن است به خوبی کسی را نشناسند (اینگونه عناصر نقاطی خواهند بود که به دیگری متصل نیستند). بنابراین ما یک نمودار داریم!

آنچه را که ابتدا «نقاط» نامیدیم، باید رئوس نمودار نامیده شود، و آنچه را که «اتصالات» نامیدیم، باید لبه‌های نمودار نامیده شود.

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

و اکنون تعاریف دقیق ریاضی از یک نمودار.

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

تعریف 2.اجازه دهید V– (غیر خالی) مجموعه رئوس، عناصر v∈V- قله ها نمودار جی = جی(V) با رئوس زیاد Vیک خانواده خاص از جفت های فرم وجود دارد: ه = (آ, ب) ، جایی که آ,ب∈V ، نشان می دهد که کدام رئوس متصل باقی می مانند. هر جفت ه = (آ, ب) - لبه نمودار یک دسته از U- لبه های زیاد هنمودار قله ها آو ب- نقاط انتهایی لبه ه .

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

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

مفاهیم اساسی نظریه گراف

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

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

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

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

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

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

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

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

درختان ریشه دار (که در آن یکی از رئوس انتخاب شده است)؛
همه درختان؛
درختانی که درجه رأس آنها از 4 تجاوز نمی کند.
درختانی که درجه رأس آنها 1 و 4 است (بیان مسئله ای از شیمی).

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

مثال 1.اجازه دهید آ- مجموعه اعداد 1، 2، 3: آ= (1، 2، 3). یک نمودار برای نمایش رابطه بسازید "

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

بنابراین، در کثرت ما آعدد 1 کوچکتر از عدد 2 و عدد 3 و عدد 2 کمتر از عدد 3 است. نمودار زیر را دریافت می کنیم:

مثال 2.اجازه دهید آ- مجموعه اعداد 2، 4، 6، 14: آ= (2، 4، 6، 14) . یک نمودار برای نمایش رابطه «قابل تقسیم بر» در این مجموعه ایجاد کنید.

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

مثال 3.اجازه دهید مجموعه های داده شده آ= (α، β، γ) و ب= (الف، ب، ج) . یک نمودار بسازید تا رابطه «ضرب دکارتی مجموعه ها» را نمایش دهد.

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

مثال 4.آژانس املاک و مستغلات مدیران ایگور، سرگئی و پیتر را استخدام می کند. اشیاء O1، O2، O3، O4، O5، O6، O7، O8 سرویس می شوند. نموداری بسازید تا روابط "ایگور با اشیاء O4، O7 کار می کند"، "سرگئی با اشیاء O1، O2، O3، O5، O6 کار می کند"، "پیتر با شی O8 کار می کند" را نمایش دهد.

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

و دوباره به مثال هایی با اعداد.

مثال 5.بگذارید یک مجموعه داده شود سی = {2, 3, 5, 6, 15, 18} . نموداری بسازید که رابطه ای را پیاده سازی کند که تمام جفت اعداد را تعریف کند آو باز بسیاری سی، که در آن هنگام تقسیم عنصر دوم بر عنصر اول، ضریبی به دست می آوریم که یک عدد صحیح بزرگتر از 1 است.

راه حل. نموداری که این روابط را نشان می‌دهد جهت‌دار خواهد بود، زیرا شرط شامل ذکر عنصر دوم و اول است، یعنی لبه از عنصر اول به عنصر دوم هدایت می‌شود. از اینجا به وضوح مشخص می شود که کدام عنصر اول و کدام عنصر دوم است. بیایید اصطلاحات بیشتری اضافه کنیم: لبه های جهت دار معمولاً قوس نامیده می شوند. در نمودار ما 7 کمان وجود خواهد داشت: ه1 = (3, 15) , ه2 = (3, 18) , ه3 = (5, 15) , ه4 = (3, 6) , ه5 = (2, 18) , ه6 = (6, 18) , ه7 = (2, 6) . در این مثال، لبه‌ها (قوس‌های) نمودار به سادگی شماره‌گذاری می‌شوند، اما شماره سریال تنها چیزی نیست که می‌توان به یک کمان نسبت داد. قوس را می توان به مقیاس ها نیز نسبت داد، به عنوان مثال، هزینه ارسال محموله از یک نقطه به نقطه دیگر. اما در ادامه و با جزئیات بیشتر با وزنه های قوسی آشنا می شویم. بنابراین، نمودار جهت دار زیر را دریافت می کنیم:

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

مثال 6.روی یک صفحه شطرنج به ابعاد 3×3، دو شوالیه سفید و دو شوالیه سیاه مانند شکل زیر قرار داده شده اند.

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

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

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

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

مثال 7.مشکل در مورد گرگ، بز و کلم. در یک ساحل رودخانه یک مرد (H)، یک قایق، یک گرگ (V)، یک بز (Kz) و یک کلم (Kp) وجود دارد. یک شخص و بیش از یکی از اشیاء حمل شده نمی تواند همزمان در قایق باشد. انسان باید همه اشیاء را با رعایت این شرط به طرف دیگر منتقل کند: گرگ را با بز و بز را با کلم بدون مراقبت رها نکند.

راه حل. در نمودار ساخته شده، راس ها پیکربندی هستند و لبه ها رابطه "اتصال با یک قایق سواری" بین پیکربندی ها هستند. پیکربندی به چیدمان اشیاء در بانک اصلی و روی کرانه مقابل اشاره دارد. هر پیکربندی به صورت ( آ|ب) ، جایی که آ- اشیاء واقع در ساحل اصلی، و ب- اشیاء واقع در ساحل مقابل. بنابراین پیکربندی اولیه این است - (PMCpKz| ) . به عنوان مثال، پس از انتقال یک بز به طرف دیگر، پیکربندی خواهد شد (VKp|ChKz) . پیکربندی نهایی همیشه است ( |PMCpKz) . اکنون می‌توانیم یک نمودار بسازیم، از قبل بدانیم که راس‌ها و یال‌ها به چه معنا هستند:

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

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

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

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

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

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

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

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

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

نمودارها و برنامه ریزی شبکه

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

PERT - تکنیک ارزیابی و بازبینی برنامه (پروژه) - تکنیکی برای ارزیابی و تجزیه و تحلیل برنامه ها (پروژه ها) که در مدیریت پروژه استفاده می شود.

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

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

در ستونی مانند این:

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

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

کل بلوک "تئوری گراف"

کلید واژه ها:

شیء گرافیکی
گرافیک کامپیوتری
گرافیک شطرنجی
گرافیک برداری
فرمت های فایل های گرافیکی

طراحی، نقاشی، طراحی، عکس و سایر تصاویر گرافیکی را اشیاء گرافیکی می نامند.

3.2.1. زمینه های کاربرد گرافیک کامپیوتری

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

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

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

برنج. 3.5.
نمونه های گرافیک کامپیوتری

http://snowflakes.barkleyus.com/ - با استفاده از ابزارهای رایانه ای می توانید هر دانه برفی را "برش دهید".
http://www.pimptheface.com/create/ - می توانید با استفاده از یک کتابخانه بزرگ از لب ها، چشم ها، ابروها، مدل مو و سایر قطعات یک چهره ایجاد کنید.
http://www.ikea.com/ms_RU/rooms_ideas/yoth/index.html - سعی کنید مبلمان و مواد تکمیلی جدید را برای اتاق خود انتخاب کنید.

3.2.2. روش های ایجاد گرافیک دیجیتال

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

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

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

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

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

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

اندازه پیکسل ها به وضوح اسکنر بستگی دارد که معمولاً بر حسب dpi (نقطه در اینچ - نقطه در اینچ 1) بیان می شود و با یک جفت اعداد (مثلاً 600 x 1200 dpi) مشخص می شود. عدد اول تعداد پیکسل هایی است که می توان توسط اسکنر در یک خط تصویر به طول 1 اینچ استخراج کرد. عدد دوم تعداد خطوطی است که یک نوار تصویر به ارتفاع 1 اینچ را می توان به آنها تقسیم کرد.

1 اینچ یک واحد طول در سیستم اندازه گیری انگلیسی است که برابر با 2.54 سانتی متر است.

وظیفه. یک تصویر رنگی با ابعاد 10×10 سانتی متر اسکن می شود. وضوح اسکنر 1200×1200 نقطه در اینچ و عمق رنگ 24 بیت است. فایل گرافیکی حاصل چه حجم اطلاعاتی خواهد داشت؟

راه حل. اندازه تصویر اسکن شده تقریباً 4 اینچ در 4 اینچ است. با در نظر گرفتن وضوح اسکنر، کل تصویر به 4 4 1200 1200 پیکسل تقسیم می شود.

پاسخ: تقریباً 66 مگابایت.

توصیه می کنیم انیمیشن های "اسکنرها: اصول کلی عملکرد"، "اسکنرها: اسکنر تخت" را که در مجموعه یکپارچه منابع آموزشی دیجیتال (http://school-collection.edu.ru/) ارسال شده است، تماشا کنید. این منابع به شما کمک می کنند تا نحوه عملکرد اسکن را بهتر درک کنید. منبع "دوربین دیجیتال" نحوه گرفتن عکس های دیجیتال را نشان می دهد (شکل 3.6).

برنج. 3.6.
اسکنر تخت و دوربین دیجیتال

3.2.3. گرافیک شطرنجی و برداری

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

گرافیک شطرنجی

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

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

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

برنج. 3.7.
تصویر شطرنجی و قطعه بزرگ شده آن

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

گرافیک برداری

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

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

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

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

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

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

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

گرافیک فراکتال مانند گرافیک برداری بر اساس محاسبات ریاضی است. اما، برخلاف گرافیک برداری، حافظه کامپیوتر توصیفات اشکال هندسی تشکیل دهنده تصویر را ذخیره نمی کند، بلکه خود فرمول ریاضی (معادله) را که برای ساختن تصویر استفاده می شود، ذخیره می کند. تصاویر فراکتال متنوع و عجیب هستند (شکل 3.10).

برنج. 3.10.
گرافیک فراکتال

شما می توانید اطلاعات کامل تر در مورد این موضوع را در اینترنت بیابید (به عنوان مثال، در http://ru.wikipedia.org/wiki/Fractal).

3.2.4. فرمت های فایل های گرافیکی

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

فرمت های گرافیکی جهانی توسط همه برنامه هایی که با گرافیک های شطرنجی (وکتوری) کار می کنند، "درک" می شوند.

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

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

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

فرمت های گرافیکی برداری جهانی شامل فرمت WMF است که برای ذخیره مجموعه ای از تصاویر مایکروسافت (http://office.microsoft.com/ru-ru/clipart) استفاده می شود.

فرمت جهانی EPS به شما امکان می دهد اطلاعات مربوط به گرافیک های شطرنجی و برداری را ذخیره کنید. اغلب برای وارد کردن 2 فایل به برنامه های چاپ استفاده می شود.

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

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

مشکل 1. برای رمزگذاری یک پیکسل، 3 بایت استفاده می شود. این عکس با ابعاد 2048 در 1536 پیکسل به عنوان یک فایل فشرده نشده ذخیره شد. اندازه فایل حاصل را تعیین کنید.

راه حل.

پاسخ: 9 مگابایت

مشکل 2. یک تصویر بیت مپ 128 در 128 پیکسل فشرده نشده 2 کیلوبایت حافظه اشغال می کند. حداکثر تعداد رنگ ممکن در پالت تصویر چقدر است؟

راه حل.

پاسخ: 2 رنگ - سیاه و سفید.

مهم ترین

گرافیک کامپیوتری مفهومی گسترده است که به موارد زیر اشاره دارد: 1) انواع مختلف اشیاء گرافیکی ایجاد شده یا پردازش شده با استفاده از رایانه. 2) حوزه ای از فعالیت که در آن رایانه ها به عنوان ابزاری برای ایجاد و پردازش اشیاء گرافیکی استفاده می شوند.

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

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

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

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

سوالات و وظایف

گرافیک کامپیوتری چیست؟
زمینه های اصلی کاربرد گرافیک کامپیوتری را فهرست کنید.
چگونه می توان گرافیک دیجیتال تولید کرد؟
یک تصویر رنگی با ابعاد 10 x 15 سانتی متر اسکن می شود. وضوح اسکنر 600 x 600 dpi، عمق رنگ 3 بایت است. فایل گرافیکی حاصل چه حجم اطلاعاتی خواهد داشت؟
تفاوت بین روش های شطرنجی و برداری برای نمایش یک تصویر چیست؟
چرا اعتقاد بر این است که تصاویر شطرنجی رنگ را بسیار دقیق منتقل می کنند؟
کدام عملیات تبدیل یک تصویر شطرنجی منجر به بیشترین کاهش کیفیت آن می شود - کاهش یا بزرگ شدن؟ چگونه می توانید این را توضیح دهید؟
چرا مقیاس گذاری بر کیفیت تصاویر وکتور تأثیر نمی گذارد؟
چگونه می توانید انواع فرمت های فایل های گرافیکی را توضیح دهید؟
تفاوت اصلی بین فرمت های گرافیکی جهانی و فرمت های کاربردی گرافیکی اختصاصی چیست؟
تا حد امکان یک نمودار کامل برای مفاهیم بخش 3.2.4 بسازید.
شرح مفصلی از تصاویر شطرنجی و برداری ارائه دهید و موارد زیر را مشخص کنید:
طراحی 1024 x 512 پیکسل به عنوان یک فایل 1.5 مگابایتی فشرده نشده ذخیره شد. چه مقدار اطلاعات برای رمزگذاری رنگ پیکسل استفاده شده است؟ حداکثر تعداد رنگ ممکن در یک پالت متناسب با این عمق رنگ چقدر است؟
یک تصویر بیت مپ 256 در 128 پیکسل فشرده نشده 16 کیلوبایت حافظه اشغال می کند. حداکثر تعداد رنگ ممکن در پالت تصویر چقدر است؟

فرمت های گرافیکی جهانی توسط همه برنامه هایی که با گرافیک های شطرنجی (وکتوری) کار می کنند، "درک" می شوند.

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

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

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

فرمت جهانی EPS به شما امکان می دهد اطلاعات مربوط به گرافیک های شطرنجی و برداری را ذخیره کنید. اغلب برای واردات استفاده می شود! فایل ها را به برنامه هایی برای تهیه محصولات چاپی تبدیل کنید.

مشکل 1. 3 بایت برای رمزگذاری یک پیکسل استفاده می شود. این عکس با ابعاد 2048 در 1536 پیکسل به عنوان یک فایل فشرده نشده ذخیره شد. اندازه فایل حاصل را تعیین کنید. راه حل.

I-k.i i-I/k

i-2. 1024 8/(128. 128) =

2 2 10 2 3 /(2 7 2 7) = 2 1 + 10 + 3 / 2 7 + 7 2 14 / 2 14 = 1 (بیت). LG-21-2.

پاسخ: 2 رنگ - سیاه و سفید.

مهم ترین

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

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

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

a سوالات و وظایف

1. گرافیک کامپیوتری چیست؟

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

H. چگونه می توان گرافیک دیجیتال تولید کرد؟

4. یک تصویر رنگی با ابعاد 10 x 15 سانتی متر اسکن می شود، وضوح اسکنر 600 x 600 dpi، عمق رنگ - 3 بایت است. فایل گرافیکی حاصل چه حجم اطلاعاتی خواهد داشت؟

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

ب چرا اعتقاد بر این است که تصاویر شطرنجی رنگ را بسیار دقیق منتقل می کنند؟

7. کدام عملیات تبدیل یک تصویر شطرنجی به بیشترین کاهش کیفیت منجر می شود - کاهش یا بزرگ شدن؟ چگونه می توانید این را توضیح دهید؟

8. چرا مقیاس گذاری بر کیفیت تصاویر وکتور تأثیر نمی گذارد؟

9. چگونه می توانید انواع فرمت های فایل های گرافیکی را توضیح دهید؟

گرافیک کامپیوتری

10. تفاوت اصلی بین فرمت های گرافیکی جهانی و فرمت های کاربردی گرافیکی اختصاصی چیست؟

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

12. شرح مفصلی از تصاویر شطرنجی و وکتوری با ذکر موارد زیر ارائه دهید:

الف) تصویر از چه عناصری ساخته شده است.

ب) چه اطلاعاتی در مورد تصویر در حافظه خارجی ذخیره می شود.

ج) چگونه اندازه یک فایل حاوی یک تصویر گرافیکی تعیین می شود.

د) چگونه کیفیت تصویر هنگام مقیاس بندی تغییر می کند.

ه) مزایا و معایب اصلی تصاویر شطرنجی (وکتور) چیست؟

13. نقاشی با ابعاد 1024 x 512 پیکسل به عنوان یک فایل فشرده نشده با حجم 1.5 مگابایت ذخیره شد. چه مقدار اطلاعات برای رمزگذاری رنگ پیکسل استفاده شده است؟ حداکثر تعداد رنگ ممکن در یک پالت متناسب با این عمق رنگ چقدر است؟

14. یک تصویر شطرنجی فشرده نشده با ابعاد 256 در 128 پیکسل، 16 کیلوبایت حافظه اشغال می کند. حداکثر تعداد رنگ ممکن در پالت تصویر چقدر است؟

اطلاعات نظری

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

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

تعداد رئوس با درجات فرد در هر گراف زوج است.
در هر نمودار با پقله هایی که در آن پ> 2، همیشه حداقل دو راس با درجه یکسان وجود دارد.
اگر در یک نمودار با رئوس p> 2 دقیقاً دو راس دارای درجه یکسانی هستند، سپس در این نمودار همیشه یا دقیقاً یک راس درجه 0 یا دقیقاً یک راس درجه وجود دارد. (پ - 1).

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

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

X 5 (y /) =2t'

جایی که تی -تعداد رئوس، و جمع بر روی تمام رئوس از 1 تا انجام می شود پ.

وظایف

مشکل 2.42. یک نمودار بر روی هشت راس بسازید که دارای توزیع درجه رئوس زیر باشد: دو راس درجه 4. سه راس درجه 3; دو راس درجه 2؛ یک راس درجه 1.

راه حل.

مجموع درجه همه رئوس 2-4 + 3- 3 + 2- 2+1 1=22 است، یعنی در مجموع 11 یال وجود دارد. ساختن نمودارها بر اساس بردار درجات، با شروع از رئوس درجات بزرگ آسانتر است. Ver-

جدول 2.9

مطابقت بین توصیف یک گراف و خواص آن

صفت	عددی	چه مفهومی داره
		نمودار دقیقاً یک جزء متصل دارد
نامنسجم		نمودار بیش از یک جزء دارد، قطر آن دقیقاً برابر با بی نهایت است
منظم	5 (U;) = SOSHI	درجات همه رئوس برابر است
مدرک تحصیلی منظم	ز(Уі)=У	درجات همه رئوس برابر است تواگر شناخته شود پ(تعداد رئوس)، سپس می توانید بلافاصله محاسبه کنید تی(تعداد دنده): y-p؟ y/2 (پیا درباید عدد زوج باشد)
غیر حلقوی	y= t-p + k = 0	عدد سیکلوماتیک صفر است، نمودار هیچ چرخه ای ندارد، یک درخت یا یک جنگل است (بسته به اتصال)، چنین نمودارهایی همیشه می توانند در دو رنگ رنگی شوند. اگر دو متغیر از سه متغیر شناخته شده باشد ( پ, تی، ک)،سپس با استفاده از فرمول می توانید بقیه را پیدا کنید
درخت (یا نمودار متصل غیر چرخه ای)	y= t- n + 1 = 0، از آنجاست T- n - 1	عدد سیکلوماتیک صفر است، نمودار هیچ چرخه ای ندارد، یک درخت است، چنین نمودارهایی را همیشه می توان در دو رنگ رنگ کرد. اگر یکی از دو متغیر شناخته شده باشد ( پیا ت)سپس با استفاده از فرمول می توانید دومی را پیدا کنید
دو رنگی		عدد کروماتیک یک نمودار دو است، چنین نمودارهایی را می توان همیشه در دو رنگ رنگ کرد، این نمودارها دو قسمتی هستند، از نظر گرافیکی یا نمودارهای غیر چرخه ای هستند یا نمودارهایی که در آنها همه چرخه ها دارای طول زوج هستند.

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

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

برنج. 2.8.

دو راس درجه 2؛ یک راس درجه 1؛ یک راس دارای درجه دلخواه است.

راه حل.

درجه کل رئوس 11 است، بنابراین، راس باقی مانده باید یک درجه فرد داشته باشد، یعنی. 1،3 یا 5. بنابراین، امکان ساخت سه نمودار مختلف وجود دارد (شکل 2.9).

برنج. 2.9.

مشکل 2.44. یک نمودار با بردار درجه رأس زیر بسازید: 5 = (1، 2، 2، 3، 4، 4، 5).

راه حل.

درجه کل 5 + 8 + 3 + 4 + 1 = 21 است. از آنجایی که این یک عدد فرد است، که با قضیه در تضاد است (تعداد یال ها نصف این عدد است، اما 21 به طور مساوی بر 2 بخش پذیر نیست).

پاسخ.چنین نموداری وجود ندارد.

مسئله 2.45. یک نمودار با بردار درجات رأس زیر بسازید: 5 = (1، 1،2، 2، 2، 4، 4، 4، 4).

مسئله 2.46. یک نمودار با بردار درجه رأس زیر بسازید: 5 = (5، 5، 6، 6، 6، 6، 6).

مشکل 2.47. یک نمودار با بردار درجات رأس زیر بسازید: 5 = (1، 1، 1،2، 3، 3، 3، 3، 5، 5، 5).

مشکل 2.48. نموداری با بردار درجات رأس زیر بسازید: 5 = (3، 3، 3، 3، 3، 3، 3، 7).

مسئله 2.49. بر روی شش راس نموداری بسازید که دارای توزیع درجات رأس زیر باشد: سه راس درجه 5 و سه راس دیگر درجه ناشناخته هستند.

مشکل 2.50. یک نمودار بر روی ده رأس بسازید، با دوبرابر تعداد یال ها و توزیع درجه رئوس زیر: دو راس درجه 6. چهار راس درجه 5; دو راس درجه 4; دو راس درجه دلخواه - یا عدم امکان ساخت چنین نموداری را توجیه می کند.

مسئله 2.51. یک نمودار بر روی ده راس بسازید که دارای توزیع درجه رئوس زیر باشد: یک راس درجه 7. دو راس درجه 6; دو راس درجه 5; دو راس درجه 4; دو راس درجه 3; یک راس درجه 2 - یا عدم امکان ساخت چنین نموداری را توجیه کنید.

مسئله 2.52. یک نمودار بر روی 11 راس بسازید که دارای توزیع درجه رئوس زیر باشد: یک راس درجه 7. دو راس درجه 6; دو راس درجه 5; دو راس درجه 4; دو راس درجه 3; یک راس درجه 2 - یا عدم امکان ساخت چنین نموداری را توجیه کنید.

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

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

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

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

1. گراف جهت دار(به طور خلاصه دیگراف) - که به لبه های آن جهت اختصاص داده شده است.

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

3. نمودار وزنی- قوس ها یا لبه ها وزن دارند (اطلاعات اضافی).

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

وظیفه 1.

راه حل: اجازه دهید دانشمندان را به عنوان رئوس نمودار نشان دهیم و از هر رأس به چهار راس دیگر خطوطی رسم کنیم. ما 10 خط دریافت می کنیم که به عنوان دست دادن در نظر گرفته می شود.

وظیفه 2.

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

راه حل:

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

وظیفه 3.

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

راه حل:

در زیر به تفکیک وظایف اشاره شده است.

شاید خواندن آن مفید باشد: