تعریف گراف

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 04 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 52 مرتبه

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

تعریف گراف - پیمان گردلو

رودخانه این شهر از میان شهر عبور می‌کرد (مانند آن‌چه در نقشه فوق می‌بینید) شهر را به چند قسمت تقسیم می‌کرد.

برخی از مردم این شهر کنجکاو بودند که بدانند آیا می‌توان با حرکت از یک نقطه از شهر و دقیقا یک‌بار عبور از هر کدام از پُل‌ها، به نقظه شروع حرکت بازگشت؟

نمای گرافیکی شهر را در شکل زیر می‌بینید:

تعریف گراف - پیمان گردلو

لئونارد اویلر 1707-1783 ریاضی‌دان برجسته سوئیسی، برای حل این مسئله از شکل زیر، که آن را امروزه به نام گراف می‌شناسیم، کمک گرفت و با استدلال، ثابت کرد که این‌کار امکان پذیر نیست.

تعریف گراف - پیمان گردلو

اگر چهار ناحیه x,y,z,w را با چهار نقطه نمایش دهیم و به‌ازای هر پل که بین دو ناحیه قرار دارد، نقاط متناظر با آن ناحیه ها را به هم وصل کنیم، شکل فوق  به‌دست می‌آید که گرافِ حاصل از مدل سازی مساله مذکور است.

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

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

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

تمرین

سه خانه و سه چاه آب مانند شکل زیر مفروضند:

تعریف گراف - پیمان گردلو

آیا می‌توان از هر چاه به هر خانه یک کانال آب حفر کرد به‌طوری که هیچ دو کانالی یک‌دیگر را قطع نکند؟

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


اگر خانه‌ها و چاه‌ها را 6 نقطه مشخص کنیم و کانال‌ها را با خطوط یا منحنی‌ها، نمایش دهیم.


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


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

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

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

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

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

تمرین

گراف G را با 9 راس و 10یال مانند شکل زیر در نظر بگیرید: 

تعریف گراف - پیمان گردلو

مجموعه راس‌های گراف G را نمایش دهید.  

VG=v1,v2,,v9

مجموعه یال‌های گراف G را نمایش دهید.  

EG=v1v2,v1v4,v1v8,v2v3,v2v5,v4v5,v4v6,v5v7,v6v8,v7v8

تذکر

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

تعریف گراف‌های مساوی

دو گراف G1=(V1,E1) و G2=(V2,E2) مساویند، هرگاه V1=V2E1=E2.

به‌عنوان نمونه دو گراف G1 و G2 در زیر مساویند.:

تعریف گراف - پیمان گردلو

تعریف گراف - پیمان گردلو

تمرین

گراف G را در نظر بگیرید:

تعریف گراف - پیمان گردلو

تساوی گراف فوق را با گراف‌های زیر، بررسی کنید. 

تعریف گراف - پیمان گردلو

در گراف فوق، راس 1 به راس 6 وصل است، در صورتی‌که در گراف G راس 1 به راس 6 وصل نیست. تساوی دو گراف برقرار نیست.

تعریف گراف - پیمان گردلو

در گراف فوق، راس 1 به راس 3 وصل است، در صورتی‌که در گراف G راس 1 به راس 3 وصل نیست. تساوی دو گراف برقرار نیست.

تعریف گراف - پیمان گردلو

گراف فوق مساوی گراف G است. 

تذکر

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

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

تمرین

گراف جهت‌دار G را در نظر بگیرید:

تعریف گراف - پیمان گردلو

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

V=a,b,c,dE=a,b,a,c,c,a,d,b

تمرین

گراف جهت‌دار G را در نظر بگیرید:

تعریف گراف - پیمان گردلو

5 تیم a,b,c,d,e در یک گروه قرار دارند و تیم‌ها دوبه‌دو با هم بازی می‌کنند وبرخی از این بازی‌ها انجام شده است.

به‌ازای هر تیم یک نقطه گذاشته‌ایم و هر دو نقطه را به‌هم وصل کرده‌ایم.

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

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

تیم a تیم‌های b و e را برده و به تیم c باخته است.

تیم b به تیم a باخته و از تیم‌ d برده است.

تیم c تیم‌های a و e را برده است.

تیم d تیم‌های b و e باخته است.

تیم e به تیم‌های a و c باخته است و از تیم d برده است.

برای ارسال نظر وارد سایت شوید